Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters

摘要

The Bloom filter provides fast approximate set membership while using little memory. Engineers often usethese filters to avoid slow operations such as disk or network accesses. As an alternative, a cuckoo filter mayneed less space than a Bloom filter and it is faster. Chazelle et al. proposed a generalization of the Bloomfilter called the Bloomier filter. Dietzfelbinger and Pagh described a variation on the Bloomier filter that cananswer approximate membership queries over immutable sets. It has never been tested empirically, to ourknowledge. We review an efficient implementation of their approach, which we call the xor filter. We findthat xor filters can be faster than Bloom and cuckoo filters while using less memory. We further show thata 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.