{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:55:25Z","timestamp":1775638525903,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T00:00:00Z","timestamp":1584057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2017-03910"],"award-info":[{"award-number":["RGPIN-2017-03910"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2020,12,6]]},"abstract":"<jats:p>The Bloom filter provides fast approximate set membership while using little memory. Engineers often use these filters to avoid slow operations such as disk or network accesses. As an alternative, a cuckoo filter may need less space than a Bloom filter and it is faster. Chazelle et al. proposed a generalization of the Bloom filter called the Bloomier filter. Dietzfelbinger and Pagh described a variation on the Bloomier filter that can answer approximate membership queries over immutable sets. It has never been tested empirically, to our knowledge. We review an efficient implementation of their approach, which we call the xor filter. We find that xor filters can be faster than Bloom and cuckoo filters while using less memory. We further show that a more compact version of xor filters (xor+) can use even less space than highly compact alternatives (e.g., Golomb-compressed sequences) while providing speeds competitive with Bloom filters.<\/jats:p>","DOI":"10.1145\/3376122","type":"journal-article","created":{"date-parts":[[2020,3,13]],"date-time":"2020-03-13T12:03:13Z","timestamp":1584100993000},"page":"1-16","source":"Crossref","is-referenced-by-count":102,"title":["Xor Filters"],"prefix":"10.1145","volume":"25","author":[{"given":"Thomas Mueller","family":"Graf","sequence":"first","affiliation":[{"name":"University of Quebec (TELUQ), Montreal, Quebec, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3306-6922","authenticated-orcid":false,"given":"Daniel","family":"Lemire","sequence":"additional","affiliation":[{"name":"University of Quebec (TELUQ), Montreal, Quebec, Canada"}]}],"member":"320","published-online":{"date-parts":[[2020,3,13]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"4","article-title":"Boosting the priority of garbage: Scheduling collection on heterogeneous multicore processors","volume":"13","author":"Akram Shoaib","year":"2016","unstructured":"Shoaib Akram , Jennifer B. Sartor , Kenzo Van Craeynest , Wim Heirman , and Lieven Eeckhout . 2016 . Boosting the priority of garbage: Scheduling collection on heterogeneous multicore processors . ACM Trans. Architect. Code Optim. 13 , 1 (2016), 4 . Shoaib Akram, Jennifer B. Sartor, Kenzo Van Craeynest, Wim Heirman, and Lieven Eeckhout. 2016. Boosting the priority of garbage: Scheduling collection on heterogeneous multicore processors. ACM Trans. Architect. Code Optim. 13, 1 (2016), 4.","journal-title":"ACM Trans. Architect. Code Optim."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1224252.1224501"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2015.12"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_61"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394893.2394911"},{"key":"e_1_2_1_7_1","volume-title":"Jayasena","author":"Breslow Alex D.","year":"2018","unstructured":"Alex D. Breslow and Nuwan S . Jayasena . 2018 . Morton Filter. Retrieved from https:\/\/github.com\/AMDComputeLibraries\/morton_filter.git. Alex D. Breslow and Nuwan S. Jayasena. 2018. Morton Filter. Retrieved from https:\/\/github.com\/AMDComputeLibraries\/morton_filter.git."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213884"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the USENIX Conference on Usenix Annual Technical Conference (USENIX ATC\u201916)","author":"Breslow Alex D.","unstructured":"Alex D. Breslow , Dong Ping Zhang , Joseph L. Greathouse , Nuwan Jayasena , and Dean M. Tullsen . 2016. Horton tables: Fast hash tables for in-memory data-intensive computing . In Proceedings of the USENIX Conference on Usenix Annual Technical Conference (USENIX ATC\u201916) . USENIX Association, Berkeley, CA, 281--294. Alex D. Breslow, Dong Ping Zhang, Joseph L. Greathouse, Nuwan Jayasena, and Dean M. Tullsen. 2016. Horton tables: Fast hash tables for in-memory data-intensive computing. In Proceedings of the USENIX Conference on Usenix Annual Technical Conference (USENIX ATC\u201916). USENIX Association, Berkeley, CA, 281--294."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129096"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1365815.1365816"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_22"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Chazelle Bernard","year":"2004","unstructured":"Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , and Ayellet Tal . 2004 . The bloomier filter: An efficient data structure for static support lookup tables . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904) . Society for Industrial and Applied Mathematics, Philadelphia, PA, 30--39. Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal. 2004. The bloomier filter: An efficient data structure for static support lookup tables. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904). Society for Industrial and Applied Mathematics, Philadelphia, PA, 30--39."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Adina Crainiceanu and Daniel Lemire. 2015. Bloofi. Info. Syst. 54 C (Dec. 2015) 311--324.  Adina Crainiceanu and Daniel Lemire. 2015. Bloofi. Info. Syst. 54 C (Dec. 2015) 311--324.","DOI":"10.1016\/j.is.2015.01.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142477"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CONECT.2003.1231477"},{"key":"e_1_2_1_17_1","volume-title":"Succinct data structures for retrieval and approximate membership (extended abstract)","author":"Dietzfelbinger Martin","unstructured":"Martin Dietzfelbinger and Rasmus Pagh . 2008. Succinct data structures for retrieval and approximate membership (extended abstract) . In Automata, Languages and Programming, Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir, and Igor Walukiewicz (Eds.). Springer , Berlin , 385--396. Martin Dietzfelbinger and Rasmus Pagh. 2008. Succinct data structures for retrieval and approximate membership (extended abstract). In Automata, Languages and Programming, Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir, and Igor Walukiewicz (Eds.). Springer, Berlin, 385--396."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1504\/IJSN.2007.012824"},{"key":"e_1_2_1_19_1","unstructured":"Bin Fan and David G. Andersen. 2013--2017. Cuckoo Filter. Retrieved from https:\/\/github.com\/efficient\/cuckoofilter.  Bin Fan and David G. Andersen. 2013--2017. Cuckoo Filter. Retrieved from https:\/\/github.com\/efficient\/cuckoofilter."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT\u201914)","author":"Fan Bin","unstructured":"Bin Fan , David G. Andersen , Michael Kaminsky , and Michael D. Mitzenmacher . 2014. Cuckoo filter: Practically better than bloom . In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT\u201914) . ACM, New York, NY, 75--88. Bin Fan, David G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. 2014. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies (CoNEXT\u201914). ACM, New York, NY, 75--88."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2461"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328554.1328564"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236216"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303757"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3230636"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 9th European Conference on Computer Systems (EuroSys\u201914)","author":"Li Xiaozhou","unstructured":"Xiaozhou Li , David G. Andersen , Michael Kaminsky , and Michael J. Freedman . 2014. Algorithmic improvements for fast concurrent cuckoo hashing . In Proceedings of the 9th European Conference on Computer Systems (EuroSys\u201914) . ACM, New York, NY. Xiaozhou Li, David G. Andersen, Michael Kaminsky, and Michael J. Freedman. 2014. Algorithmic improvements for fast concurrent cuckoo hashing. In Proceedings of the 9th European Conference on Computer Systems (EuroSys\u201914). ACM, New York, NY."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.803864"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20061"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_30_1","unstructured":"Prashant Pandey Michael A. Bender Rob Johnson and Rob Patro. 2017. Counting Quotient Filter (CQF). Retrieved from https:\/\/github.com\/splatlab\/cqf.  Prashant Pandey Michael A. Bender Rob Johnson and Rob Patro. 2017. Counting Quotient Filter (CQF). Retrieved from https:\/\/github.com\/splatlab\/cqf."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035963"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 10th International Workshop on Data Management on New Hardware (DaMoN\u201914)","author":"Polychroniou Orestis","unstructured":"Orestis Polychroniou and Kenneth A. Ross . 2014. Vectorized bloom filters for advanced SIMD processors . In Proceedings of the 10th International Workshop on Data Management on New Hardware (DaMoN\u201914) . ACM, New York, NY. Orestis Polychroniou and Kenneth A. Ross. 2014. Vectorized bloom filters for advanced SIMD processors. In Proceedings of the 10th International Workshop on Data Management on New Hardware (DaMoN\u201914). ACM, New York, NY."},{"key":"e_1_2_1_33_1","volume-title":"An optimal bloom filter replacement based on matrix solving","author":"Porat Ely","unstructured":"Ely Porat . 2009. An optimal bloom filter replacement based on matrix solving . In Computer Science\u2014Theory and Applications, Anna Frid, Andrey Morozov, Andrey Rybalchenko, and Klaus W. Wagner (Eds.). Springer , Berlin , 263--273. Ely Porat. 2009. An optimal bloom filter replacement based on matrix solving. In Computer Science\u2014Theory and Applications, Anna Frid, Andrey Morozov, Andrey Rybalchenko, and Klaus W. Wagner (Eds.). Springer, Berlin, 263--273."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149202"},{"key":"e_1_2_1_35_1","article-title":"Cache-, hash-, and space-efficient bloom filters","author":"Putze Felix","year":"2010","unstructured":"Felix Putze , Peter Sanders , and Johannes Singler . 2010 . Cache-, hash-, and space-efficient bloom filters . J. Exp. Algor. 14 ( Jan. 2010). Felix Putze, Peter Sanders, and Johannes Singler. 2010. Cache-, hash-, and space-efficient bloom filters. J. Exp. Algor. 14 (Jan. 2010).","journal-title":"J. Exp. Algor. 14"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2272604"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_12"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MELCON.2010.5476244"},{"key":"e_1_2_1_40_1","volume-title":"Smith","author":"Weaver Sean A.","year":"2018","unstructured":"Sean A. Weaver , Hannah J. Roberts , and Michael J . Smith . 2018 . XOR-satisfiability set membership filters. In Proceedings of the Theory and Applications of Satisfiability Testing (SAT\u201918), Olaf Beyersdorff and Christoph M. Wintersteiger (Eds.). Springer International Publishing , Cham, 401--418. Sean A. Weaver, Hannah J. Roberts, and Michael J. Smith. 2018. XOR-satisfiability set membership filters. In Proceedings of the Theory and Applications of Satisfiability Testing (SAT\u201918), Olaf Beyersdorff and Christoph M. Wintersteiger (Eds.). Springer International Publishing, Cham, 401--418."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_15"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3376122","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3376122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:34Z","timestamp":1750203874000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3376122"}},"subtitle":["Faster and Smaller Than Bloom and Cuckoo Filters"],"short-title":[],"issued":{"date-parts":[[2020,3,13]]},"references-count":41,"alternative-id":["10.1145\/3376122"],"URL":"https:\/\/doi.org\/10.1145\/3376122","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,13]]}}}