{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T06:45:47Z","timestamp":1784011547502,"version":"3.55.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>This paper presents new alternatives to the well-known Bloom filter data structure. The Bloom filter, a compact data structure supporting set insertion and membership queries, has found wide application in databases, storage systems, and networks. Because the Bloom filter performs frequent random reads and writes, it is used almost exclusively in RAM, limiting the size of the sets it can represent.<\/jats:p>\n          <jats:p>This paper first describes the quotient filter, which supports the basic operations of the Bloom filter, achieving roughly comparable performance in terms of space and time, but with better data locality. Operations on the quotient filter require only a small number of contiguous accesses. The quotient filter has other advantages over the Bloom filter: it supports deletions, it can be dynamically resized, and two quotient filters can be efficiently merged.<\/jats:p>\n          <jats:p>The paper then gives two data structures, the buffered quotient filter and the cascade filter, which exploit the quotient filter advantages and thus serve as SSD-optimized alternatives to the Bloom filter. The cascade filter has better asymptotic I\/O performance than the buffered quotient filter, but the buffered quotient filter outperforms the cascade filter on small to medium data sets. Both data structures significantly outperform recently-proposed SSD-optimized Bloom filter variants, such as the elevator Bloom filter, buffered Bloom filter, and forest-structured Bloom filter. In experiments, the cascade filter and buffered quotient filter performed insertions 8.6--11 times faster than the fastest Bloom filter variant and performed lookups 0.94--2.56 times faster.<\/jats:p>","DOI":"10.14778\/2350229.2350275","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1627-1637","source":"Crossref","is-referenced-by-count":161,"title":["Don't thrash"],"prefix":"10.14778","volume":"5","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University and Tokutek, Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University and Tokutek, Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"Stony Brook University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Russell","family":"Kraner","sequence":"additional","affiliation":[{"name":"VCORE Solutions LLC."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bradley C.","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"MIT and Tokutek, Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dzejla","family":"Medjedovic","sequence":"additional","affiliation":[{"name":"Stony Brook University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pablo","family":"Montes","sequence":"additional","affiliation":[{"name":"Stony Brook University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pradeep","family":"Shetty","sequence":"additional","affiliation":[{"name":"Stony Brook University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Richard P.","family":"Spillane","sequence":"additional","affiliation":[{"name":"Stony Brook University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erez","family":"Zadok","sequence":"additional","affiliation":[{"name":"Stony Brook University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_61"},{"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":"VLDB ADMS Workshop","author":"Canim M.","year":"2010","unstructured":"M. Canim , G. A. Mihaila , B. Bhattacharhee , C. A. Lang , and K. A. Ross . Buffered Bloom filters on solid state storage . In VLDB ADMS Workshop , 2010 . M. Canim, G. A. Mihaila, B. Bhattacharhee, C. A. Lang, and K. A. Ross. Buffered Bloom filters on solid state storage. In VLDB ADMS Workshop, 2010."},{"key":"e_1_2_1_6_1","first-page":"205","volume-title":"OSDI","author":"Chang F.","year":"2006","unstructured":"F. Chang , J. Dean , S. Ghemawat , W. C. Hsieh , D. A. Wallach , M. Burrows , T. Chandra , A. Fikes , and R. E. Gruber . Bigtable: A distributed storage system for structured data . In OSDI , pages 205 -- 218 , 2006 . F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: A distributed storage system for structured data. In OSDI, pages 205--218, 2006."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00454-4_7"},{"key":"e_1_2_1_8_1","unstructured":"H. Cheung. TG Video: Fusion io - the power of 1000 hard drives in the palm of your hand. http:\/\/www.tgdaily.com\/hardware-features\/34065-tg-video-fusion-io-the-power-of-1000-hard-drives-in-the-palm-of-your-hand 2007.  H. Cheung. TG Video: Fusion io - the power of 1000 hard drives in the palm of your hand. http:\/\/www.tgdaily.com\/hardware-features\/34065-tg-video-fusion-io-the-power-of-1000-hard-drives-in-the-palm-of-your-hand 2007."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.44"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"e_1_2_1_12_1","volume-title":"Apr.","author":"Freeman L.","year":"2010","unstructured":"L. Freeman . How NetApp deduplication works - a primer , Apr. 2010 . http:\/\/blogs.netapp.com\/drdedupe\/2010\/04\/how-netapp-deduplication-works.html. L. Freeman. How NetApp deduplication works - a primer, Apr. 2010. http:\/\/blogs.netapp.com\/drdedupe\/2010\/04\/how-netapp-deduplication-works.html."},{"key":"e_1_2_1_13_1","volume-title":"Design and validation of computer protocols","author":"Holzmann G. J.","year":"1991","unstructured":"G. J. Holzmann . Design and validation of computer protocols . Prentice-Hall, Inc. , 1991 . G. J. Holzmann. Design and validation of computer protocols. Prentice-Hall, Inc., 1991."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1740390.1740395"},{"key":"e_1_2_1_15_1","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"Knuth D. E.","year":"1973","unstructured":"D. E. Knuth . The Art of Computer Programming: Sorting and Searching , volume 3 . Addison Wesley , 1973 . D. E. Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison Wesley, 1973."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1987816.1987827"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2011.5937232"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92995-6_13"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.52778"},{"key":"e_1_2_1_20_1","first-page":"126","volume-title":"SIGIR Workshop on Distributed Multimedia Information Retrieval","author":"Singh A.","year":"2003","unstructured":"A. Singh , M. Srivatsa , L. Liu , and T. Miller . Apoidea: A decentralized peer-to-peer architecture for crawling the world wide web . In SIGIR Workshop on Distributed Multimedia Information Retrieval , pages 126 -- 142 , 2003 . A. Singh, M. Srivatsa, L. Liu, and T. Miller. Apoidea: A decentralized peer-to-peer architecture for crawling the world wide web. In SIGIR Workshop on Distributed Multimedia Information Retrieval, pages 126--142, 2003."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/WAIM.2008.45"},{"key":"e_1_2_1_22_1","first-page":"1","volume-title":"FAST","author":"Zhu B.","year":"2008","unstructured":"B. Zhu , K. Li , and H. Patterson . Avoiding the disk bottleneck in the data domain deduplication file system . In FAST , pages 18: 1 -- 18 :14, 2008 . B. Zhu, K. Li, and H. Patterson. Avoiding the disk bottleneck in the data domain deduplication file system. In FAST, pages 18:1--18:14, 2008."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:31:09Z","timestamp":1672227069000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350275"}},"subtitle":["how to cache your hash on flash"],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":22,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350275"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350275","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}