Tag
sketches
- Jul 21, 2026 Counting Distinct Elements with HyperLogLog Registers How a fixed array of small registers estimates cardinality to within about one percent, why the estimator uses a harmonic mean, and how register-wise maximum makes sketches mergeable. algorithms
- Feb 24, 2025 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. data structures
- Dec 10, 2024 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. data structures
- Sep 23, 2023 Frequency Moments and the Tug-of-War Sketch How a random sign vector turns the second frequency moment into a sum of squares, why the estimator is unbiased, and how the same construction generalises to higher moments. algorithms
- Jul 20, 2023 The Streaming Model: One Pass, Sublinear Space, Approximate Answers What the one-pass model forbids, how cash-register and turnstile streams differ, and why exact answers cost linear space while sketches can be merged by addition. algorithms
- Jul 10, 2023 Count-Min Sketch: Why the Minimum of Overestimates Is the Estimate The counter grid, the derivation of width e over epsilon and depth ln of one over delta, and why conservative update shrinks error without changing the guarantee. algorithms