compact-quotient-filter.H File Reference

Memory-optimized quotient filter with bit-packed slots. More...

#include <cstdint>
#include <cstddef>
#include <cmath>
#include <algorithm>
#include <utility>
#include <ah-errors.H>
#include <bitArray.H>
#include <hash-fct.H>

Include dependency graph for compact-quotient-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_Quotient_Filter< T >
	Memory-optimized quotient filter with bit-packed slots. More...

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

Detailed Description

Memory-optimized quotient filter with bit-packed slots.

This is a space-optimized variant of Aleph::Quotient_Filter that uses bit-packing to store slot metadata and remainders compactly. Instead of storing each slot in a full uint64_t, slots are packed into a BitArray using exactly 3 + r bits per slot.

Space Savings

With r=8 remainder bits:

• Standard Quotient_Filter: 64 bits/slot
• Compact_Quotient_Filter: 11 bits/slot (3 metadata + 8 remainder)
• 82% memory reduction

With 2^20 slots (1M slots):

• Standard: 8 MB
• Compact: ~1.4 MB

Performance Trade-off

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

Template Parameters

T	Element type. Must be hashable via murmur3hash(T, seed).

See also

quotient-filter.H for the standard (faster) variant.

Author

Leandro Rabindranath Leon

Definition in file compact-quotient-filter.H.