Parameter calculator
Working backwards. Say how many items you expect and how much error you can live with, and this gives you the structure to build and what it will cost in memory.
Where this is actually used
This is how these actually get sized in practice. Nobody picks a bit count directly — they know roughly how many items are coming and what error rate the system can absorb, and the size falls out of a formula. Both formulas are shown here, not just their results.
How it works
State what you expect and what you can tolerate. Get the structure to build, the formula it came from, and what it costs.
Parameters
Bloom filter
m — bits
9,585,059
k — hashes
7
Memory
1.14 MiB
Bits per item
9.59
Predicted
1.00%
Against an exact structure
13.4×
An exact Set of the same n, at 16 bytes per key, would take 15.26 MiB
How that number was reached
m = −n·ln ε / (ln 2)²
= −1,000,000 × (−4.6052) / 0.4805
= 9,585,059 bits
ln ε is negative, so the minus makes m positive: a smaller ε means a larger m. The (ln 2)² comes from the array being half full at the optimum — the fullness that balances "more bits set means more evidence" against "more bits set means more accidents".
k = (m/n)·ln 2
= (9,585,059 / 1,000,000) × 0.6931
= 7 hashes
k has an optimum rather than a best-is-most: each extra hash is another chance to catch an absent item, and another bit set on every insert. The two cross at (m/n)·ln 2, which is exactly the k that fills the array half way.
Sizes are rounded up to whole bits, whole counters, or the next power of two, so the delivered error is always at least as good as the target — never worse.
Burton H. Bloom, CACM 13(7), 1970
Count-Min sketch
w — width
272
d — depth
5
Memory
5.3 KiB
1,360 × Uint32
Overestimate bounded by ε·N
1.00% × N
The error is additive over the whole stream, not over the item’s own count. A rare item in a long stream can be overestimated by far more than it truly appears.
How that number was reached
w = ⌈e/ε⌉
= ⌈2.7183 / 0.01⌉
= 272 columns
e appears because the bound is a Markov-inequality argument on the expected collision mass in a row; e/ε is the width at which the expected overestimate falls under ε·N.
d = ⌈ln(1/δ)⌉
= ⌈ln(1 / 0.01)⌉ = ⌈4.6052⌉
= 5 rows
Each row is an independent estimate that can only be too high. Rows fail independently, so d of them fail together with probability at most (1/e)^d — set that below δ and you get d = ln(1/δ).
Sizes are rounded up to whole bits, whole counters, or the next power of two, so the delivered error is always at least as good as the target — never worse.
Cormode & Muthukrishnan, J. Algorithms 55(1), 2005
HyperLogLog
p — precision
12
m — registers
4,096
Memory
4.0 KiB
one byte per register — packed to 6 bits, real implementations use 25% less
Standard error 1.04/√m
1.63%
Against an exact structure
3906×
An exact Set of the same n, at 16 bytes per key, would take 15.26 MiB
How that number was reached
m = (1.04/σ)²
= (1.04 / 0.02)² = 2704
= 4,096 registers (2^12)
The standard error of the estimator is 1.04/√m, so the registers needed grow with the square of the accuracy you want: halving the error costs four times the memory.
σ = 1.04/√m
= 1.04 / √4,096
= 1.63%
m must be a power of two because the register index is read off the top p bits of the hash. The precision is therefore rounded up, and the error you get is a little better than the one you asked for.
Flajolet, Fusy, Gandouet & Meunier, AofA 2007
Note what is missing: n. HyperLogLog’s memory does not depend on how many items you expect. The same 16 KiB counts a thousand distinct values or a billion, and only the relative error is fixed.
Cuckoo filter
f — fingerprint bits
10
Buckets
524,288
× 4 entries each
Memory
4.00 MiB
whole bytes per entry — packed to f bits, real implementations use less
Capacity
1,992,294
inserts are refused past this, not degraded
How that number was reached
f = ⌈log₂(2b/ε)⌉
= ⌈log₂(2×4 / 0.01)⌉
= 10 bits
Each bucket holds b fingerprints and a query checks two buckets, so an absent item has about 2b chances to match one of 2^f possible fingerprints.
buckets = 2^⌈log₂(n/αb)⌉
= 2^⌈log₂(1,000,000 / (α × 4))⌉
= 524,288
Sizes are rounded up to whole bits, whole counters, or the next power of two, so the delivered error is always at least as good as the target — never worse.
Fan, Andersen, Kaminsky & Mitzenmacher, CoNEXT 2014
Ideal bits per item, packed
Cuckoo 10.53 · Bloom 9.59
At this ε, Bloom needs fewer bits. Cuckoo overtakes it below about ε = 0.2%.