Cuckoo Filter: Practically Better Than Bloom
Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies, 2014 · paper · Computer science
Proposes the cuckoo filter, a data structure for approximate set membership tests that supports adding and removing items. It is reported to beat Bloom filters in lookup speed and, at low false-positive rates, in space, and to outperform deletion-capable variants.
Checked: PDF from cs.cmu.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
7 findings
Substance Section 2.1 prints the static-set fingerprint length as "(of length ⌈1/ϵ⌉ bits)"; it should be ⌈log2(1/ϵ)⌉ bits.
- p. 2 Section 2.1, paragraph on the information-theoretic optimum
(of length ⌈1/ϵ⌉
- p. 2 Section 2.1, paragraph on information-theoretic optimum
by using fingerprints (of length ⌈1/ϵ⌉ bits)
- p. 2 Section 2.1
(of length ⌈1/ϵ⌉ bits)
- p. 2
fingerprints (of length ⌈1/ϵ⌉ bits)
Judge's note: The page 2 image shows ⌈1/ϵ⌉ with no log, so this is not an extraction artefact. The sentence just before gives the information-theoretic minimum as log2(1/ϵ) bits per item. Fingerprints of 1/ϵ bits would be 100 bits at ϵ = 1%, nowhere near optimal.
Second check: another model agreed
Report a problem with this finding
Substance Section 4 says "recall that Bloom filters use a constant (approximately ln(1/ϵ) bits) per item", but the paper's own figure is 1.44 log2(1/ϵ) ≈ 2.08 ln(1/ϵ) bits (Sec. 2.1, Table 2, Sec. 6).
- p. 7 Section 4, paragraph after Eq. (3)
approximately ln(1/ϵ) bits) per item
- p. 2 Section 2.1
can store each item using 1.44 log2(1/ϵ) bits
- p. 7 Section 4, after Eq. (3)
recall that Bloom filters use a constant (approximately ln(1/ϵ) bits) per item
- p. 7 Section 4 after Eq. 3
approximately ln(1/ϵ) bits
Judge's note: The p.7 image shows ln(1/ϵ). By the paper's own formula, 1.44 log2(1/ϵ) = ln(1/ϵ)/(ln 2)^2 ≈ 2.08 ln(1/ϵ). At ϵ=1%, ln(100) ≈ 4.6 bits, which is even below the stated information-theoretic bound of log2(100) ≈ 6.64. The same page says roughly 10 bits are needed at ϵ=1%.
Second check: another model agreed
Report a problem with this finding
Substance The testbed L3 cache is given as '12MB L3 cache' in the Experiment Setup and as 'the L3 cache (20 MB) in our testbed' in Section 7.2.
- p. 10 Section 7, Experiment Setup
L5640@2.27GHz, 12MB L3 cache
- p. 10 Section 7.2, Different Workloads
L3 cache (20 MB) in our testbed
- p. 10 Experiment Setup
12MB L3 cache
- p. 10 Section 7.2
L3 cache (20 MB)
Only the authors can say what is right here.
Judge's note: Both statements are on page 10 and describe the same machine ('two Intel Xeon processors (L5640@2.27GHz, 12MB L3 cache)'). The paper gives no per-socket or total explanation that would yield 20 MB: two sockets give 24 MB. Only the authors can say which figure is intended.
Second check: another model agreed
Report a problem with this finding
Substance 'The dl-CBF outperforms the ss-CF, but 30% slower than a BF.' In Figure 5 the dl-CBF lookup throughput is at or above the standard BF at every p.
- p. 11 Section 7.2, Different Workloads
The dl-CBF outperforms the ss-CF, but 30% slower than a BF.
- p. 11 Figure 5
lookup throughput (million OPS)
Only the authors can say what is right here.
Judge's note: In Figure 5 (page 11), dl-CBF is about 8.5, 7.8, 7.4, 7.5 and 8.0 MOPS and BF about 8.3, 6.0, 5.3, 5.0 and 4.9 MOPS across p = 0–100%. dl-CBF is therefore never 30% slower than BF. A gap of roughly 30% exists against blk-BF at p=0 (~12) or against CF (~10.5–12). The paper defines BF and blk-BF as separate labels. Only the authors can say which filter was meant.
Second check: another model agreed
Report a problem with this finding
Reference or label The Table 2 caption says "Space and lookup cost of Bloom filters and three cuckoo filters", but the table lists only two cuckoo filter variants (cuckoo filter; cuckoo filter w/ semi-sort).
- p. 8 Table 2 caption
Space and lookup cost of Bloom filters and three cuckoo filters.
Judge's note: The p.8 image shows three rows: the space-optimized Bloom filter, the cuckoo filter, and the cuckoo filter w/ semi-sort. That is two cuckoo filters.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [6] lists the same author twice: 'A. Broder, M. Mitzenmacher, and A. Broder.'
- p. 13 Reference [6]
A. Broder, M. Mitzenmacher, and A. Broder.
- p. 13 Ref [20]
Proc. ASM-SIAM Symposium on Discrete Algorithms
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the survey's author list is Broder and Mitzenmacher only. The page 13 image shows 'A. Broder' as both first and third author, which is evidently a duplication.
Second check: another model agreed
Report a problem with this finding
Wording Evaluation Summary: 'It also makes lookups, inserts, and deletes slower, but still faster than conventional BFs.' Table 3 and Figures 5–6 show ss-CF slower than BF in several regimes, and BFs do not support deletes.
- p. 12 Evaluation Summary
slower, but still faster than conventional BFs
- p. 10 Table 3, constr. speed row
3.13
- p. 12 Section 7.4, Evaluation Summary
It also makes lookups, inserts, and deletes slower, but still faster than conventional BFs.
- p. 11 Section 7.2 text on Figure 5
the ss-CF still outperforms BFs when more than 25% of queries are positive
Only the authors can say what is right here.
Judge's note: Table 3 (p10) gives construction speed ss-CF 3.13 vs BF 3.91 M keys/s. In Fig 5, ss-CF lookups (~6.4) are below BF (~8.3) at p=0, and Sec 7.2 itself qualifies the claim to 'more than 25% of queries are positive'. In Fig 6a (negative lookups), ss-CF (~6.5) is below BF (~8.5–17) at all occupancies. Page 10 states that standard BFs do not support deletion. The unqualified summary sentence is not supported as written.
Second check: another model agreed
Report a problem with this finding
17 minor (typos and the like; most checked by the judge only)
Wording The ϵ < 3% space advantage is stated for cuckoo filters with no qualifier (intro item 4: "It uses less space than Bloom filters ... if the target false positive rate ϵ is less than 3%"; Fig. 4 caption; Conclusion), but Section 6 limits it to "cuckoo filters with semi-sorting".
- p. 1 Introduction, advantage 4
It uses less space than Bloom filters in many practical applications, if the target false positive rate ϵ is less than 3%.
- p. 2 Introduction, first line of col. 1
a cuckoo filter uses less space while supporting deletion than a non-deletable, space-optimized Bloom filter when ϵ < 3%.
- p. 9 Figure 4 caption
For low false positive rates (< 3%), cuckoo filters require fewer bits per element than the space-optimized Bloom filters.
- p. 12 Conclusion
better space efficiency for applications requiring low false positive rates (ϵ < 3%)
Only the authors can say what is right here.
Judge's note: Section 6 (p.9) says "Thus cuckoo filters with semi-sorting are more space efficient than Bloom filters when ϵ < 3%." Using the Table 2 formulas (p.8) with α = 95.5%, the plain cuckoo filter, (log2(1/ϵ)+3)/α, crosses 1.44 log2(1/ϵ) at log2(1/ϵ) ≈ 8, i.e. ϵ ≈ 0.39%. At ϵ = 1% it needs about 10.1 bits against about 9.57 for Bloom. The semi-sorted variant crosses near ϵ ≈ 2.5–3%, which matches the Fig. 4 annotation "Crossover: 7.2 bits (3% false positive rate)". At this resolution I cannot tell exactly where the blue (plain CF) curve meets the red one in Fig. 4, and the figure uses empirical load factors. So I am raising this as a wording and qualification query, not a hard error.
Second check: another model agreed
Report a problem with this finding
Wording The intro says d-left counting Bloom filters "are still 1.5× larger", while Table 1 gives "1.5x ∼ 2x" and Section 2.1 gives "usually requiring 1.5 − 2× the space".
- p. 1 Introduction, col. 2
which are still 1.5× larger
- p. 2 Table 1
1.5x ∼ 2x
Judge's note: Checked p.1 and p.2. The intro gives only the lower end of the range used on p.2. "Still 1.5× larger" can be read as "at least", so this is a minor consistency point.
Second check: another model agreed
Report a problem with this finding
Wording Quotient filter overhead is "10 ∼ 25% more space than a comparable standard Bloom" in the text but "1x ∼ 1.2x" in Table 1 (same page).
- p. 2 Section 2.1, Quotient filters
10 ∼ 25% more space than a comparable standard Bloom
- p. 2 Table 1, quotient row
1x ∼ 1.2x
- p. 2 Section 2.1 quotient filters
10 ∼ 25% more space
Judge's note: Both are on the p.2 image. The text range of 1.10–1.25× does not match the table's 1.0–1.2×. Table 1 is qualitative and may be rounded, so this is an observation.
Second check: another model agreed
Report a problem with this finding
Wording Section 2.1 says without qualification "Cuckoo filters achieve higher space efficiency and performance than these data structures", but Table 3 and Section 7 report that blk-BF has the highest construction rate (7.64 vs CF 5.00 Mkeys/s).
- p. 2 Section 2.1, first paragraph
Cuckoo filters achieve higher space efficiency and performance than these data structures.
- p. 10 Table 3, constr. speed
7.64
Only the authors can say what is right here.
Judge's note: Table 3 (p.10) bolds blk-BF at 7.64 for construction speed. Section 7.1 says "the blk-BF achieves the highest construction rate". The Evaluation Summary says CF construction is "faster than other filters except the blk-BF". The blanket 'performance' claim on p.2 is therefore broader than the paper's own results.
Second check: another model agreed
Report a problem with this finding
Wording "These data structures are evaluated empirically in Section 7" refers to the Table 1 structures, but the standard counting Bloom filter is not among the filters evaluated in Section 7 (BF, blk-BF, QF, dl-CBF, CF, ss-CF).
- p. 2 Section 2.1, first paragraph
These data structures are evaluated empirically in Section 7.
- p. 9 Section 7, list of compared filters
we implemented four other filters for comparison
Judge's note: Checked the Table 1 rows on p.2 and the Section 7 list on p.9 ("four other filters for comparison": BF, blk-BF, QF, dl-CBF). The counting Bloom filter is left out.
Second check: another model agreed
Report a problem with this finding
Wording 'the false positive rate of the blocked filter is 2× higher than the BF and 4× higher than the best CF': Table 3 gives 0.43% vs 0.09% (ss-CF), a ratio of about 4.8.
- p. 10 Section 7.1
is 2× higher than the BF and 4× higher than the best CF
Judge's note: Table 3 on page 10 gives blk-BF 0.43%, BF 0.19% and ss-CF 0.09%. 2× is a fair rounding of 2.26. 4× understates the ratio of 4.78, which is closer to 5×. These are informal approximations, so this is minor.
Second check: another model agreed
Report a problem with this finding
Wording 'the ss-CF still outperforms BFs when more than 25% of queries are positive' holds only for the standard BF; in Figure 5 blk-BF is above ss-CF at every p.
- p. 11 Section 7.2
ss-CF still outperforms BFs when more than 25% of queries are positive
Judge's note: In Figure 5, ss-CF is about 6 MOPS and BF about 6.0, 5.3, 5.0 and 4.9 for p ≥ 25%, so the claim holds against BF. blk-BF (about 9–12) stays above ss-CF throughout. The plural 'BFs' therefore overstates the claim.
Second check: another model agreed
Report a problem with this finding
Typo Subject–verb disagreement: "Quotient filters uses a technique similar to linear probing" should read "use".
- p. 2 Section 2.1, Quotient filters
Quotient filters uses a tech-
- p. 2 Section 2.1, Quotient filters
Quotient filters uses a technique
Judge's note: Seen on the p.2 image, Section 2.1, Quotient filters paragraph.
Second check: none (judge only)
Report a problem with this finding
Typo The Figure 1(c) subcaption is garbled: "A cuckoo filter, two hash per item and functions and four entries per bucket" should read "two hash functions per item and four entries per bucket".
- p. 3 Figure 1(c) subcaption
two hash per item and functions and four entries per bucket
- p. 3 Figure 1(c) caption
A cuckoo filter, two hash per item and functions and four entries per bucket
Judge's note: The crop of p.3 shows the words in this order in the rendered caption.
Second check: none (judge only)
Report a problem with this finding
Typo The fingerprint threshold for 95% load at m=2^30 is given as "fingerprints that are 6 bits or larger" (p.6) and as "once fingerprints exceed six bits" (p.7).
- p. 6 Section 4 intro
fingerprints that are 6 bits or larger
- p. 7 Section 4, Empirical Evaluation
once fingerprints exceed six bits
Judge's note: In Fig. 2(a) the m=2^30 curve reaches about 0.95 at f≈6, which fits "6 bits or larger". "Exceed six bits" is loose wording for the same threshold.
Second check: none (judge only)
Report a problem with this finding
Typo Extra words: "to store fingerprints in a cuckoo filter to leads to a lower bound" (Sec. 4) and "when the these filters are filled" (Sec. 7.2).
- p. 6 Section 4, first sentence
in a cuckoo filter to leads to a lower bound
- p. 11 Sec 7.2
when the these filters
Judge's note: Both appear on the page images (p.6, first sentence of Sec. 4; p.11, Different Occupancy paragraph).
Second check: none (judge only)
Report a problem with this finding
Typo "has almost no return in term of improving the load factor" should read "in terms of".
- p. 7 Section 4, Empirical Evaluation
no return in term of improving the load factor
Judge's note: Seen on the p.7 image, Empirical Evaluation paragraph.
Second check: none (judge only)
Report a problem with this finding
Typo Comma splice: 'from 0.19% to 0.09%, On the other hand' should end the sentence with a full stop.
- p. 10 Section 7.1
from 0.19% to 0.09%, On the other hand
Judge's note: The page 10 image, Sec 7.1 second paragraph, shows the comma followed by a capitalised 'On'.
Second check: none (judge only)
Report a problem with this finding
Typo Subject–verb disagreement: 'The d-left counting Bloom filter have the same number of hash table entries' (should be 'has').
- p. 10 Section 7.1
d-left counting Bloom filter have the same number of hash
Judge's note: I confirmed the wording on the page 10 image, Sec 7.1.
Second check: none (judge only)
Report a problem with this finding
Typo Duplicated determiner: 'when the these filters are filled'.
- p. 11 Section 7.2, Different Occupancy
when the these filters are filled
Judge's note: I confirmed it on the page 11 image, 'Different Occupancy' paragraph.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [20] gives the venue as 'Proc. ASM-SIAM Symposium on Discrete Algorithms, SODA'; this should be ACM-SIAM.
- p. 13 Reference [20]
Proc. ASM-SIAM Symposium on Discrete
- p. 13 Reference [20]
Proc. ASM-SIAM Symposium on Discrete Algorithms
Judge's note: The page 13 image shows 'ASM-SIAM' in [20]. Reference [13] in the same list correctly writes 'ACM-SIAM Symposium on Discrete Algorithms'.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [8] journal is printed as 'IEEE Transactions on Computer'.
- p. 13 Reference [8]
IEEE Transactions on Computer
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the journal title is 'IEEE Transactions on Computers'. The page 13 image shows 'Computer' in [8].
Second check: none (judge only)