Model

Space of an approximate membership filter

The space advantage of cuckoo filters only exists below about 3%.

floor = lo g_{2} \frac{1}{ε}, Bloom = \frac{1}{l n 2} lo g_{2} \frac{1}{ε} \approx 1.44 lo g_{2} \frac{1}{ε}, cuckoo \approx \frac{lo g _{2} ( 1/ ε ) + 3}{α}

$ε$: False-positive rate; the false-positive rate
$α$: Occupancy; table occupancy, about 0.95

Trade-off: Exactness vs. approximation

How it behaves

One input on the horizontal axis, the others held fixed.

information floorBloomcuckoo (α = 0.95)

Data table

Bits per key by false-positive rate
False-positive rate ε	series	Bits per key
0	information floor	16.6
0	information floor	16.4
0	information floor	16.3
0	information floor	16.1
0	information floor	15.9
0	information floor	15.7
0	information floor	15.5
0	information floor	15.4
0	information floor	15.2
0	information floor	15
0	information floor	14.8
0	information floor	14.6
0	information floor	14.5
0	information floor	14.3
0	information floor	14.1
0	information floor	13.9
0	information floor	13.8
0	information floor	13.6
0	information floor	13.4
0	information floor	13.2
0	information floor	13
0	information floor	12.9
0	information floor	12.7
0	information floor	12.5
0	information floor	12.3
0	information floor	12.1
0	information floor	12
0	information floor	11.8
0	information floor	11.6
0	information floor	11.4
0	information floor	11.3
0	information floor	11.1
0.001	information floor	10.9
0.001	information floor	10.7
0.001	information floor	10.5
0.001	information floor	10.4
0.001	information floor	10.2
0.001	information floor	10
0.001	information floor	9.82
0.001	information floor	9.64
0.001	information floor	9.47
0.002	information floor	9.29
0.002	information floor	9.11
0.002	information floor	8.93
0.002	information floor	8.75
0.003	information floor	8.57
0.003	information floor	8.39
0.003	information floor	8.22
0.004	information floor	8.04
0.004	information floor	7.86
0.005	information floor	7.68
0.006	information floor	7.5
0.006	information floor	7.32
0.007	information floor	7.14
0.008	information floor	6.97
0.009	information floor	6.79
0.01	information floor	6.61
0.012	information floor	6.43
0.013	information floor	6.25
0.015	information floor	6.07
0.017	information floor	5.89
0.019	information floor	5.72
0.022	information floor	5.54
0.024	information floor	5.36
0.028	information floor	5.18
0.031	information floor	5
0.035	information floor	4.82
0.04	information floor	4.64
0.045	information floor	4.47
0.051	information floor	4.29
0.058	information floor	4.11
0.066	information floor	3.93
0.074	information floor	3.75
0.084	information floor	3.57
0.095	information floor	3.39
0.108	information floor	3.21
0.122	information floor	3.04
0.138	information floor	2.86
0.156	information floor	2.68
0.177	information floor	2.5
0.2	information floor	2.32
0	Bloom	24
0	Bloom	23.7
0	Bloom	23.4
0	Bloom	23.2
0	Bloom	22.9
0	Bloom	22.7
0	Bloom	22.4
0	Bloom	22.2
0	Bloom	21.9
0	Bloom	21.6
0	Bloom	21.4
0	Bloom	21.1
0	Bloom	20.9
0	Bloom	20.6
0	Bloom	20.4
0	Bloom	20.1
0	Bloom	19.8
0	Bloom	19.6
0	Bloom	19.3
0	Bloom	19.1
0	Bloom	18.8
0	Bloom	18.6
0	Bloom	18.3
0	Bloom	18
0	Bloom	17.8
0	Bloom	17.5
0	Bloom	17.3
0	Bloom	17
0	Bloom	16.7
0	Bloom	16.5
0	Bloom	16.2
0	Bloom	16
0.001	Bloom	15.7
0.001	Bloom	15.5
0.001	Bloom	15.2
0.001	Bloom	14.9
0.001	Bloom	14.7
0.001	Bloom	14.4
0.001	Bloom	14.2
0.001	Bloom	13.9
0.001	Bloom	13.7
0.002	Bloom	13.4
0.002	Bloom	13.1
0.002	Bloom	12.9
0.002	Bloom	12.6
0.003	Bloom	12.4
0.003	Bloom	12.1
0.003	Bloom	11.9
0.004	Bloom	11.6
0.004	Bloom	11.3
0.005	Bloom	11.1
0.006	Bloom	10.8
0.006	Bloom	10.6
0.007	Bloom	10.3
0.008	Bloom	10
0.009	Bloom	9.79
0.01	Bloom	9.53
0.012	Bloom	9.28
0.013	Bloom	9.02
0.015	Bloom	8.76
0.017	Bloom	8.5
0.019	Bloom	8.25
0.022	Bloom	7.99
0.024	Bloom	7.73
0.028	Bloom	7.47
0.031	Bloom	7.21
0.035	Bloom	6.96
0.04	Bloom	6.7
0.045	Bloom	6.44
0.051	Bloom	6.18
0.058	Bloom	5.93
0.066	Bloom	5.67
0.074	Bloom	5.41
0.084	Bloom	5.15
0.095	Bloom	4.9
0.108	Bloom	4.64
0.122	Bloom	4.38
0.138	Bloom	4.12
0.156	Bloom	3.87
0.177	Bloom	3.61
0.2	Bloom	3.35
0	cuckoo (α = 0.95)	20.6
0	cuckoo (α = 0.95)	20.5
0	cuckoo (α = 0.95)	20.3
0	cuckoo (α = 0.95)	20.1
0	cuckoo (α = 0.95)	19.9
0	cuckoo (α = 0.95)	19.7
0	cuckoo (α = 0.95)	19.5
0	cuckoo (α = 0.95)	19.3
0	cuckoo (α = 0.95)	19.1
0	cuckoo (α = 0.95)	18.9
0	cuckoo (α = 0.95)	18.8
0	cuckoo (α = 0.95)	18.6
0	cuckoo (α = 0.95)	18.4
0	cuckoo (α = 0.95)	18.2
0	cuckoo (α = 0.95)	18
0	cuckoo (α = 0.95)	17.8
0	cuckoo (α = 0.95)	17.6
0	cuckoo (α = 0.95)	17.4
0	cuckoo (α = 0.95)	17.3
0	cuckoo (α = 0.95)	17.1
0	cuckoo (α = 0.95)	16.9
0	cuckoo (α = 0.95)	16.7
0	cuckoo (α = 0.95)	16.5
0	cuckoo (α = 0.95)	16.3
0	cuckoo (α = 0.95)	16.1
0	cuckoo (α = 0.95)	15.9
0	cuckoo (α = 0.95)	15.8
0	cuckoo (α = 0.95)	15.6
0	cuckoo (α = 0.95)	15.4
0	cuckoo (α = 0.95)	15.2
0	cuckoo (α = 0.95)	15
0	cuckoo (α = 0.95)	14.8
0.001	cuckoo (α = 0.95)	14.6
0.001	cuckoo (α = 0.95)	14.4
0.001	cuckoo (α = 0.95)	14.2
0.001	cuckoo (α = 0.95)	14.1
0.001	cuckoo (α = 0.95)	13.9
0.001	cuckoo (α = 0.95)	13.7
0.001	cuckoo (α = 0.95)	13.5
0.001	cuckoo (α = 0.95)	13.3
0.001	cuckoo (α = 0.95)	13.1
0.002	cuckoo (α = 0.95)	12.9
0.002	cuckoo (α = 0.95)	12.7
0.002	cuckoo (α = 0.95)	12.6
0.002	cuckoo (α = 0.95)	12.4
0.003	cuckoo (α = 0.95)	12.2
0.003	cuckoo (α = 0.95)	12
0.003	cuckoo (α = 0.95)	11.8
0.004	cuckoo (α = 0.95)	11.6
0.004	cuckoo (α = 0.95)	11.4
0.005	cuckoo (α = 0.95)	11.2
0.006	cuckoo (α = 0.95)	11.1
0.006	cuckoo (α = 0.95)	10.9
0.007	cuckoo (α = 0.95)	10.7
0.008	cuckoo (α = 0.95)	10.5
0.009	cuckoo (α = 0.95)	10.3
0.01	cuckoo (α = 0.95)	10.1
0.012	cuckoo (α = 0.95)	9.93
0.013	cuckoo (α = 0.95)	9.74
0.015	cuckoo (α = 0.95)	9.55
0.017	cuckoo (α = 0.95)	9.36
0.019	cuckoo (α = 0.95)	9.17
0.022	cuckoo (α = 0.95)	8.99
0.024	cuckoo (α = 0.95)	8.8
0.028	cuckoo (α = 0.95)	8.61
0.031	cuckoo (α = 0.95)	8.42
0.035	cuckoo (α = 0.95)	8.23
0.04	cuckoo (α = 0.95)	8.05
0.045	cuckoo (α = 0.95)	7.86
0.051	cuckoo (α = 0.95)	7.67
0.058	cuckoo (α = 0.95)	7.48
0.066	cuckoo (α = 0.95)	7.29
0.074	cuckoo (α = 0.95)	7.11
0.084	cuckoo (α = 0.95)	6.92
0.095	cuckoo (α = 0.95)	6.73
0.108	cuckoo (α = 0.95)	6.54
0.122	cuckoo (α = 0.95)	6.35
0.138	cuckoo (α = 0.95)	6.17
0.156	cuckoo (α = 0.95)	5.98
0.177	cuckoo (α = 0.95)	5.79
0.2	cuckoo (α = 0.95)	5.6

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
$\frac{lo g _{2} ( 1/ ε ) + 3}{α} bits per key$
Read it in place →