Qfilter

Efficient bloom filter like data structure, based on the Rank Select Quotient Filter (RSQF).

This is a small and flexible general-purpose AMQ-Filter. It not only supports approximate membership testing like a bloom filter but also deletions, merging, resizing and serde serialization.

• High performance
• Supports removals
• Extremely compact, more so than comparable filters
• Can be created with a initial small capacity and grow as needed
• (De)Serializable with serde
• Portable Rust implementation
• Only verifiable usages of unsafe

This data structure is a succinct hash table that can store fingerprints in a very compact way. Fingerprints are similar to a hash values, but are possibly truncated. The reason for false positives is that multiple items can map to the same fingerprint. For more information see the quotient filter Wikipedia page that describes a similar but less optimized version of the data structure. The actual implementation is based on the Rank Select Quotient Filter (RSQF).

The public API also exposes a fingerprint API, which can be used to succinctly store u64 hash values.

Example

let mut f = qfilter::Filter::new(1000000, 0.01).unwrap();
for i in 0..1000 {
    f.insert(i).unwrap();
}
for i in 0..1000 {
    assert!(f.contains(i));
}

Hasher

The hashing algorithm used is xxhash3 which offers both high performance and stability across platforms.

Filter size

For a given capacity and error probability the RSQF may require significantly less space than the equivalent bloom filter or other AMQ-Filters.

Compatibility between versions

Version 0.3 is not serialization compatible with previous versions.

Version 0.2 changed public APIs (e.g. fallible constructors) which required a major version bump.

Serialization is bidirectionally compatible between versions 0.1 and 0.2.

Not implemented

• Fingerprint attached values
• Counting with fingerprint attached values, not fingerprint duplication
• More advanced growth strategies (InfiniFilter).

Legacy x86_64 CPUs support

The implementation assumes popcnt and BMI2 (pdep, tzcnt) instructions are available when compiling for x86_64 targets. These instructions are available on CPUs from 2015 or later. If they are not available, the Filter constructor will panic.

The legacy_x86_64_support feature enables support for older x86_64 CPUs by using portable fallbacks and a ~10% performance penalty.

License

This project is licensed under the MIT license.