HackerPapers

arXiv:1912.08258cs.DS

Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters

Thomas Mueller Graf, Daniel Lemire

Abstract

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 be used effectively for approximate membership queries. 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.

arXiv comments
Journal reference
Journal of Experimental Algorithmics 25 (1), 2020
DOI
doi:10.1145/3376122
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 6 identifiable commenters in 6 comments across 5 threads, from Dec 2019 to Jul 2025.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. Efficient set-membership filters and dictionaries based on SAT 1 comment

    • the reference in the repo is paywalled (US$ 30!). I did find this https://arxiv.org/pdf/1912.08258 which may or may not be related. but what I found interesting is that the construction looks alot like perfect hashes

      convolvatronView on HNParent context

  2. Bloom Filters 1 comment

    • > check the literature for various alternatives that are better in specific situations For direct replacements, see Xor(+)-Filters: https://arxiv.org/abs/1912.08258 and the subsequent evolution into Binary Fuse Filters: https://arxiv.org/abs/2201.01174

      f_devdView on HNParent context

  3. Bloom Filters: More than a space-efficient hashmap 1 comment

    • This paper seems to use an un-optimized Bloom filter implementation. It also lists cuckoo filters to be 10 times faster than Bloom filters. In other papers, e.g. the cuckoo filter paper and the xor filter paper, the difference is _much_ smaller; maybe factor 2.…

      thomasmgView on HNParent context

  4. Bloom filters debunked: Dispelling 30 Years of bad math with Coq 1 comment

    • Or you go with Xor filters, which are more efficient than both Cockoo and Bloom filters. [0] [0] https://arxiv.org/abs/1912.08258 ("Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters")

      19hView on HNParent context

  5. Xor Filters: Faster and Smaller Than Bloom Filters 2 comments

    • Direct link to paper (pdf) - https://arxiv.org/pdf/1912.08258.pdf I haven't fully read the paper yet, but it seems like a variation of a bloom filter where membership is determined by xoring three hashes (see algorithm 1 in the pdf)

      colinchartierView on HNParent context

    • He probably did not talk about it because this post was an announcement of his paper: https://arxiv.org/abs/1912.08258, the XOR filter description starts at page 3.

      _visgeanView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.