  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.
