___           ___       ___           ___           ___     
     /\  \         /\__\     /\  \         /\  \         /\  \    
    /::\  \       /:/  /    /::\  \       /::\  \        \:\  \   
   /:/\:\  \     /:/  /    /:/\:\  \     /:/\:\  \        \:\  \  
  /::\~\:\  \   /:/  /    /::\~\:\  \   /::\~\:\  \       /::\  \ 
 /:/\:\ \:\__\ /:/__/    /:/\:\ \:\__\ /:/\:\ \:\__\     /:/\:\__\
 \/__\:\/:/  / \:\  \    \:\~\:\ \/__/ \/__\:\/:/  /    /:/  \/__/
      \::/  /   \:\  \    \:\ \:\__\        \::/  /    /:/  /     
       \/__/     \:\  \    \:\ \/__/        /:/  /     \/__/      
                  \:\__\    \:\__\         /:/  /                 
                   \/__/     \/__/         \/__/                  

Ribbon filters with pleated construction — a one-pass, cache-window reordering that builds space-optimal filters at close to Bloom-filter speed, and roughly twice as fast as building in arrival order at scale. An Integrallis project; companion to the paper "Ribbon Catches Bloom: Pleated Construction at Bloom Speed."

Two filter families — homogeneous RibbonFilter (w=64) and standard StdRibbon (w=128, the RocksDB shape) — each with arrival / pleated / parallel construction (all bit-identical), tunable false-positive rate, arbitrary hashable keys, batch queries, and serialization. Every kernel component is differentially gated byte-for-byte against the reference C++ implementation.

A ribbon filter answers approximate set membership — "is this key possibly in the set?" — in about 7.6 bits per key at a ~0.8% false-positive rate, well under a Bloom filter's memory for the same accuracy. The cost has always been construction: ribbon filters are built by solving a banded linear system, and doing that in arrival order makes every key a random jump through a table far larger than cache. Pleating groups keys into cache-sized windows with a single counting pass first, so the banding stays local.

use pleat::filter::RibbonFilter;

let keys: Vec<u64> = /* your 64-bit key hashes */ vec![10, 20, 30];
let filter = RibbonFilter::from_keys_pleated(&keys);

assert!(filter.contains(20));           // members always present
// filter.contains(999) is false with ~99.2% probability

let bytes = filter.to_bytes();          // persist
let restored = RibbonFilter::from_bytes(&bytes).unwrap();

Construction variants, all producing the bit-identical filter (banding is order-independent):

RibbonFilter::from_keys(&keys);              // arrival order (reference default)
RibbonFilter::from_keys_pleated(&keys);      // pleated: ~2x faster at scale
RibbonFilter::from_keys_parallel(&keys, 8);  // slot-range parallel (feature "parallel")
RibbonFilter::from_hashable(&["a", "b"]);    // any Hash type (strings, tuples, ...)

The *_hashable helpers use Rust's Hash trait and are intended for values produced and consumed by the same crate/toolchain. For durable or cross-language filters, define a stable application encoding and hash it to u64, then use the from_keys/contains APIs.

Query one key or a batch (batch prefetches for throughput):

f.contains(key);
f.contains_hashable(&"some string");
let mut out = vec![false; probes.len()];
f.contains_batch(&probes, &mut out);

Tune the false-positive rate with the result-width parameter R (~2^-R):

use pleat::filter::Ribbon;
let low_fpr = Ribbon::<10>::from_keys_pleated(&keys);   // ~0.1% FPR, ~10.9 bits/key
// RibbonFilter is the alias Ribbon<7> (~0.8% FPR, ~7.6 bits/key)

Measured construction cost

On an Intel i9-14900HX, ns/key (means of 10, cargo bench --bench construct; raw criterion output committed under benches/):

n keys	arrival	pleated	parallel 8t
1,000,000 (table fits in L3)	23.8	26.1	21.9
10,000,000 (table exceeds L3)	60.4	26.0	24.4

Pleating pays off once the banding table exceeds cache (2.3x at 10M keys here); below that crossover it costs slightly more than arrival order, as expected. These are this crate's own numbers; the paper's headline figures are measured on the reference C++ kernel.

Query, serialization, and accuracy

Same machine, 10M-key filter (cargo bench --bench query --bench serde):

• Query (miss-dominated), ns per lookup: homogeneous 17.4 scalar / 15.4 batch; standard 24.2 scalar. contains_batch prefetches, giving ~12% over scalar for homogeneous.
• Serialization: validated from_bytes (checksum + full field validation) runs at ~1.2 GB/s — validation is not a bottleneck.
• False-positive rate at r=7, measured over 2M absent probes: 0.783% (theory 2⁻⁷ = 0.781%); a statistical test asserts this on every cargo test run.

Correctness

Every kernel component is differentially gated against the reference ribbon implementation (fastfilter_cpp, by the ribbon authors, RocksDB-derived). tools/vecgen.cc emits committed test vectors — per-key hash/start/coefficient values, a full-build solution fingerprint, and query outcomes — and the Rust tests assert byte-exact agreement:

• hashing reproduces the reference per-key values on 1000 vectors;
• banding + back-substitution reproduce the reference's serialized solution byte-for-byte;
• queries reproduce the reference's present/absent outcomes;
• pleated and parallel builds are verified bit-identical to the sequential build.

Nothing in the kernel is written from memory; several subtle transcription errors were caught, including the fact that homogeneous back-substitution fills unconstrained rows with pseudorandom data, not zero, which preserves the false-positive rate.

Scope

This release implements homogeneous ribbon at w=64 with a tunable result width R (columns): the false-positive rate is ~2^-R and the size is ~1.09·R bits per key, so R=7 gives ~0.8% FPR at ~7.6 bits/key — the variant used as the reference benchmark — and R=10 gives ~0.1% at ~10.9 bits/key. Gated against reference vectors for R in {5, 7, 8, 10}. Keys are 64-bit; hash your keys to u64 first.

Standard ribbon (w=128) — the RocksDB production shape — is also available via StdRibbon, with the same pleated and arrival construction (bit-identical, seed-retry included) and slightly tighter space:

use pleat::filter::StdRibbon;
let f = StdRibbon::<8>::from_keys_pleated(&keys).expect("solves");  // ~0.4% FPR
assert!(f.contains(keys[0]));

Reproduce

cargo test --all-features         # differential gate + property tests
cargo test --no-default-features # serial-only feature configuration
cargo clippy --all-features --all-targets -- -D warnings
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps --all-features
cargo deny --all-features check   # advisories, licenses, sources, dependency policy
cargo bench --bench construct     # construction benchmark
cargo +nightly fuzz run decode -- -max_total_time=30
./reproduce.sh                    # regenerate reference vectors + run gate + bench

License

MIT OR Apache-2.0. The ribbon kernel is ported from RocksDB / fastfilter_cpp (Apache-2.0); ported files carry attribution.