Crate xorf[−][src]
Expand description
This library implements 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.
Xor filters operate only on sets of 64-bit (unsigned) integers. This library does not provide
methods for hashing arbitrary types to 64-bit integers. Xor filters are immutable,
serializable, and guarantee no false negatives. This library is no_std and needs_allocator.
Filters are implemented as described in the paper Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters and in Daniel Lemire’s go and c implementations. All are useful references on the theory behind xor filters. For performance statistics, refer to individual filters’ documentation or the mentioned paper.
General considerations for all filters
For a given N, XorN filters are larger and less uniform than FuseN filters, but XorN are
guaranteed to be constructable while FuseN filters require a large number of keys for
construction to succeed. N refers to the bit size of a fingerprint (the
result of a hash function) in the filter. Filters with larger fingerprints trade off
lower false-positive rates for greater filter sizes.
The false-positive rate of a filter with fingerprint size N is around 2^{-N}; for more
numbers, see the documentation of each individual filter.
Below, we list important constraints to keep in mind regardless of the filter used:
- It is a pre-condition that all filters are constructed from a data structure containing no duplicate keys. You must perform any de-duplication needed yourself before constructing a filter.
Structs
Xor filter using 8-bit fingerprints in a fuse graph. Requires less space than an Xor8.
Xor filter using 16-bit fingerprints in a fuse graph. Requires less space than an Xor16.
Xor filter using 32-bit fingerprints in a fuse graph. Requires less space than an Xor32.
Arbitrary key type proxy for xor filters.
Xor filter using 8-bit fingerprints.
Xor filter using 16-bit fingerprints.
Xor filter using 32-bit fingerprints.
Traits
Methods common to xor filters.