Crate qfilter

source ·
Expand description

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 (not implemented), resizing and serde serialization.

Example

let mut f = qfilter::Filter::new(1000000, 0.01);
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 itemError probability when full
3.1250.362
4.1250.201
5.1250.106
6.1250.0547
7.1250.0277
8.1250.014
9.1250.00701
10.1250.00351
11.1250.00176
12.1250.000879
13.1250.000439
14.1250.00022
15.1250.00011
16.1255.49e-05
17.1252.75e-05
18.1251.37e-05
19.1256.87e-06
20.1253.43e-06
21.1251.72e-06
22.1258.58e-07
23.1254.29e-07
24.1252.15e-07
25.1251.07e-07
26.1255.36e-08
27.1252.68e-08
28.1251.34e-08
29.1256.71e-09
30.1253.35e-09
31.1251.68e-09
32.1258.38e-10

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).

Enums