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.
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.
Controls include stream distribution shape (uniform, moderately skewed, heavy-tailed), stream length, number of parallel signed counters per group, number of independent groups for the median step, and playback speed, with a live comparison panel showing the running sketch estimate of F2 alongside the exact value.
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.
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.
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.
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 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.