{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:38Z","timestamp":1750220918665,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T00:00:00Z","timestamp":1572912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2019,11,5]]},"abstract":"<jats:p>We present the Succinct Range Filter (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. SuRF is based on a new data structure called the Fast Succinct Trie (FST) that matches the point and range query performance of state-of-the-art order-preserving indexes, while consuming only 10 bits per trie node. The false positive rates in SuRF for both point and range queries are tunable to satisfy different application needs. We evaluate SuRF in RocksDB as a replacement for its Bloom filters to reduce I\/O by filtering requests before they access on-disk data structures. Our experiments on a 100 GB dataset show that replacing RocksDB's Bloom filters with SuRFs speeds up open-seek (without upper-bound) and closed-seek (with upper-bound) queries by up to 1.5\u00d7 and 5\u00d7 with a modest cost on the worst-case (all-missing) point query throughput due to slightly higher false positive rate.<\/jats:p>","DOI":"10.1145\/3371316.3371335","type":"journal-article","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T18:56:07Z","timestamp":1572980167000},"page":"78-85","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Succinct Range Filters"],"prefix":"10.1145","volume":"48","author":[{"given":"Huanchen","family":"Zhang","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hyeontaek","family":"Lim","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viktor","family":"Leis","sequence":"additional","affiliation":[{"name":"Friedrich Schiller University Jena, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David G.","family":"Andersen","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kimberly","family":"Keeton","sequence":"additional","affiliation":[{"name":"Hewlett Packard Labs, Palo Alto, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Pavlo","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,5]]},"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":"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_5_1","unstructured":"Kairosdb. https:\/\/kairosdb.github.io\/.  Kairosdb. https:\/\/kairosdb.github.io\/."},{"key":"e_1_2_1_6_1","unstructured":"Quasardb. https:\/\/en.wikipedia.org\/wiki\/Quasardb.  Quasardb. https:\/\/en.wikipedia.org\/wiki\/Quasardb."},{"key":"e_1_2_1_7_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_8_1","unstructured":"Squid Web Proxy Cache. http:\/\/www.squid-cache.org\/.  Squid Web Proxy Cache. http:\/\/www.squid-cache.org\/."},{"key":"e_1_2_1_9_1","unstructured":"Succinct data structures. https:\/\/en.wikipedia.org\/ wiki\/Succinct_data_structure.  Succinct data structures. https:\/\/en.wikipedia.org\/ wiki\/Succinct_data_structure."},{"volume-title":"https:\/\/github. com\/hillbig\/tx-trie","year":"2010","key":"e_1_2_1_10_1","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_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556556"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972900.9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118737.3118845"},{"key":"e_1_2_1_14_1","unstructured":"T. Bingmann. Stx b+ tree c++ template classes. http:\/\/idlebox. net\/2007\/stx-btree\/ 2008.  T. Bingmann. Stx b+ tree c++ template classes. http:\/\/idlebox. net\/2007\/stx-btree\/ 2008."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_61"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463710"},{"key":"e_1_2_1_19_1","unstructured":"S. Dong. personal communication 2017. 2017-08--28.  S. Dong. personal communication 2017. 2017-08--28."},{"key":"e_1_2_1_20_1","first-page":"3","volume-title":"CIDR","volume":"3","author":"Dong S.","year":"2017","unstructured":"S. Dong , M. Callaghan , L. Galanis , D. Borthakur , T. Savor , and M. Strum . Optimizing space amplification in rocksdb . In CIDR , volume 3 , page 3 , 2017 . S. Dong, M. Callaghan, L. Galanis, D. Borthakur, T. Savor, and M. Strum. Optimizing space amplification in rocksdb. In CIDR, volume 3, page 3, 2017."},{"key":"e_1_2_1_21_1","volume-title":"Summary cache: a scalable wide-area web cache sharing protocol","author":"Fan L.","year":"2000","unstructured":"L. Fan , P. Cao , J. Almeida , and A. Z. Broder . Summary cache: a scalable wide-area web cache sharing protocol . IEEE\/ACM Transactions on Networking (TON) , 8(3):281--293, 2000 . L. Fan, P. Cao, J. Almeida, and A. Z. Broder. Summary cache: a scalable wide-area web cache sharing protocol. IEEE\/ACM Transactions on Networking (TON), 8(3):281--293, 2000."},{"key":"e_1_2_1_22_1","first-page":"27","volume-title":"Proceedings of WEA'05","author":"Gonz\u00e1lez R.","year":"2005","unstructured":"R. Gonz\u00e1lez , S. Grabowski , V. M\u00e4kinen , and G. Navarro . Practical implementation of rank and select queries . In Proceedings of WEA'05 , pages 27 -- 38 , 2005 . R. Gonz\u00e1lez, S. Grabowski, V. M\u00e4kinen, and G. Navarro. Practical implementation of rank and select queries. In Proceedings of WEA'05, pages 27--38, 2005."},{"key":"e_1_2_1_23_1","volume-title":"Fast compressed tries through path decompositions. Journal of Experimental Algorithmics (JEA), 19:3--4","author":"Grossi R.","year":"2015","unstructured":"R. Grossi and G. Ottaviano . Fast compressed tries through path decompositions. Journal of Experimental Algorithmics (JEA), 19:3--4 , 2015 . R. Grossi and G. Ottaviano. Fast compressed tries through path decompositions. Journal of Experimental Algorithmics (JEA), 19:3--4, 2015."},{"key":"e_1_2_1_24_1","first-page":"549","volume-title":"Foundations of Computer Science","author":"Jacobson G.","year":"1989","unstructured":"G. Jacobson . Space-efficient static trees and graphs . In Foundations of Computer Science , pages 549 -- 554 . IEEE, 1989 . G. Jacobson. Space-efficient static trees and graphs. In Foundations of Computer Science, pages 549--554. IEEE, 1989."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.08.008"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_26"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_9"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056102"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.13"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090191.1080114"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_12"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1658939.1658975"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_40_1","first-page":"151","volume-title":"Proceedings of SEA '13","author":"Zhou D.","year":"2013","unstructured":"D. Zhou , D. G. Andersen , and M. Kaminsky . Space-efficient, highperformance rank and select structures on uncompressed bit sequences . In Proceedings of SEA '13 , pages 151 -- 163 . Springer , 2013 . D. Zhou, D. G. Andersen, and M. Kaminsky. Space-efficient, highperformance rank and select structures on uncompressed bit sequences. In Proceedings of SEA '13, pages 151--163. Springer, 2013."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371335","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371316.3371335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:05Z","timestamp":1750204385000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,5]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,11,5]]}},"alternative-id":["10.1145\/3371316.3371335"],"URL":"https:\/\/doi.org\/10.1145\/3371316.3371335","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2019,11,5]]},"assertion":[{"value":"2019-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}