Algorithms · Cluster
Streaming Algorithms
Sublinear sketches over unbounded input.
- 01 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.
- 02 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.
- 03 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.
- 04 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.
- 05 Heavy Hitters with Misra-Gries Counters and Space-Saving Buckets Two deterministic summaries that find every item exceeding a fraction of the stream, why decrementing all counters preserves the guarantee, and how their error differs in direction.
- 06 Reservoir Sampling and Priority Sampling on a Single Pass How to hold a uniform sample of a stream of unknown length with one pass, how priority sampling generalises it to weighted elements with unbiased totals, and where the sample stops being uniform.
- 07 Sliding Windows and Exponential Histograms for Recent Data Why a window over the last W items needs a different summary from a whole-stream sketch, how bucket merging bounds error to a constant factor, and what late-arriving data does to the guarantee.
- 08 Linear Sketches and Recovering Sparse Signals from Bucket Measurements How a sketch that only stores bucket sums can still return the identities of heavy items, why recovery needs a median over rows, and what the restricted isometry property guarantees.
- 09 Quantile Summaries: Greenwald-Khanna Bounds and the KLL Compactor How a deterministic summary tracks ranks within a guaranteed error using tuple invariants, and how randomised compaction reaches constant space per item with a smaller constant.
- 10 Triangles and Connectivity in Edge-Stream Graphs Why graph streams get n polylog n space rather than sublinear space, how wedge sampling estimates triangle counts, and how l0 samplers build spanning forests without storing edges.