aleph_filter/lib.rs
1//! # Aleph Filter
2//!
3//! ## Overview
4//!
5//! The Aleph Filter is a probabilistic data structure for approximate membership queries with:
6//! - **O(1) expected insertion and lookup time**
7//! - **Tunable false positive rate (FPR)** without cryptographic hashing
8//! - **Automatic expansion** with fingerprint bit sacrifice
9//! - **Deletion support** via tombstone markers
10//! - **Compact memory usage** (~1.3-2 bits per item for typical FPR ranges)
11//!
12//! ## Quick Start
13//!
14//! ```
15//! use aleph_filter::AlephFilter;
16//!
17//! let mut filter = AlephFilter::new(1000, 0.01); // 1000 items, 1% FPR
18//! filter.insert(b"hello");
19//! assert!(filter.contains(b"hello"));
20//! filter.delete(b"hello");
21//! ```
22//!
23//! ## Architecture
24//!
25//! - **`hash`**: Hash splitting into quotient (slot index) and remainder (fingerprint)
26//! - **`slot`**: 64-bit packing of fingerprint + length, special markers (void, tombstone)
27//! - **`metadata`**: Per-slot flags (occupied, continuation, shifted) for cluster/run tracking
28//! - **`aleph_filter`**: Main quotient filter with insertion, lookup, deletion, and expansion
29//!
30//! ## Key Concepts
31//!
32//! ### Quotient Filter Terminology
33//! - **Canonical slot**: Hash-determined target position for a key
34//! - **Run**: Sequence of slots sharing the same canonical slot
35//! - **Cluster**: Sequence of consecutive occupied or shifted slots
36//! - **Quotient**: Low-order hash bits indicating canonical slot
37//! - **Remainder (Fingerprint)**: High-order hash bits stored as compact fingerprint
38//!
39//! ### Expansion
40//! When load factor exceeds threshold (0.9):
41//! 1. Double the slot count
42//! 2. Increment quotient width by 1 bit
43//! 3. Sacrifice 1 bit per entry from fingerprints
44//! 4. Re-insert using extracted bit to determine new canonical slots
45//!
46//! ## Files
47//!
48//! - `hash.rs` - Hash functions and utilities
49//! - `slot.rs` - Compact 64-bit slot storage
50//! - `metadata.rs` - Per-slot metadata flags
51//! - `aleph_filter.rs` - Main filter implementation
52
53pub mod hash;
54pub mod metadata;
55pub mod slot;
56mod aleph_filter; // private: users can't access the module directly
57
58// pub mod aleph_filter;
59// pub use aleph_filter::AlephFilter;
60
61pub use aleph_filter::AlephFilter;
62
63pub mod prelude {
64 pub use crate::AlephFilter;
65}