Count-min sketch guarantee

How it behaves

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

Worked examples, recomputed

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

• ε = 0.001 → w = 2,719
• δ = 1% → d = 5
• ≈ 13,600 counters ≈ 54 KB
• 10⁹ events, ε = 0.001 → ± 10⁶

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?

  $$w=\lceil e/\epsilon \rceil ,d=\lceil \ln (1/\delta )\rceil :\text{error}\le \epsilon N$$

  Read it in place →