{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T23:37:58Z","timestamp":1723073878971},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T00:00:00Z","timestamp":1616371200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1535821"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2021,4]]},"abstract":"\n We present the\n Succinct Range Filter<\/jats:italic>\n (SuRF), a fast and compact data structure for approximate membership tests. Unlike traditional Bloom filters, SuRF supports both single-key lookups and common range queries, such as range counts. SuRF is based on a new data structure called the\n Fast Succinct Trie (FST)<\/jats:italic>\n that matches the performance of state-of-the-art order-preserving indexes, while consuming only 10 bits per trie node---a space close to the minimum required by information theory. Our experiments show that SuRF speeds up range queries in a widely used database storage engine by up to 5\u00d7.\n <\/jats:p>","DOI":"10.1145\/3450262","type":"journal-article","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T14:36:31Z","timestamp":1616423791000},"page":"166-173","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Succinct range filters"],"prefix":"10.1145","volume":"64","author":[{"given":"Huanchen","family":"Zhang","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Hyeontaek","family":"Lim","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Viktor","family":"Leis","sequence":"additional","affiliation":[{"name":"Friedrich Schiller University, Jena, Germany"}]},{"given":"David G.","family":"Andersen","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Michael","family":"Kaminsky","sequence":"additional","affiliation":[{"name":"BrdgAI, Pittsburgh, PA"}]},{"given":"Kimberly","family":"Keeton","sequence":"additional","affiliation":[{"name":"Hewlett Packard Labs, Palo Alto, CA"}]},{"given":"Andrew","family":"Pavlo","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]}],"member":"320","published-online":{"date-parts":[[2021,3,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Facebook MyRocks. http:\/\/myrocks.io\/. Facebook MyRocks. http:\/\/myrocks.io\/."},{"key":"e_1_2_1_2_1","unstructured":"Facebook RocksDB. http:\/\/rocksdb.org\/. Facebook RocksDB. http:\/\/rocksdb.org\/."},{"key":"e_1_2_1_3_1","unstructured":"Google LevelDB. https:\/\/github.com\/google\/leveldb. Google LevelDB. https:\/\/github.com\/google\/leveldb."},{"key":"e_1_2_1_4_1","unstructured":"RocksDB Tuning Guide. https:\/\/github.com\/facebook\/rocksdb\/wiki\/RocksDB-Tuning-Guide. RocksDB Tuning Guide. https:\/\/github.com\/facebook\/rocksdb\/wiki\/RocksDB-Tuning-Guide."},{"key":"e_1_2_1_5_1","unstructured":"The InfluxDB storage engine and the time-structured merge tree (TSM). https:\/\/docs.influxdata.com\/influxdb\/v1.0\/concepts\/storage_engine\/. The InfluxDB storage engine and the time-structured merge tree (TSM). https:\/\/docs.influxdata.com\/influxdb\/v1.0\/concepts\/storage_engine\/."},{"key":"e_1_2_1_6_1","volume-title":"https:\/\/github.com\/hillbig\/tx-trie","author":"Succinct Trie Implementation","year":"2010","unstructured":"tx-trie 0.18-- Succinct Trie Implementation . https:\/\/github.com\/hillbig\/tx-trie , 2010 . tx-trie 0.18--Succinct Trie Implementation. https:\/\/github.com\/hillbig\/tx-trie, 2010."},{"key":"e_1_2_1_7_1","first-page":"43","article-title":"Representing trees of higher degree","volume":"4","author":"Benoit D.","year":"2005","unstructured":"Benoit , D. , Demaine , E.D. , Munro , J.I. , Raman , R. , Raman , V. , Rao , S.S . Representing trees of higher degree . Algorithmica 4 , 43 ( 2005 ), 275--292. Benoit, D., Demaine, E.D., Munro, J.I., Raman, R., Raman, V., Rao, S.S. Representing trees of higher degree. Algorithmica 4, 43 (2005), 275--292.","journal-title":"Algorithmica"},{"key":"e_1_2_1_8_1","volume-title":"http:\/\/idlebox.net\/2007\/stx-btree\/","author":"Bingmann T.","year":"2008","unstructured":"Bingmann , T. STX B+tree C++ Template Classes . http:\/\/idlebox.net\/2007\/stx-btree\/ , 2008 . Bingmann, T. STX B+tree C++ Template Classes. http:\/\/idlebox.net\/2007\/stx-btree\/, 2008."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_10_1","volume-title":"Personal communication","author":"Dong S.","year":"2017","unstructured":"Dong , S. Personal communication , 2017 . 2017-08-28. Dong, S. Personal communication, 2017. 2017-08-28."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of CIDR'17","volume":"3","author":"Dong S.","year":"2017","unstructured":"Dong , S. , Callaghan , M. , Galanis , L. , Borthakur , D. , Savor , T. , Strum , M. Optimizing space amplification in RocksDB . In Proceedings of CIDR'17 , Volume 3 ( 2017 ), 3. Dong, S., Callaghan, M., Galanis, L., Borthakur, D., Savor, T., Strum, M. Optimizing space amplification in RocksDB. In Proceedings of CIDR'17, Volume 3 (2017), 3."},{"key":"e_1_2_1_12_1","first-page":"19","article-title":"Fast compressed tries through path decompositions","author":"Grossi R.","year":"2015","unstructured":"Grossi , R. , Ottaviano , G . Fast compressed tries through path decompositions . J. Exp. Algorithm. 3--4 , 19 ( 2015 ). Grossi, R., Ottaviano, G. Fast compressed tries through path decompositions. J. Exp. Algorithm. 3--4, 19 (2015).","journal-title":"J. Exp. Algorithm. 3--4"},{"key":"e_1_2_1_13_1","volume-title":"Foundations of Computer Science","author":"Jacobson G.","year":"1989","unstructured":"Jacobson , G. Space-efficient static trees and graphs . In Foundations of Computer Science ( 1989 ), IEEE , 549--554. Jacobson, G. Space-efficient static trees and graphs. In Foundations of Computer Science (1989), IEEE, 549--554."},{"key":"e_1_2_1_14_1","first-page":"44","article-title":"A decentralized structured storage system","volume":"2","author":"Lakshman A.","year":"2010","unstructured":"Lakshman , A. , Malik , P. Cassandra : A decentralized structured storage system . ACM SIGOPS Oper. Syst. Rev 2 , 44 ( 2010 ), 35--40. Lakshman, A., Malik, P. Cassandra: A decentralized structured storage system. ACM SIGOPS Oper. Syst. Rev 2, 44 (2010), 35--40.","journal-title":"ACM SIGOPS Oper. Syst. Rev"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_16_1","first-page":"33","article-title":"The log-structured merge-tree (LSM-tree)","volume":"4","author":"O'Neil P.","year":"1996","unstructured":"O'Neil , P. , Cheng , E. , Gawlick , D. , O'Neil , E . The log-structured merge-tree (LSM-tree) . Acta Inform. 4 , 33 ( 1996 ), 351--385. O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. The log-structured merge-tree (LSM-tree). Acta Inform. 4, 33 (1996), 351--385.","journal-title":"Acta Inform."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056102"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of SEA'13","author":"Zhou D.","year":"2013","unstructured":"Zhou , D. , Andersen , D.G. , Kaminsky , M. Space-efficient, highperformance rank and select structures on uncompressed bit sequences . In Proceedings of SEA'13 ( 2013 ), Springer, 151--163. Zhou, D., Andersen, D.G., Kaminsky, M. Space-efficient, highperformance rank and select structures on uncompressed bit sequences. In Proceedings of SEA'13 (2013), Springer, 151--163."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450262","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T22:39:57Z","timestamp":1672612797000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,22]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["10.1145\/3450262"],"URL":"https:\/\/doi.org\/10.1145\/3450262","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,22]]},"assertion":[{"value":"2021-03-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}