{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T05:14:39Z","timestamp":1771046079379,"version":"3.50.1"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SA 933\/3-1"],"award-info":[{"award-number":["SA 933\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>A Bloom filter is a very compact data structure that supports approximate membership queries on a set, allowing false positives.<\/jats:p>\n          <jats:p>We propose several new variants of Bloom filters and replacements with similar functionality. All of them have a better cache-efficiency and need less hash bits than regular Bloom filters. Some use SIMD functionality, while the others provide an even better space efficiency. As a consequence, we get a more flexible trade-off between false-positive rate, space-efficiency, cache-efficiency, hash-efficiency, and computational effort. We analyze the efficiency of Bloom filters and the proposed replacements in detail, in terms of the false-positive rate, the number of expected cache-misses, and the number of required hash bits. We also describe and experimentally evaluate the performance of highly tuned implementations. For many settings, our alternatives perform better than the methods proposed so far.<\/jats:p>","DOI":"10.1145\/1498698.1594230","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":60,"title":["Cache-, hash-, and space-efficient bloom filters"],"prefix":"10.1145","volume":"14","author":[{"given":"Felix","family":"Putze","sequence":"first","affiliation":[{"name":"Universit\u00e4t Karlsruhe"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Singler","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405292"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 6th International Formal Methods in Computer-Aided Design (FMCAD'04)","author":"Dillinger P. C."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 11th International SPIN Workshop. Springer","author":"Dillinger P. C."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.851975"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_42"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Lumetta S. and Mitzenmacher M. 2006. Using the power of two choices to improve bloom filters. http:\/\/www.eecs.harvard.edu\/~michaelm\/postscripts\/bftwo.ps.  Lumetta S. and Mitzenmacher M. 2006. Using the power of two choices to improve bloom filters. http:\/\/www.eecs.harvard.edu\/~michaelm\/postscripts\/bftwo.ps.","DOI":"10.1080\/15427951.2007.10129136"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00032-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Moffat A. and Turpin A. 2002. Compression and Coding Algorithms. Kluwer.   Moffat A. and Turpin A. 2002. Compression and Coding Algorithms. Kluwer.","DOI":"10.1007\/978-1-4615-0935-6"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 16th Annual Symposium on Discrete Algorithms (SODA'05)","author":"Pagh A."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.83"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics, Philadephia.","author":"Sanders P."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1594230","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1594230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:38Z","timestamp":1750253918000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1594230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":15,"alternative-id":["10.1145\/1498698.1594230"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1594230","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}