{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T06:27:00Z","timestamp":1778048820395,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"crossref","award":["PRIN-2017WR7SHH"],"award-info":[{"award-number":["PRIN-2017WR7SHH"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["871042"],"award-info":[{"award-number":["871042"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union ? NextGenerationEU ? PNRR","award":["IR0000013"],"award-info":[{"award-number":["IR0000013"]}]},{"name":"European Union ? NextGenerationEU ? PNRR","award":["CN00000013"],"award-info":[{"award-number":["CN00000013"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Range filters allow checking whether a query range intersects a given set of keys with a chance of returning a false positive answer, thus generalising the functionality of Bloom filters from point to range queries. Existing practical range filters have addressed this problem heuristically, resulting in high false positive rates and query times when dealing with adversarial inputs, such as in the common scenario where queries are correlated with the keys.<\/jats:p>\n          <jats:p>We introduce Grafite, a novel range filter that solves these issues with a simple design and clear theoretical guarantees that hold regardless of the input data and query distribution: given a fixed space budget of B bits per key, the query time is O(1), and the false positive probability is upper bounded by l\/2B-2, where l is the query range size. Our experimental evaluation shows that Grafite is the only range filter to date to achieve robust and predictable false positive rates across all combinations of datasets, query workloads, and range sizes, while providing faster queries and construction times, and dominating all competitors in the case of correlated queries.<\/jats:p>\n          <jats:p>As a further contribution, we introduce a very simple heuristic range filter whose performance on uncorrelated queries is very close to or better than the one achieved by the best heuristic range filters proposed in the literature so far.<\/jats:p>","DOI":"10.1145\/3639258","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-23","source":"Crossref","is-referenced-by-count":9,"title":["Grafite: Taming Adversarial Queries with Optimal Range Filters"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-8397-7580","authenticated-orcid":false,"given":"Marco","family":"Costa","sequence":"first","affiliation":[{"name":"University of Pisa, Pisa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1353-360X","authenticated-orcid":false,"given":"Paolo","family":"Ferragina","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0328-7791","authenticated-orcid":false,"given":"Giorgio","family":"Vinciguerra","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556556"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380842"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3505286"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_37"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_2_6_1","volume-title":"Network Applications of Bloom Filters: A Survey. Internet mathematics","author":"Broder Andrei","year":"2004","unstructured":"Andrei Broder and Michael Mitzenmacher. 2004. Network Applications of Bloom Filters: A Survey. Internet mathematics, Vol. 1, 4 (2004), 485--509."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3445967"},{"key":"e_1_2_2_8_1","volume-title":"Compact Pat Trees. Ph.,D. Dissertation","author":"Clark David Richard","unstructured":"David Richard Clark. 1996. Compact Pat Trees. Ph.,D. Dissertation. University of Waterloo, Canada."},{"key":"e_1_2_2_9_1","volume-title":"Introduction to Algorithms 4 ed.)","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2022. Introduction to Algorithms 4 ed.). The MIT Press."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276980"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589285"},{"key":"e_1_2_2_12_1","volume-title":"Proc. ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM). 201--212","author":"Dharmapurikar Sarang","unstructured":"Sarang Dharmapurikar, Praveen Krishnamurthy, and David E. Taylor. 2003. Longest Prefix Matching Using Bloom Filters. In Proc. ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM). 201--212."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SEA.2022.4"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_2_16_1","volume-title":"On the Number of Bits Required to Implement an Associative Memory","author":"Fano Robert Mario","unstructured":"Robert Mario Fano. 1971. On the Number of Bits Required to Implement an Associative Memory. Massachusetts Institute of Technology, Project MAC."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3077136.3080789"},{"key":"e_1_2_2_18_1","volume-title":"Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 769--775","author":"Goswami Mayank","year":"2014","unstructured":"Mayank Goswami, Allan Gr\u00f8nlund, Kasper Green Larsen, and Rasmus Pagh. 2014. Approximate Range Emptiness in Constant Time and Optimal Space. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 769--775."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376122"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526167"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517867"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20643-6_19"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2018.2889329"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415546"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.48786\/edbt.2023.11"},{"key":"e_1_2_2_28_1","volume-title":"Compact data structures: a practical approach","author":"Navarro Gonzalo","unstructured":"Gonzalo Navarro. 2016. Compact data structures: a practical approach. Cambridge University Press."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409371"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.6"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609615"},{"key":"e_1_2_2_32_1","volume-title":"Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 823--829","author":"Pagh Anna","unstructured":"Anna Pagh, Rasmus Pagh, and S. Srinivasa Rao. 2005. An Optimal Bloom Filter Replacement. In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 823--829."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CPM.2017.30"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03351-3_25"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529347"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433409"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00158"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90033--7"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375660"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450262"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639258","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:18:10Z","timestamp":1755789490000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639258"],"URL":"https:\/\/doi.org\/10.1145\/3639258","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}