xorf
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.
This library is no_std and
needs_allocator.
Currently, the following xor filters are provided:
xorf also provides a HashProxy for using Xor filters
with arbitrary key types.
Installation
Add a dependency to xorf in Cargo.toml:
[]
= "M.m.p" # use a desired version
Available versions are listed on crates and the in repository's releases.
Usage
Please see the library documentation for usage information.
Features
To enable
needs_allocator
and serialization/deserialization, add the nightly and serde features,
respectively:
[]
= { = "M.m.p", = ["nightly", "serde"] }
By default, xorf uses the uniform-random feature, which uses random values for unused
fingerprint entries rather than setting them to zero. This provides a slightly lower false-positive
rate, but incurs a higher initialization cost. The cost of lookups is not affected.
To disable the uniform-random feature, specify that default features should be disabled:
[]
= { = "M.m.p", = false }
Development
Development of xorf targets the master branch of this repository.
Changes can be tested by running the check script:
Contribution
Contributions are warmly welcomed. No contribution is too small, and all are appreciated.