{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:36Z","timestamp":1779174876960,"version":"3.51.4"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"NSF &#x28;National Science Foundation&#x29;","award":["2517201"],"award-info":[{"award-number":["2517201"]}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["RGPIN-2023-03580"],"award-info":[{"award-number":["RGPIN-2023-03580"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>Range filters are probabilistic data structures used to efficiently perform range emptiness queries, with applications in databases, big data analytics, and key-value stores. Modern range filters are compact and can guarantee a bounded false positive rate irrespective of the spatial skew in queries. However, existing range filters are still susceptible to temporal skew: in skewed workloads where a few queries are repeated disproportionately more often, the false positive rate of a range filter may be unbounded.<\/jats:p>\n                  <jats:p>We introduce the Aeris filter, an adaptive expandable range filter that guarantees a robust false positive rate irrespective of spatial or temporal skew. The Aeris filter achieves this by dynamically resolving and adapting to false positives. More specifically, the Aeris filter is monotonic adaptive, i.e., it never forgets a previously encountered false positive. The Aeris filter introduces a novel encoding scheme to implement adaptivity in a range filter with no additional space or operational overhead. Furthermore, the Aeris filter deamortizes the I\/O cost to expand monotonic adaptive filters by utilizing on-disk adaptivity structures, resulting in fewer system disruptions.<\/jats:p>\n                  <jats:p>Experimental results demonstrate that the Aeris filter achieves up to a 10\u00d7 reduction in false positive rates on skewed query distributions compared to other non-adaptive range filters. When integrated into a database, the Aeris filter delivers 1.5-8\u00d7 higher throughput for adversarial workloads, and is able to deliver this high throughput using a cache of smaller size. The Aeris filter also reduces expansion overhead by up to 3\u00d7 compared to the Memento filter, a spatially-robust expandable range filter. These improvements ensure scalable, efficient, and adaptive range query handling in dynamic environments.<\/jats:p>","DOI":"10.1145\/3786621","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["Aeris Filter: A Strongly and Monotonically Adaptive Range Filter"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8573-4299","authenticated-orcid":false,"given":"Yuvaraj","family":"Chesetti","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3522-5846","authenticated-orcid":false,"given":"Navid","family":"Eslami","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4821-1558","authenticated-orcid":false,"given":"Huanchen","family":"Zhang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0314-0167","authenticated-orcid":false,"given":"Niv","family":"Dayan","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5576-0320","authenticated-orcid":false,"given":"Prashant","family":"Pandey","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"6","article-title":"Review of Variants of Bloom Filters for Detection of Malicious URL","volume":"1","author":"Atti Mangadevi","year":"2024","unstructured":"Mangadevi Atti and Manas Kumar Yogi. 2024. Review of Variants of Bloom Filters for Detection of Malicious URL. Journal of Intelligent Decision Technologies and Applications 1, 1 (2024), 6--12.","journal-title":"Journal of Intelligent Decision Technologies and Applications"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976489.2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/WFCS.2017.7991963"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644201"},{"key":"e_1_2_1_8_1","unstructured":"Alex Carluccio. 2023. Anonymous People Flow Monitoring System Leveraging Bloom Filters. Ph. D. Dissertation. Politecnico di Torino."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659447"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3445967"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588726"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2020 USENIX Annual Technical Conference, USENIX ATC 2020, July 15--17","author":"Conway Alexander","year":"2020","unstructured":"Alexander Conway, Abhishek Gupta, Vijay Chidambaram, Martin Farach-Colton, Richard P. Spillane, Amy Tai, and Rob Johnson. 2020. SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. In Proceedings of the 2020 USENIX Annual Technical Conference, USENIX ATC 2020, July 15--17, 2020, Ada Gavrilovska and Erez Zadok (Eds.). USENIX Association, 49--63. https:\/\/www.usenix.org\/conference\/atc20\/presentation\/conway"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639258"},{"key":"e_1_2_1_15_1","unstructured":"Transaction Processing Performance Council. 2011. TPC Benchmarks. http:\/\/www.tpc.org\/information\/benchmarks.asp."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589285"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3682027"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642-02652--2_6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2833312.2833449"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3749646.3749664"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698820"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-024-00873-w"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3077136.3080789"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.52"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2001.914838"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526167"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3320233"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--83508--8_40"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4896"},{"key":"e_1_2_1_32_1","unstructured":"Cockroach Labs. 2015. https:\/\/github.com\/cockroachdb\/cockroach"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2021.60"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JNCA.2013.05.009"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3339504"},{"key":"e_1_2_1_37_1","unstructured":"MongoDB. [n.d.]. WiredTiger. https:\/\/github.com\/wiredtiger\/wiredtiger."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.48786\/EDBT.2023.11"},{"key":"e_1_2_1_39_1","unstructured":"Pat O'Neil Betty O'Neil and Xuedong Chen. 2007. The Star Schema Benchmark. http:\/\/www.cs.umb.edu\/~poneil\/StarSchemaB.PDF."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070548"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380598"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2023.3302306"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2024.3371793"},{"key":"e_1_2_1_45_1","volume-title":"Last Accessed","author":"DB","year":"2025","unstructured":"RocksDB 2013. https:\/\/rocksdb.org\/, Last Accessed Sept. 7, 2025."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453914"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529347"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677128"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611502"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3347146.3359077"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T19:29:51Z","timestamp":1775676591000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786621"],"URL":"https:\/\/doi.org\/10.1145\/3786621","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}