compact-cuckoo-filter.H File Reference

Memory-optimized Cuckoo filter with bit-packed fingerprints. More...

#include <cassert>
#include <cstddef>
#include <cmath>
#include <optional>
#include <random>
#include <algorithm>
#include <hash-fct.H>
#include <ah-errors.H>
#include <ahUtils.H>
#include <tpl_array.H>
#include <bitArray.H>

Include dependency graph for compact-cuckoo-filter.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >
	Memory-optimized Cuckoo Filter with bit-packed fingerprints. More...
struct	Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Bucket
struct	Aleph::Compact_Cuckoo_Filter< T, FingerprintBits, EntriesPerBucket >::Victim
	Victim entry: a fingerprint that was displaced during a failed insert. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Memory-optimized Cuckoo filter with bit-packed fingerprints.

This is a space-optimized variant of Aleph::Cuckoo_Filter that uses bit-packing to store fingerprints compactly. Instead of storing each fingerprint in a full uint32_t, fingerprints are packed into a BitArray using exactly FingerprintBits bits per entry.

Space Savings

With 8-bit fingerprints and 4 entries per bucket:

• Standard Cuckoo_Filter: 16 bytes/bucket (4 × 32 bits)
• Compact_Cuckoo_Filter: 4 bytes/bucket (4 × 8 bits)
• 75% memory reduction

Performance Trade-off

Bit-packing requires shift/mask operations on every fingerprint access, which can be 10-30% slower than direct array indexing. Use this variant when memory is constrained and the performance cost is acceptable.

Template Parameters

T	Item type.
FingerprintBits	Number of bits per fingerprint (e.g., 8, 12, 16).
EntriesPerBucket	Associativity (number of slots per bucket).

False Positive Rate

The theoretical FP rate is approximately 2 * EntriesPerBucket / 2^FingerprintBits. With the defaults (8-bit fingerprints, 4 entries per bucket) this is ~3.1 %.

Note

Inserting the same item twice stores two fingerprints. After a single remove() the filter will still report the item as present. Callers that need set semantics should guard with contains() before inserting.

See also

Cuckoo_Filter for the standard (faster) variant.

Author

Leandro Rabindranath León

Definition in file compact-cuckoo-filter.H.