{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T06:06:41Z","timestamp":1759730801766,"version":"3.41.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"crossref","award":["CCF-1535821"],"award-info":[{"award-number":["CCF-1535821"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Intel Science and Technology Center for Visual Cloud Systems"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>\n            We present the\n            <jats:italic>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: open-range queries, closed-range queries, and range counts. SuRF is based on a new data structure called the\n            <jats:italic>Fast Succinct Trie (FST)<\/jats:italic>\n            that matches the point and range query performance of state-of-the-art order-preserving indexes, while consuming only 10\u00a0bits 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\u2019s 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.\n          <\/jats:p>","DOI":"10.1145\/3375660","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T02:39:04Z","timestamp":1592793544000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Succinct Range Filters"],"prefix":"10.1145","volume":"45","author":[{"given":"Huanchen","family":"Zhang","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Forbes Ave, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hyeontaek","family":"Lim","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Forbes Ave, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viktor","family":"Leis","sequence":"additional","affiliation":[{"name":"Friedrich Schiller University Jena, F\u00fcrstengraben, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David G.","family":"Andersen","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Forbes Ave, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kaminsky","sequence":"additional","affiliation":[{"name":"BrdgAI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kimberly","family":"Keeton","sequence":"additional","affiliation":[{"name":"Hewlett Packard Labs, America Center Dr., San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Pavlo","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Forbes Ave, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2010. tx-trie 0.18\u2014Succinct Trie Implementation. Retrieved from https:\/\/github.com\/hillbig\/tx-trie.  2010. tx-trie 0.18\u2014Succinct Trie Implementation. Retrieved from https:\/\/github.com\/hillbig\/tx-trie."},{"key":"e_1_2_1_2_1","unstructured":"2013. Squid Web Proxy Cache. Retrieved from http:\/\/www.squid-cache.org\/.  2013. Squid Web Proxy Cache. Retrieved from http:\/\/www.squid-cache.org\/."},{"key":"e_1_2_1_3_1","unstructured":"2014. Google LevelDB. Retrieved from https:\/\/github.com\/google\/leveldb.  2014. Google LevelDB. Retrieved from https:\/\/github.com\/google\/leveldb."},{"key":"e_1_2_1_4_1","unstructured":"2015. Apache HBase. Retrieved from https:\/\/hbase.apache.org\/.  2015. Apache HBase. Retrieved from https:\/\/hbase.apache.org\/."},{"key":"e_1_2_1_5_1","unstructured":"2015. Facebook MyRocks. Retrieved from http:\/\/myrocks.io\/.  2015. Facebook MyRocks. Retrieved from http:\/\/myrocks.io\/."},{"key":"e_1_2_1_6_1","unstructured":"2015. Facebook RocksDB. Retrieved from http:\/\/rocksdb.org\/.  2015. Facebook RocksDB. Retrieved from http:\/\/rocksdb.org\/."},{"key":"e_1_2_1_7_1","unstructured":"2015. KairosDB. Retrieved from https:\/\/kairosdb.github.io\/.  2015. KairosDB. Retrieved from https:\/\/kairosdb.github.io\/."},{"key":"e_1_2_1_8_1","unstructured":"2015. QuasarDB. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Quasardb.  2015. QuasarDB. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Quasardb."},{"key":"e_1_2_1_9_1","unstructured":"2016. ARF Implementation. Retrieved from https:\/\/github.com\/carolinux\/adaptive_range_filters.  2016. ARF Implementation. Retrieved from https:\/\/github.com\/carolinux\/adaptive_range_filters."},{"key":"e_1_2_1_10_1","unstructured":"2016. Succinct Data Structures. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Succinct_data_structure.  2016. Succinct Data Structures. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Succinct_data_structure."},{"key":"e_1_2_1_11_1","unstructured":"2017. The InfluxDB Storage Engine and the Time-Structured Merge Tree (TSM). Retrieved from https:\/\/docs.influxdata.com\/influxdb\/v1.0\/concepts\/storage_engine\/.  2017. The InfluxDB Storage Engine and the Time-Structured Merge Tree (TSM). Retrieved from https:\/\/docs.influxdata.com\/influxdb\/v1.0\/concepts\/storage_engine\/."},{"volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201915)","year":"2015","author":"Agarwal Rachit","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556556"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972900.9"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Extended Database Technology Conference (EDBT\u201916)","volume":"2016","author":"Athanassoulis Manos","year":"2016"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118737.3118845"},{"key":"e_1_2_1_18_1","unstructured":"Timo Bingmann. 2008. STX B+ Tree C++ Template Classes. Retrieved from http:\/\/idlebox.net\/2007\/stx-btree\/.  Timo Bingmann. 2008. STX B+ Tree C++ Template Classes. Retrieved from http:\/\/idlebox.net\/2007\/stx-btree\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196896"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_61"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213884"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463710"},{"volume-title":"August 28, 2017).","year":"2017","author":"Dong Siying","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201917)","volume":"3","author":"Dong Siying","year":"2017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732967.2732968"},{"key":"e_1_2_1_30_1","unstructured":"Facebook. 2015. RocksDB Tuning Guide. Retrieved from https:\/\/github.com\/facebook\/rocksdb\/wiki\/RocksDB-Tuning-Guide.  Facebook. 2015. RocksDB Tuning Guide. Retrieved from https:\/\/github.com\/facebook\/rocksdb\/wiki\/RocksDB-Tuning-Guide."},{"volume-title":"Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. ACM, 75--88","author":"Fan Bin","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"volume-title":"A simple optimal representation for balanced parentheses. Theor. Comput. Sci. 368, 3","year":"2006","author":"Geary Richard F.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741973"},{"volume-title":"Proceedings of the International Conference on Experimental Algorithms (WEA\u201905)","year":"2005","author":"Gonz\u00e1lez Rodrigo","key":"e_1_2_1_35_1"},{"volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 769--775","year":"2014","author":"Goswami Mayank","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_3"},{"volume-title":"Article 1.8 (October","year":"2014","author":"Grossi Roberto","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"volume-title":"Foundations of Computer Science","author":"Jacobson Guy","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_20"},{"volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201916)","year":"2016","author":"Khandelwal Anurag","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_45_1","first-page":"28","article-title":"Balanced parentheses strike back","volume":"4","author":"Lu I.","year":"2008","journal-title":"Trans. Algor."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.08.008"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1151"},{"volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201904)","author":"Ian Munro J.","key":"e_1_2_1_49_1"},{"volume-title":"Compact Data Structures: A Practical Approach","author":"Navarro Gonzalo","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30850-5_26"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_9"},{"volume-title":"Proceedings of the International Conference on Experimental Algorithms (WEA\u201906)","year":"2006","author":"Rahman Naila","key":"e_1_2_1_54_1"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"volume-title":"Space-efficient Data Structures, Streams, and Algorithms","author":"Raman Rajeev","key":"e_1_2_1_56_1"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056102"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.13"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090191.1080114"},{"key":"e_1_2_1_61_1","unstructured":"The Apache Software Foundation. 2015. Apache Cassandra. Retrieved from https:\/\/cassandra.apache.org\/.  The Apache Software Foundation. 2015. Apache Cassandra. Retrieved from https:\/\/cassandra.apache.org\/."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788888.1788900"},{"volume-title":"Proceedings of the 2018 International Conference on Management of Data. ACM, 473--488","author":"Wang Ziqi","key":"e_1_2_1_63_1"},{"key":"e_1_2_1_64_1","unstructured":"WiredTiger. 2014. WiredTiger. Retrieved from http:\/\/www.wiredtiger.com\/.  WiredTiger. 2014. WiredTiger. Retrieved from http:\/\/www.wiredtiger.com\/."},{"volume-title":"Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conference. USENIX Association, 71--82","year":"2015","author":"Wu Xingbo","key":"e_1_2_1_65_1"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1658939.1658975"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915222"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_15"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375660","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375660","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:15Z","timestamp":1750199895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375660"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":69,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3375660"],"URL":"https:\/\/doi.org\/10.1145\/3375660","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2020,6,21]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}