This repository hosts a Rust library implementing xor filters -- data structures for fast approximation of set membership using little memory. Probabilistic filters like xor filters are useful for quickly estimating of the existence of an entity to avoid using an expensive resource. For example, they can be used to reduce disk writes in a cache or identify malicious URLs.
Xor filters are faster and smaller than Bloom and Cuckoo filters. Xor filters incur a relative time penalty in construction, but are very fast in lookups; the expectation is that construction of a filter is amortized after many queries. Daniel Lemire's go implementation provides a useful summary of xor filters' benefits and listing of other xor filter libraries.
Xor filters operate on sets ofs 64-bit unsigned integers. Information regarding
usage of the filters can be found in the
library documentation. This library is no_std and
needs_allocator.