{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:45:52Z","timestamp":1776969952272,"version":"3.51.4"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2026,4,23]]},"abstract":"<jats:p>Range filters are compact data structures that answer approximate range emptiness queries. They are used in many domains, e.g., in key-value stores, to quickly rule out the existence of keys in a given query range and avoid having to search for them in storage. However, all existing range filters exhibit at least one of the following shortcomings: (1) they do not provide robust false positive rate and performance guarantees, (2) they do not support variable-length keys and query ranges, and (3) they do not allow dynamic operations such as insertions, deletions, or expansions.<\/jats:p>\n                  <jats:p>We introduce Diva, the first range filter to address all the above challenges simultaneously. Diva learns the dataset's distribution by sampling keys and storing them in a cacheefficient trie. It compresses the keys in-between samples by removing their longest common prefix and truncating their suffixes while leaving enough bits in the middle (i.e., an infix) to allow differentiating between the keys in the sorted order. It stores infixes in constant-time dynamic data blocks, which it stretches and eventually splits to handle insertions and expansions. It processes a range query by traversing the trie and checking for the inclusion of at least one infix in the target query range.<\/jats:p>\n                  <jats:p>Diva is the culmination of several years of research on filters from Orca Lab at the University of Toronto, in collaboration with KTH and Copenhagen University. This paper describes how Diva builds on this body of work, and how it addresses the limitations of prior art.<\/jats:p>","DOI":"10.1145\/3810900.3810910","type":"journal-article","created":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:16:38Z","timestamp":1776968198000},"page":"51-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic Range Filtering Beyond Worst-Case Bounds"],"prefix":"10.1145","volume":"55","author":[{"given":"Navid","family":"Eslami","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioana O.","family":"Bercea","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niv","family":"Dayan","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556556"},{"key":"e_1_2_1_2_1","volume-title":"Apache cassandra","year":"2024","unstructured":"Apache. Apache cassandra, 2024."},{"key":"e_1_2_1_3_1","volume-title":"Apache druid","year":"2024","unstructured":"Apache. Apache druid, 2024."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301323"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1822"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_7_1","first-page":"1","volume-title":"19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Bercea I. O.","year":"2024","unstructured":"I. O. Bercea, J. B. T. Houen, and R. Pagh. Daisy bloom filters. In H. L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1-9:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl - Leibniz-Zentrum f\u00a8ur Informatik."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_9_1","first-page":"11","article-title":"Survey: Network applications of bloom filters: A survey","volume":"1","author":"Broder A.","year":"2003","unstructured":"A. Broder and M. Mitzenmacher. Survey: Network applications of bloom filters: A survey. Internet Mathematics, 1, 11 2003.","journal-title":"Internet Mathematics"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659447"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3786621"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_2_1_14_1","unstructured":"G. Cloud. Bigquery enterprise data warehouse 2024."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC\u201920","author":"Conway A.","year":"2020","unstructured":"A. Conway, A. Gupta, V. Chidambaran, M. Farach-Colton, R. Spillane, A. Tai, and R. Johnson. Splinterdb: closing the bandwidth gap for nvme key-value stores. In Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC\u201920, USA, 2020. USENIX Association."},{"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":"crossref","unstructured":"M. Costa P. Ferragina and G. Vinciguerra. Grafite: Taming adversarial queries with optimal range filters. volume 2 of SIGMOD \u201924 page 1-23 New York NY USA Mar. 2024. Association for Computing Machinery.","DOI":"10.1145\/3639258"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682027"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589285"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457273"},{"key":"e_1_2_1_22_1","volume-title":"Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications. ACM Trans. Storage, 17(4), oct","author":"Dong S.","year":"2021","unstructured":"S. Dong, A. Kryczka, Y. Jin, and M. Stumm. Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications. ACM Trans. Storage, 17(4), oct 2021."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3749646.3749664"},{"key":"e_1_2_1_25_1","first-page":"1","volume-title":"Proceedings of the 2025 International Conference on Management of Data, SIGMOD \u201925","author":"Eslami N.","year":"2025","unstructured":"N. Eslami and N. Dayan. Memento filter: A fast, dynamic, and robust range filter. In Proceedings of the 2025 International Conference on Management of Data, SIGMOD \u201925, page 1-27, New York, NY, USA, 2025. Association for Computing Machinery."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-024-00873-w"},{"key":"e_1_2_1_28_1","volume-title":"Computation Structures Group Memo","author":"Fano R.","year":"1971","unstructured":"R. Fano. On the Number of Bits Required to Implement an Associative Memory. Computation Structures Group Memo. MIT Project MAC Computer Structures Group, 1971."},{"key":"e_1_2_1_29_1","volume-title":"Mariadb server: The innovative open source database","author":"Foundation M.","year":"2024","unstructured":"M. Foundation. Mariadb server: The innovative open source database, 2024."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722181"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_32_1","volume-title":"To Appear","author":"Kim H. M.","year":"2026","unstructured":"H. M. Kim, N. Eslami, and N. Dayan. Zeno filter: To infinity in tiny steps. To Appear, 2026."},{"key":"e_1_2_1_33_1","volume-title":"NeurIPS Workshop on Machine Learning for Systems","author":"Kipf A.","year":"2019","unstructured":"A. Kipf, R. Marcus, A. van Renen, M. Stoian, A. Kemper, T. Kraska, and T. Neumann. Sosd: A benchmark for learned indexes. NeurIPS Workshop on Machine Learning for Systems, 2019."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526167"},{"key":"e_1_2_1_35_1","volume-title":"Sorting And Searching","author":"Knuth D.","year":"1973","unstructured":"D. Knuth. The Art Of Computer Programming, vol. 3: Sorting And Searching. Addison-Wesley, 1973."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3339504"},{"key":"e_1_2_1_40_1","volume-title":"Wiredtiger storage engine","author":"DB.","year":"2024","unstructured":"MongoDB. Wiredtiger storage engine, 2024."},{"key":"e_1_2_1_41_1","volume-title":"bloomrf: On performing range-queries in bloom-filters with piecewise-monotone hash functions and prefix hashing","author":"M\u00a8o\u00dfner B.","year":"2022","unstructured":"B. M\u00a8o\u00dfner, C. Riegger, A. Bernhardt, and I. Petrov. bloomrf: On performing range-queries in bloom-filters with piecewise-monotone hash functions and prefix hashing, 2022."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_10"},{"key":"e_1_2_1_44_1","volume-title":"How to approximate a set without knowing its size in advance","author":"Pagh R.","year":"2013","unstructured":"R. Pagh, G. Segev, and U. Wieder. How to approximate a set without knowing its size in advance, 2013."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1145\/3035918.3035963","volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD '17","author":"Pandey P.","year":"2017","unstructured":"P. Pandey, M. A. Bender, R. Johnson, and R. Patro. A general-purpose counting filter: Making every bit count. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD '17, page 775-787, New York, NY, USA, 2017. Association for Computing Machinery."},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"1386","DOI":"10.1145\/3448016.3452841","volume-title":"Proceedings of the 2021 International Conference on Management of Data, SIGMOD \u201921","author":"Pandey P.","year":"2021","unstructured":"P. Pandey, A. Conway, J. Durie, M. A. Bender, M. Farach-Colton, and R. Johnson. Vector quotient filters: Overcoming the time\/space trade-off in filter design. In Proceedings of the 2021 International Conference on Management of Data, SIGMOD \u201921, page 1386-1399, New York, NY, USA, 2021. Association for Computing Machinery."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3654681"},{"key":"e_1_2_1_48_1","volume-title":"6th International Workshop, WEA 2007","volume":"4525","author":"Putze F.","year":"2007","unstructured":"F. Putze, P. Sanders, and J. Singler. Cache-, hashand space-efficient bloom filters. In Experimental Algorithms, 6th International Workshop, WEA 2007, volume 4525 of Lecture Notes in Computer Science, pages 108-121. Springer, 2007."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/560733"},{"issue":"1","key":"e_1_2_1_50_1","doi-asserted-by":"crossref","first-page":"526","DOI":"10.14778\/1453856.1453914","article-title":"Rose: compressed, log-structured replication","volume":"1","author":"Sears R.","year":"2008","unstructured":"R. Sears, M. Callaghan, and E. Brewer. Rose: compressed, log-structured replication. Proc. VLDB Endow., 1(1):526-537, aug 2008.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_51_1","volume-title":"The snowflake ai data cloud","year":"2024","unstructured":"Snowflake. The snowflake ai data cloud, 2024."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529347"},{"key":"e_1_2_1_53_1","volume-title":"Don\u2019t forget range delete! enhancing lsm-based key-value stores with more compatible lookups and deletes","author":"Wang F.","year":"2025","unstructured":"F. Wang, D. Mo, and S. Luo. Don\u2019t forget range delete! enhancing lsm-based key-value stores with more compatible lookups and deletes, 2025."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00158"},{"key":"e_1_2_1_55_1","volume-title":"Proc. ACM Manag. Data, 2(4)","author":"Wen R.","year":"2024","unstructured":"R. Wen, H. McCoy, D. Tench, G. Tagliavini, M. A. Bender, A. Conway, M. Farach-Colton, R. Johnson, and P. Pandey. Adaptive quotient filters. Proc. ACM Manag. Data, 2(4), Sept. 2024."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303955"},{"key":"e_1_2_1_58_1","volume-title":"May","author":"Yohe J. M.","year":"1972","unstructured":"J. M. Yohe. Algorithm 428: Hu-tucker minimum redundancy alphabetic coding method [z]. Commun. ACM, 15(5):360-362, May 1972."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3810900.3810910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T18:17:05Z","timestamp":1776968225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3810900.3810910"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,23]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,23]]}},"alternative-id":["10.1145\/3810900.3810910"],"URL":"https:\/\/doi.org\/10.1145\/3810900.3810910","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2026,4,23]]},"assertion":[{"value":"2026-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}