Crate qfilter

Approximate Membership Query Filter (AMQ-Filter) 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.

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.

Bits per item	Error probability when full	Bits per item (cont.)	Error (cont.)
3.125	0.362	19.125	6.87e-06
4.125	0.201	20.125	3.43e-06
5.125	0.106	21.125	1.72e-06
6.125	0.0547	22.125	8.58e-07
7.125	0.0277	23.125	4.29e-07
8.125	0.014	24.125	2.15e-07
9.125	0.00701	25.125	1.07e-07
10.125	0.00351	26.125	5.36e-08
11.125	0.00176	27.125	2.68e-08
12.125	0.000879	28.125	1.34e-08
13.125	0.000439	29.125	6.71e-09
14.125	0.00022	30.125	3.35e-09
15.125	0.00011	31.125	1.68e-09
16.125	5.49e-05	32.125	8.38e-10
17.125	2.75e-05	..	..
18.125	1.37e-05	..	..

Legacy x86_64 CPUs support

The implementation assumes the popcnt instruction (equivalent to integer.count_ones()) is present when compiling for x86_64 targets. This is theoretically not guaranteed as the instruction in only available on AMD/Intel CPUs released after 2007/2008. If that’s not the case the Filter constructor will panic.

Support for such legacy x86_64 CPUs can be optionally enabled with the legacy_x86_64_support which incurs a ~10% performance penalty.

Structs

Filter

Approximate Membership Query Filter (AMQ-Filter) based on the Rank Select Quotient Filter (RSQF).

FingerprintIter

An iterator over the fingerprints of a Filter.

Enums

Error