{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T16:07:41Z","timestamp":1787242061775,"version":"build-2736575974"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>We present Sparse Numerical Array-Based Range Filters (SNARF), a learned range filter that efficiently supports range queries for numerical data. SNARF creates a model of the data distribution to map the keys into a bit array which is stored in a compressed form. The model along with the compressed bit array which constitutes SNARF are used to answer membership queries.<\/jats:p>\n                  <jats:p>We evaluate SNARF on multiple synthetic and real-world datasets as a stand-alone filter and by integrating it into RocksDB. For range queries, SNARF provides up to 50x better false positive rate than state-of-the-art range filters, such as SuRF and Rosetta, with the same space usage. We also evaluate SNARF in RocksDB as a filter replacement for filtering requests before they access on-disk data structures. For RocksDB, SNARF can improve the execution time of the system up to 10x compared to SuRF and Rosetta for certain read-only workloads.<\/jats:p>","DOI":"10.14778\/3529337.3529347","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T18:23:05Z","timestamp":1655922185000},"page":"1632-1644","source":"Crossref","is-referenced-by-count":40,"title":["SNARF"],"prefix":"10.14778","volume":"15","author":[{"given":"Kapil","family":"Vaidya","sequence":"first","affiliation":[{"name":"MIT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subarna","family":"Chatterjee","sequence":"additional","affiliation":[{"name":"Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Knorr","sequence":"additional","affiliation":[{"name":"Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[{"name":"Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stratos","family":"Idreos","sequence":"additional","affiliation":[{"name":"Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Kraska","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556556"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_2_1_3_1","volume-title":"422--426","author":"Bloom Burton H.","year":"1970","unstructured":"Burton H. Bloom . 1970. Space\/ Time Trade-Offs in Hash Coding with Allowable Errors . ( 1970 ), 422--426 . Burton H. Bloom. 1970. Space\/Time Trade-Offs in Hash Coding with Allowable Errors. (1970), 422--426."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_5_1","volume-title":"Better bitmap performance with roaring bitmaps. Software: practice and experience 46, 5","author":"Chambi Samy","year":"2016","unstructured":"Samy Chambi , Daniel Lemire , Owen Kaser , and Robert Godin . 2016. Better bitmap performance with roaring bitmaps. Software: practice and experience 46, 5 ( 2016 ), 709--719. Samy Chambi, Daniel Lemire, Owen Kaser, and Robert Godin. 2016. Better bitmap performance with roaring bitmaps. Software: practice and experience 46, 5 (2016), 709--719."},{"key":"e_1_2_1_6_1","unstructured":"Efficient Lab CMU. 2020. https:\/\/github.com\/efficient\/cuckoofilter.  Efficient Lab CMU. 2020. https:\/\/github.com\/efficient\/cuckoofilter."},{"key":"e_1_2_1_7_1","unstructured":"Efficient Lab CMU. 2020. https:\/\/github.com\/efficient\/SuRF.  Efficient Lab CMU. 2020. https:\/\/github.com\/efficient\/SuRF."},{"key":"e_1_2_1_8_1","volume-title":"Concise: Compressed `n'composable integer set. Inform. Process. Lett.","author":"Colantonio Alessandro","year":"2010","unstructured":"Alessandro Colantonio and Roberto Di Pietro . 2010 . Concise: Compressed `n'composable integer set. Inform. Process. Lett. (2010), 644--650. Alessandro Colantonio and Roberto Di Pietro. 2010. Concise: Compressed `n'composable integer set. Inform. Process. Lett. (2010), 644--650."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807152"},{"key":"e_1_2_1_11_1","unstructured":"Andrew Crotty. 2021. Hist-Tree: Those Who Ignore It Are Doomed to Learn. In CIDR.  Andrew Crotty. 2021. Hist-Tree: Those Who Ignore It Are Doomed to Learn. In CIDR."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739071"},{"key":"e_1_2_1_13_1","volume-title":"Ribbon filter: practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515","author":"Dillinger Peter C","year":"2021","unstructured":"Peter C Dillinger and Stefan Walzer . 2021. Ribbon filter: practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515 ( 2021 ). Peter C Dillinger and Stefan Walzer. 2021. Ribbon filter: practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515 (2021)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389711"},{"key":"e_1_2_1_15_1","unstructured":"Facebook. 2015. http:\/\/myrocks.io\/.  Facebook. 2015. http:\/\/myrocks.io\/."},{"key":"e_1_2_1_16_1","volume-title":"Mitzenmacher","author":"Fan Bin","year":"2014","unstructured":"Bin Fan , David G. Andersen , Michael Kaminsky , and Michael D . Mitzenmacher . 2014 . Cuckoo Filter : Practically Better Than Bloom. In Proc. CoNEXT. Bin Fan, David G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. 2014. Cuckoo Filter: Practically Better Than Bloom. In Proc. CoNEXT."},{"key":"e_1_2_1_17_1","volume-title":"The PGM-index. Proceedings of the VLDB Endowment 13","author":"Ferragina Paolo","year":"2020","unstructured":"Paolo Ferragina and Giorgio Vinciguerra . 2020 . The PGM-index. Proceedings of the VLDB Endowment 13 (2020). Paolo Ferragina and Giorgio Vinciguerra. 2020. The PGM-index. Proceedings of the VLDB Endowment 13 (2020)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0717021"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055357"},{"key":"e_1_2_1_21_1","volume-title":"Poster Proc.","volume":"38","author":"Gonz\u00e1lez Rodrigo","year":"2005","unstructured":"Rodrigo Gonz\u00e1lez , Szymon Grabowski , Veli M\u00e4kinen , and Gonzalo Navarro . 2005 . Practical implementation of rank and select queries . In Poster Proc. Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). 27-- 38 . Rodrigo Gonz\u00e1lez, Szymon Grabowski, Veli M\u00e4kinen, and Gonzalo Navarro. 2005. Practical implementation of rank and select queries. In Poster Proc. Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). 27--38."},{"key":"e_1_2_1_22_1","volume-title":"Kasper Green Larsen, and Rasmus Pagh","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 . arXiv:1407.2907 [cs.DS] Mayank Goswami, Allan Gr\u00f8nlund, Kasper Green Larsen, and Rasmus Pagh. 2014. Approximate Range Emptiness in Constant Time and Optimal Space. arXiv:1407.2907 [cs.DS]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376122"},{"key":"e_1_2_1_24_1","volume-title":"More Haste","author":"Grossi Roberto","unstructured":"Roberto Grossi , Alessio Orlandi , Rajeev Raman , and S. Srinivasa Rao . 2009. More Haste , Less Waste : Lowering the Redundancy in Fully Indexable Dictionaries . arXiv:0902.2648 [cs.DS] Roberto Grossi, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao. 2009. More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries. arXiv:0902.2648 [cs.DS]"},{"key":"e_1_2_1_25_1","unstructured":"Ali Hadian and Thomas Heinis. 2021. Shift-Table: A Low-latency Learned Index for Range Queries using Model Correction. arXiv:2101.10457 [cs.DB]  Ali Hadian and Thomas Heinis. 2021. Shift-Table: A Low-latency Learned Index for Range Queries using Model Correction. arXiv:2101.10457 [cs.DB]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3383133"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656234"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Andreas Kipf Ryan Marcus Alexander van Renen Mihail Stoian Alfons Kemper Tim Kraska and Thomas Neumann. 2020. RadixSpline: A Single-Pass Learned Index. arXiv:2004.14541 [cs.DB]  Andreas Kipf Ryan Marcus Alexander van Renen Mihail Stoian Alfons Kemper Tim Kraska and Thomas Neumann. 2020. RadixSpline: A Single-Pass Learned Index. arXiv:2004.14541 [cs.DB]","DOI":"10.1145\/3401071.3401659"},{"key":"e_1_2_1_29_1","volume-title":"Jeffrey Dean, and Neoklis Polyzotis.","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska , Alex Beutel , Ed H. Chi , Jeffrey Dean, and Neoklis Polyzotis. 2018 . The Case for Learned Index Structures . arXiv:1712.01208 [cs.DB] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. arXiv:1712.01208 [cs.DB]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389752"},{"key":"e_1_2_1_31_1","unstructured":"Ani Kristo Kapil Vaidya and Tim Kraska. 2021. Defeating duplicates: A re-design of the LearnedSort algorithm. arXiv:2107.03290 [cs.DS]  Ani Kristo Kapil Vaidya and Tim Kraska. 2021. Defeating duplicates: A re-design of the LearnedSort algorithm. arXiv:2107.03290 [cs.DS]"},{"key":"e_1_2_1_32_1","unstructured":"Cockroach Labs. 2015. https:\/\/github.com\/cockroachdb\/cockroach.  Cockroach Labs. 2015. https:\/\/github.com\/cockroachdb\/cockroach."},{"key":"e_1_2_1_33_1","unstructured":"Yongkun Li Chengjin Tian Fan Guo Cheng Li and Yinlong Xu. 2019. Elasticbf: elastic bloom filter with hotness awareness for boosting read performance in large key-value stores. In 2019 {USENIX} Annual Technical Conference ({USENIX} {ATC} 19). 739--752.  Yongkun Li Chengjin Tian Fan Guo Cheng Li and Yinlong Xu. 2019. Elasticbf: elastic bloom filter with hotness awareness for boosting read performance in large key-value stores. In 2019 { USENIX } Annual Technical Conference ( { USENIX } { ATC } 19). 739--752."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389731"},{"key":"e_1_2_1_35_1","volume-title":"Workshop on ML for Systems at NeurIPS.","author":"Macke Stephen","year":"2018","unstructured":"Stephen Macke , Alex Beutel , Tim Kraska , Maheswaran Sathiamoorthy , Derek Zhiyuan Cheng , and EH Chi . 2018 . Lifting the curse of multidimensional data with learned existence indexes . In Workshop on ML for Systems at NeurIPS. Stephen Macke, Alex Beutel, Tim Kraska, Maheswaran Sathiamoorthy, Derek Zhiyuan Cheng, and EH Chi. 2018. Lifting the curse of multidimensional data with learned existence indexes. In Workshop on ML for Systems at NeurIPS."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Ryan Marcus Andreas Kipf Alexander van Renen Mihail Stoian Sanchit Misra Alfons Kemper Thomas Neumann and Tim Kraska. 2020. Benchmarking Learned Indexes. arXiv:2006.12804 [cs.DB]  Ryan Marcus Andreas Kipf Alexander van Renen Mihail Stoian Sanchit Misra Alfons Kemper Thomas Neumann and Tim Kraska. 2020. Benchmarking Learned Indexes. arXiv:2006.12804 [cs.DB]","DOI":"10.14778\/3421424.3421425"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"e_1_2_1_38_1","volume-title":"Garnett (Eds.)","volume":"31","author":"Mitzenmacher Michael","year":"2018","unstructured":"Michael Mitzenmacher . 2018 . A Model for Learned Bloom Filters and Optimizing by Sandwiching. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R . Garnett (Eds.) , Vol. 31 . Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper\/ 2018\/file\/0f49c89d1e7298bb9930789c8ed59d48-Paper.pdf Michael Mitzenmacher. 2018. A Model for Learned Bloom Filters and Optimizing by Sandwiching. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc. https:\/\/proceedings.neurips.cc\/paper\/2018\/file\/0f49c89d1e7298bb9930789c8ed59d48-Paper.pdf"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_40_1","volume-title":"Succincter. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 305--313","author":"Patrascu Mihai","year":"2008","unstructured":"Mihai Patrascu . 2008 . Succincter. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 305--313 . Mihai Patrascu. 2008. Succincter. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 305--313."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_9"},{"key":"e_1_2_1_42_1","unstructured":"Christian Riegger Arthur Bernhardt Bernhard Moessner and Ilia Petrov. 2020. bloomRF: On Performing Range-Queries with Bloom-Filters based on Piecewise-Monotone Hash Functions and Dyadic Trace-Trees. arXiv:2012.15596 [cs.DB]  Christian Riegger Arthur Bernhardt Bernhard Moessner and Ilia Petrov. 2020. bloomRF: On Performing Range-Queries with Bloom-Filters based on Piecewise-Monotone Hash Functions and Dyadic Trace-Trees. arXiv:2012.15596 [cs.DB]"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453914"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"e_1_2_1_45_1","volume-title":"Partitioned Learned Bloom Filter. CoRR abs\/2006.03176","author":"Vaidya Kapil","year":"2020","unstructured":"Kapil Vaidya , Eric Knorr , Tim Kraska , and Michael Mitzenmacher . 2020. Partitioned Learned Bloom Filter. CoRR abs\/2006.03176 ( 2020 ). arXiv:2006.03176 https:\/\/arxiv.org\/abs\/2006.03176 Kapil Vaidya, Eric Knorr, Tim Kraska, and Michael Mitzenmacher. 2020. Partitioned Learned Bloom Filter. CoRR abs\/2006.03176 (2020). arXiv:2006.03176 https:\/\/arxiv.org\/abs\/2006.03176"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 2019 International Conference on Management of Data (SIGMOD '19)","author":"Sandt Peter Van","unstructured":"Peter Van Sandt , Yannis Chronis , and Jignesh M. Patel . 2019. Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search? . In Proceedings of the 2019 International Conference on Management of Data (SIGMOD '19) . 36--53. Peter Van Sandt, Yannis Chronis, and Jignesh M. Patel. 2019. Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD '19). 36--53."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196931"},{"key":"e_1_2_1_48_1","volume-title":"REMIX: Efficient Range Query for LSM-trees. In FAST.","author":"Zhong Wenshao","year":"2021","unstructured":"Wenshao Zhong , Chen Chen , Xingbo Wu , and Song Jiang . 2021 . REMIX: Efficient Range Query for LSM-trees. In FAST. Wenshao Zhong, Chen Chen, Xingbo Wu, and Song Jiang. 2021. REMIX: Efficient Range Query for LSM-trees. In FAST."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_15"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3529337.3529347","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:47:00Z","timestamp":1672202820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3529337.3529347"}},"subtitle":["a learning-enhanced range filter"],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":49,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.14778\/3529337.3529347"],"URL":"https:\/\/doi.org\/10.14778\/3529337.3529347","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}