Home▸Algorithms & AI▸AMS Sketch: Estimating Stream Skew in a Sliver of Memory

🎲 AMS Sketch: Estimating Stream Skew in a Sliver of Memory

Explore the AMS (Alon-Matias-Szegedy) Sketch, a randomized streaming algorithm that estimates the second frequency moment F2 of a massive data stream using signed counters and sublinear memory.

Algorithms & AI3DModerate60 FPS

The simulation demonstrates how a handful of independent signed counters, each fed by a stream of items tagged with random plus-one or minus-one signs, converge on average toward the true second frequency moment F2 of the stream, and how averaging and taking the median across repetitions tightens the estimate around the true value even though any single counter fluctuates.

🔬 What It Demonstrates

🎮 How to Use

Choose a stream distribution ranging from uniform to highly skewed, set the number of parallel counters and the number of repetition groups, then run the stream and watch each counter accumulate signed increments in real time; compare the sketch's median-of-means F2 estimate against the exact F2 value computed from full per-item counts to see how accuracy improves as you add more counters.

💡 Did You Know?

Did you know that the same random-sign idea behind the AMS Sketch, where independent random projections preserve squared magnitudes on average, is a discrete cousin of the Johnson-Lindenstrauss lemma used to compress high-dimensional vectors while approximately preserving distances, connecting streaming algorithms to dimensionality reduction in machine learning.

⚙ Under the hood

Explore the AMS (Alon-Matias-Szegedy) Sketch, a randomized streaming algorithm that estimates the second frequency moment F2 of a massive data stream using signed counters and sublinear memory.

streaming algorithmsams sketchfrequency momentsrandomized algorithmsdata streamssketchingnetwork anomaly detectionmedian of means

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install