{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:07:38Z","timestamp":1779131258419,"version":"3.51.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T00:00:00Z","timestamp":1779062400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2517201"],"award-info":[{"award-number":["2517201"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["2513656"],"award-info":[{"award-number":["2513656"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>Adaptive filters, unlike traditional filters, update their representation upon detecting a false positive to avoid repeating the same error in the future. Adaptive filters require an auxiliary structure, typically much larger than the main filter and often residing on slow storage, to facilitate adaptation. Each adaptation requires a disk I\/O, creating overhead that must be amortized across repeated false positives. On highly skewed or adversarial workloads, this overhead is well amortized over repeated false positives. However, on uniform random work- loads, adaptive filters experience noticeable performance degradation as false positives do not repeat often, making adaptivity an unnecessary overhead.<\/jats:p>\n                  <jats:p>In this paper, we address this fundamental limitation in adaptive filters by establishing a connection to the online ski rental problem, a classic online decision problem where one must repeatedly choose between renting or buying skis without knowing future usage. We demonstrate that adapting a false positive is equivalent to ''buying'', while accepting the false positive without adaptation corresponds to ''renting''. Using the online model, we theoretically analyze the cost of adaptivity and develop an adaptivity strategy to determine when to adapt a false positive to avoid unnecessary overheads.<\/jats:p>\n                  <jats:p>We introduce the SkiQF, an online adaptive filter that provides robust false positive rate guarantees through adaptivity while maintaining consistent, high performance across diverse query distributions. The SkiQF makes no assumptions about the query distribution and is 2-competitive, i.e., its total I\/O never exceeds twice the optimal for any workload. In a database system using a filter to avoid unnecessary disk accesses, the SkiQF achieves up to 1.78\u00d7higher throughput compared to the AdaptiveQF. Compared to traditional filters, the SkiQF achieves up to 1.45\u00d7higher throughput on skewed workloads and up to 10\u00d7higher throughput on adversarial workloads, demonstrating robustness and resilience. We also introduce the HybridSkiQF, a variant that detects the underlying query distribution and chooses an adaptivity strategy to minimize I\/O. Additionally, it dynamically adjusts its strategy in response to distribution drift. When it detects repeating false positives, the HybridSkiQF switches to immediate adaptation, like a standard adaptive filter, avoiding the overhead of the SkiQF's delayed adaptivity when immediate adaptation is optimal. The HybridSkiQF achieves up to 1.28\u00d7 and 1.79\u00d7higher throughput than the SkiQF and traditional filter respectively.<\/jats:p>","DOI":"10.1145\/3802121","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["To Adapt or Not to Adapt, That is the Ski Question"],"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\/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,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526121"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_2_1_4_1","volume-title":"3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage'11","author":"Bender Michael A.","year":"2011","unstructured":"Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, and Erez Zadok. 2011. Don't Thrash: How to Cache Your Hash on Flash. In 3rd USENIX Workshop on Hot Topics in Storage and File Systems, HotStorage'11, Portland, OR, USA, June 14, 2011, Irfan Ahmad (Ed.). USENIX Association. https:\/\/www.usenix.org\/conference\/hotstorage11\/dont-thrash-how-cache-your-hash-flash"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_6_1","volume-title":"Eduardo PC Rocha, Gil McVean, and Zamin Iqbal.","author":"Bradley Phelim","year":"2019","unstructured":"Phelim Bradley, Henk C Den Bakker, Eduardo PC Rocha, Gil McVean, and Zamin Iqbal. 2019. Ultrafast search of all deposited bacterial and viral genomic data. Nature biotechnology 37, 2 (2019), 152--159."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_8_1","volume-title":"18th USENIX Conference on File and Storage Technologies, FAST 2020","author":"Cao Zhichao","year":"2020","unstructured":"Zhichao Cao, Siying Dong, Sagar Vemuri, and David H. C. Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-ValueWorkloads at Facebook. In 18th USENIX Conference on File and Storage Technologies, FAST 2020, Santa Clara, CA, USA, February 24--27, 2020, Sam H. Noh and Brent Welch (Eds.). USENIX Association, 209--223. https:\/\/www.usenix.org\/conference\/fast20\/presentation\/cao-zhichao"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"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.1093\/bioinformatics\/btu558"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588726"},{"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\/3035918.3064054"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2010 USENIX Annual Technical Conference, USENIX ATC 2010","author":"Debnath Biplob K.","year":"2010","unstructured":"Biplob K. Debnath, Sudipta Sengupta, and Jin Li. 2010. ChunkStash: Speeding Up Inline Storage Deduplication Using Flash Memory. In Proceedings of the 2010 USENIX Annual Technical Conference, USENIX ATC 2010, Boston, MA, USA, June 23--25, 2010, Paul Barham and Timothy Roscoe (Eds.). USENIX Association. https:\/\/www.usenix.org\/conference\/usenixatc-10\/chunkstash-speeding-inline-storage-deduplication-using-flash-memory"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698820"},{"key":"e_1_2_1_17_1","volume-title":"Kuszmaul","author":"Esmet John","year":"2012","unstructured":"John Esmet, Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul. 2012. The TokuFS Streaming File System. In 4th USENIXWorkshop on Hot Topics in Storage and File Systems, HotStorage'12, Boston, MA, USA, June 13--14, 2012, Raju Rangaswami (Ed.). USENIX Association. https:\/\/www.usenix.org\/conference\/hotstorage12\/workshopprogram\/presentation\/esmet"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0573--15"},{"key":"e_1_2_1_20_1","unstructured":"Geoffrey Irving. 2012. Inverse of a hash function. https:\/\/naml.us\/post\/inverse-of-a-hash-function\/"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015","author":"Jannen William","year":"2015","unstructured":"William Jannen, Jun Yuan, Yang Zhan, Amogh Akshintala, John Esmet, Yizheng Jiao, Ankur Mittal, Prashant Pandey, Phaneendra Reddy, LeifWalsh, Michael A. Bender, Martin Farach-Colton, Rob Johnson, Bradley C. Kuszmaul, and Donald E. Porter. 2015. BetrFS: A Right-OptimizedWrite-Optimized File System. In Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST 2015, Santa Clara, CA, USA, February 16--19, 2015, Jiri Schindler and Erez Zadok (Eds.). USENIX Association, 301--315. https:\/\/www.usenix.org\/conference\/fast15\/technical-sessions\/presentation\/jannen"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592568.1592592"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380845"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320216"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"key":"e_1_2_1_26_1","unstructured":"Don Knuth. 1962. NOTES ON ''OPEN'' ADDRESSING. (1962). https:\/\/jeffe.cs.illinois.edu\/teaching\/datastructures\/2011\/notes\/knuth-OALP.pdf"},{"key":"e_1_2_1_27_1","volume-title":"Sorting and Searching. AddisonWesley","author":"Knuth Donald E.","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Vol. 3: Sorting and Searching. AddisonWesley, Reading, MA."},{"key":"e_1_2_1_28_1","volume-title":"15th Conference on Innovative Data Systems Research, CIDR 2025","author":"Kumar Ravi","year":"2025","unstructured":"Ravi Kumar, Todd Lipcon, Manish Purohit, and Tam\u00e1s Sarl\u00f3s. 2025. Linear Elastic Caching via Ski Rental. In 15th Conference on Innovative Data Systems Research, CIDR 2025, Amsterdam, The Netherlands, January 19--22, 2025. www.cidrdb.org. https:\/\/vldb.org\/cidrdb\/2025\/linear-elastic-caching-via-ski-rental.html"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2021.60"},{"key":"e_1_2_1_30_1","unstructured":"Heng Li. 2015. Invertible Hash Function Implementation. https:\/\/gist.github.com\/lh3\/59882d6b96166dfc3d8d. GitHub Gist. Accessed: 2026-02-02."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217022"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3339504"},{"key":"e_1_2_1_33_1","unstructured":"MongoDB. 2024. WiredTiger Storage Engine. https:\/\/www.mongodb.com\/docs\/manual\/core\/wiredtiger\/"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070548"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452841"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168845"},{"key":"e_1_2_1_38_1","volume-title":"Weightless: Lossy weight encoding for deep neural network compression. In 6th International Conference on Learning Representations, ICLR","author":"Reagen Brandon","year":"2018","unstructured":"Brandon Reagen, Udit Gupta, Robert Adolf, Michael Mitzenmacher, Alexander M. Rush, Gu-Yeon Wei, and David Brooks. 2018. Weightless: Lossy weight encoding for deep neural network compression. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Workshop Track Proceedings. OpenReview.net. https:\/\/openreview.net\/forum?id=rJpXxgaIG"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2022.3182906"},{"key":"e_1_2_1_40_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_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677128"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1658939.1658975"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-025-00928--6"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802121","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:33:13Z","timestamp":1779129193000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802121"],"URL":"https:\/\/doi.org\/10.1145\/3802121","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}