0 of 23 Parts Published
Main Parts
The core 23-part path: stream models and guarantees, concentration and hashing, approximate counting and sampling, membership filters, cardinality and frequency estimation, heavy hitters, moments, quantiles, similarity/LSH, sliding windows, linear sketches, dimensionality reduction, randomized linear algebra, graph and geometric streaming, distributed sketches, communication and information-theoretic lower bounds, robustness/privacy, then sketch engineering and evaluation.
Part 1
Streaming Models, Guarantees & Complexity
Frame streaming problems before choosing an algorithm.
Read Article →Part 2
Probability, Concentration & Confidence Amplification
Turn random estimators into explicit accuracy and confidence guarantees.
Read Article →Part 3
Hashing, Independence & Pseudorandomness
Use just enough randomness for fast, reproducible sketches.
Read Article →Part 4
Approximate Counting & Stream Sampling
Count and sample streams with sublinear state.
Read Article →Part 5
Membership Filters & Duplicate Detection
Trade bounded false positives for compact membership state.
Read Article →Part 6
Distinct Elements & Set Cardinality
Estimate F0 from hash-order statistics and register patterns.
Read Article →Part 7
Frequency Estimation & Point Queries
Answer point queries with compact hashed counters.
Read Article →Part 8
Heavy Hitters & Frequent Items
Recover frequent items without storing the universe.
Read Article →Part 9
Frequency Moments, Norms & Entropy
Estimate global norms and distribution statistics.
Read Article →Part 10
Quantiles, Ranks & Distribution Summaries
Summarize ranks, quantiles, and distributions with bounded error.
Read Article →Part 11
Similarity, MinHash & Locality-Sensitive Hashing
Estimate similarity and retrieve approximate neighbors.
Read Article →Part 12
Sliding Windows & Time Decay
Make summaries reflect recent rather than lifetime data.
Read Article →Part 13
Linear Sketches, l0-Sampling & Sparse Recovery
Treat sketches as linear measurements of dynamic vectors.
Read Article →Part 14
Dimensionality Reduction
Preserve geometry while reducing dimension.
Read Article →Part 15
Randomized Numerical Linear Algebra
Sketch matrices for regression, low rank, and spectral tasks.
Read Article →Part 16
Graph Streaming
Summarize massive graphs from edge updates.
Read Article →Part 17
Geometric Streams & Coresets
Compress geometric data while preserving objective costs.
Read Article →Part 18
Distributed, Parallel & Mergeable Sketches
Scale sketches across partitions without changing their meaning.
Read Article →Part 19
Communication Complexity & Streaming Lower Bounds
Prove streaming space limits through communication reductions.
Read Article →Part 20
Information-Theoretic & Statistical Lower Bounds
Use entropy and statistical indistinguishability to limit sketches.
Read Article →Part 21
Robustness, Privacy & Adaptive Streams
Protect sketches from adaptive queries and information leakage.
Read Article →Part 22
Practical Sketch Engineering
Turn asymptotic sketches into dependable production components.
Read Article →Part 23
Evaluation, Testing & Algorithm Selection
Select algorithms with evidence rather than headline complexity.
Read Article →0 of 19 Deep Dives Published
Deep Dives
Focused technique write-ups published alongside the part they extend: Chernoff bounds, limited-independence hashing, Morris counting, sampling methods, filter comparisons, HyperLogLog, Count-Min vs. Count Sketch, Misra-Gries/Space-Saving, AMS F2, KLL, sliding-window histograms, l0-sampling, sparse recovery, Johnson-Lindenstrauss, Frequent Directions, dynamic connectivity, communication lower bounds, adaptive attacks, and differential privacy.
Deep Dive
Chernoff Bounds & Confidence Amplification
Derive exponential tails and reliable repetition schemes.
Read Article →Deep Dive
Limited-Independence Hash Families
Construct practical hash families that satisfy proof assumptions.
Read Article →Deep Dive
Morris Approximate Counting
Understand randomized logarithmic-state counting.
Read Article →Deep Dive
Reservoir, Priority & Bottom-k Sampling
Compare uniform and weighted one-pass sampling strategies.
Read Article →Deep Dive
Bloom, Cuckoo & XOR Filters Compared
Choose among Bloom, cuckoo, and XOR filter families.
Read Article →Deep Dive
HyperLogLog Estimator & Corrections
Derive the HLL estimator from registers to corrections.
Read Article →Deep Dive
Count-Min versus Count Sketch
Contrast one-sided l1 error with signed l2 error.
Read Article →Deep Dive
Misra-Gries & Space-Saving Invariants
Prove deterministic frequent-item guarantees.
Read Article →Deep Dive
AMS F2 Estimation
Build the canonical second-moment linear sketch.
Read Article →Deep Dive
KLL Compaction & Rank Guarantees
Understand randomized compaction and near-optimal rank space.
Read Article →Deep Dive
Exponential & Smooth Histograms
Summarize recent history with logarithmic buckets.
Read Article →Deep Dive
l0-Sampling in Dynamic Streams
Return a uniformly random nonzero coordinate after insertions and deletions.
Read Article →Deep Dive
Sparse Recovery from Count-Sketch Measurements
Decode heavy coordinates from hashed signed measurements.
Read Article →Deep Dive
Johnson-Lindenstrauss Proof & Sparse Embeddings
Prove JL and engineer fast sparse projections.
Read Article →Deep Dive
Frequent Directions Matrix Sketch
Maintain a deterministic spectral matrix summary.
Read Article →Deep Dive
Dynamic Graph Connectivity Sketches
Recover spanning forests from turnstile edge streams.
Read Article →Deep Dive
Communication Reduction from INDEX
Learn the reduction template from INDEX to memory lower bounds.
Read Article →Deep Dive
Adaptive Attacks against Linear Sketches
See how feedback can invalidate oblivious guarantees.
Read Article →Deep Dive
Differential Privacy under Continual Observation
Release streaming statistics with event-level privacy over time.
Read Article →0 of 6 Projects Published
Projects & Capstone
Five progressively harder hands-on builds -- a streaming statistics toolkit, a real-time telemetry analyzer, a similarity/deduplication service, a sketch benchmark laboratory, and a streaming matrix/graph lab -- followed by a distributed streaming analytics engine capstone.
Capstone
Streaming Statistics Toolkit
Ship foundational counters, samplers, filters, and summaries behind one API.
Read Article →Capstone
Real-Time Telemetry Analyzer
Build a real-time observability pipeline with bounded memory.
Read Article →Capstone
Similarity & Deduplication Service
Create a streaming near-duplicate detection service.
Read Article →Capstone
Sketch Benchmark Laboratory
Make sketch tradeoffs reproducible and decision-ready.
Read Article →Capstone
Streaming Matrix & Graph Lab
Unify matrix and dynamic-graph sketch experiments.
Read Article →Capstone
Distributed Streaming Analytics Engine
Integrate theory and engineering into a partitioned analytics engine.
Read Article →