Data Structures · Cluster
Probabilistic Structures
Filters, sketches, and bounded-error membership.
- 01 How a Bloom Filter Trades Bits for a False-Positive Rate The bit-array layout behind Bloom filters, the derivation of the false-positive probability, and how the bits-per-key budget fixes the achievable error.
- 02 Counting Bloom Filters and the Price of Supporting Deletion Replacing bits with small saturating counters makes removal possible, but residue, overflow, and spurious decrements each introduce a distinct failure.
- 03 Cuckoo Filters: Fingerprint Placement and the Load-Factor Ceiling How two-bucket cuckoo hashing with stored fingerprints supports deletion in less space than a counting Bloom filter, and why displacement fails near full occupancy.
- 04 Deriving k Bloom Filter Probes from Two Hash Words Why the h1 + i·h2 construction preserves the false-positive bound, where the independence assumption breaks, and what enhanced double hashing repairs.
- 05 Blocked and Partitioned Bloom Filters for Cache-Resident Probes Confining the k probes of a filter to one cache line, or to one slice of the array, changes the error rate by a measurable factor and the memory behaviour by an order of magnitude.
- 06 HyperLogLog: Estimating Cardinality from a Register Array How stochastic averaging over harmonic means turns a fixed array of small registers into a cardinality estimate with roughly 1.04/sqrt(m) relative error.
- 07 Count-Min Sketches and the Bias of Always Rounding Up A fixed grid of counters answers frequency queries with a one-sided error bounded by the stream length, and conservative updates cut the excess without changing the guarantee.
- 08 Merging Probabilistic Sketches Across Shards Union and sum are the only safe merge operations, they require identical parameters and hash seeds, and the error of a merged estimate grows in a way single-sketch sizing hides.
- 09 Growing and Ageing a Filter Without Rebuilding It Scalable Bloom filters add slices with tightening error instead of rehashing, and decaying sketches replace deletion with a time constant that bounds the effective window.
- 10 Composing Probabilistic Checks: Why Error Budgets Do Not Add Chaining filters and sketches multiplies false positives instead of summing them, correlation between stages breaks the union bound, and the pipeline error is dominated by the weakest stage.