{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:06Z","timestamp":1787022366966,"version":"build-2736575974"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p>We present Stacked Filters, a new probabilistic filter which is fast and robust similar to query-agnostic filters (such as Bloom and Cuckoo filters), and at the same time brings low false positive rates and sizes similar to classifier-based filters (such as Learned Filters). The core idea is that Stacked Filters incorporate workload knowledge about frequently queried non-existing values. Instead of learning, they structurally incorporate that knowledge using hashing and several sequenced filter layers, indexing both data and frequent negatives. Stacked Filters can also gather workload knowledge on-the-fly and adaptively build the filter. We show experimentally that for a given memory budget, Stacked Filters achieve end-to-end query throughput up to 130x better than the best alternative for a workload, either query-agnostic or classifier-based filters, and depending on where data is (SSD or HDD).<\/jats:p>","DOI":"10.14778\/3436905.3436919","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T12:23:50Z","timestamp":1613996630000},"page":"600-612","source":"Crossref","is-referenced-by-count":22,"title":["Stacked filters"],"prefix":"10.14778","volume":"14","author":[{"given":"Kyle","family":"Deeds","sequence":"first","affiliation":[{"name":"Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Brian","family":"Hentschel","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"}]}],"member":"320","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Shalla secure services kg. http:\/\/www.shallalist.de.  Shalla secure services kg. http:\/\/www.shallalist.de."},{"key":"e_1_2_1_2_1","unstructured":"Top 10 million websites: Openpagerank. \"https:\/\/www.domcop.com\/openpagerank\/what-is-openpagerank\".  Top 10 million websites: Openpagerank. \"https:\/\/www.domcop.com\/openpagerank\/what-is-openpagerank\"."},{"key":"e_1_2_1_3_1","volume-title":"Firehose streaming benchmarks","author":"Anderson K.","year":"2015"},{"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.14778\/3213880.3213884"},{"key":"e_1_2_1_7_1","first-page":"636","volume-title":"Internet Mathematics","author":"Broder A.","year":"2002"},{"key":"e_1_2_1_8_1","first-page":"2304","volume-title":"Weighted bloom filter","author":"Bruck J.","year":"2006"},{"key":"e_1_2_1_9_1","first-page":"1","volume-title":"ADMS@ VLDB","author":"Canim M.","year":"2010"},{"key":"e_1_2_1_10_1","volume-title":"Yes-no bloom filter: A way of representing sets with fewer false positives. arXiv preprint arXiv:1603.01060","author":"Carrea L.","year":"2016"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.2011358"},{"key":"e_1_2_1_13_1","volume-title":"Adaptive learned bloom filter (ada-bf): Efficient utilization of the classifier","author":"Dai Z.","year":"2019"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064054"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.44"},{"key":"e_1_2_1_16_1","volume-title":"Technical report: Stacked filters","author":"Deeds K.","year":"2020"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142477"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863979"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1368436.1368454"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cose.2009.04.007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2664243.2664267"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3077136.3080789"},{"key":"e_1_2_1_25_1","volume-title":"Xor filters: Faster and smaller than bloom and cuckoo filters","author":"Graf T. M.","year":"2019"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329785.3329934"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSTCC.2015.7321404"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303757"},{"key":"e_1_2_1_30_1","volume-title":"Complement bloom filter for identifying true positiveness of a bloom filter","author":"Lim H.","year":"1905"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2011.27"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3326943.3326986"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3339504"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_35_1","volume-title":"Jan","author":"Pike G.","year":"2011"},{"key":"e_1_2_1_36_1","first-page":"51","volume-title":"A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation","author":"Powell M. J. D.","year":"1994"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1768570.1768582"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3267809.3267834"},{"key":"e_1_2_1_39_1","volume-title":"Meta-learning neural bloom filters. arXiv preprint arXiv:1906.04304","author":"Rae J. W.","year":"2019"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89737-8_15"},{"key":"e_1_2_1_41_1","volume-title":"Rocksdb trace, replay, analyzer, and workload generation","author":"DB.","year":"2020"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq230"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2011.031611.00024"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364333"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18123-3_21"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3436905.3436919","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:26:23Z","timestamp":1672205183000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3436905.3436919"}},"subtitle":["learning to filter by structure"],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.14778\/3436905.3436919"],"URL":"https:\/\/doi.org\/10.14778\/3436905.3436919","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}