AMS Sketch: Estimating Stream Skew in a Sliver of Memory

What the Second Frequency Moment Actually Measures

For a data stream, let m_i denote how many times item i appears by the end of the stream. The zeroth frequency moment, F0, counts the number of distinct items. The first frequency moment, F1, is simply the total length of the stream, since it sums every frequency to the first power. The second frequency moment, F2, sums the square of every item's frequency: it is the sum over all distinct items of m_i squared. Squaring frequencies before summing has a striking effect: it rewards concentration and punishes spread. Consider two streams of the same total length. In one, a million items each appear exactly once, so F2 equals a million. In the other, a single item appears a million times while everything else is silent, so F2 equals a million squared, a trillion. Both streams have identical length, but F2 differs by six orders of magnitude because F2 is sensitive to how unevenly the mass of the stream is distributed across items. This is precisely why F2 is called a measure of skew or concentration: dividing F2 by F1 squared, or comparing F2 to what a perfectly uniform distribution would produce, gives a normalized sense of how lopsided the item frequencies are. Statisticians will recognize F2 as closely related to the Herfindahl-Hirschman Index used in economics to measure market concentration, and to the notion of collision probability in information theory, since F2 divided by the square of the stream length equals the probability that two items drawn uniformly at random from the stream happen to be the same item. Because F2 rewards a few large frequencies so heavily, it acts as an early warning signal: when a network normally spreads packets across thousands of flows and F2 suddenly spikes, it is a strong quantitative hint that a small number of flows, perhaps a denial of service attack or a misbehaving application, have started to dominate traffic, even before anyone manually inspects flow-level logs.

Why F2 Matters for Real Systems

Beyond network anomaly detection, F2 shows up wherever engineers need a cheap proxy for how skewed a distribution is without materializing the full distribution. A content delivery network wants to know whether requests are spread across millions of files or concentrated on a viral few, because that concentration determines caching strategy: a highly skewed request pattern, meaning a high F2 relative to F1 squared, means a small cache holding the hottest items will absorb most traffic, while a flat distribution means caching offers little benefit. A database query optimizer estimating the selectivity of a join benefits from F2, because the cost of a self-join on a column is exactly the F2 of that column's value distribution, so join-order optimizers use F2 estimates to decide which join order will produce the fewest intermediate rows. Fraud detection systems watch F2 over sliding windows of transaction sources to catch bursts of activity from a small number of accounts. In all of these settings, the defining constraint is the same: the stream is enormous, arrives once and cannot be replayed cheaply, and there is no room to store a hash table mapping every distinct item to its exact count, because the number of distinct items, whether flows, files, or account identifiers, can run into the millions or billions. Exact computation of F2 is trivial given unlimited memory: keep a counter per item, increment it on each arrival, and sum the squares at the end. The entire value proposition of the AMS Sketch is that it approximates this quantity to a provably bounded relative error using memory that is sublinear in, and in practice completely independent of, the number of distinct items, which is what makes it deployable on router line cards, embedded stream processors, and other places where memory is the scarcest resource in the system.

The Random Sign Trick: How a Single Counter Estimates F2

The heart of the AMS Sketch is deceptively simple. Before the stream starts, fix a random function that maps every possible item to either plus one or minus one, with each outcome equally likely, and crucially with the property that any four of these signs are mutually independent, a property called four-wise independence. Such a function can be generated and stored compactly using a small polynomial hash rather than an explicit lookup table for every possible item, which is what keeps the scheme memory-efficient. Maintain a single running counter, call it Z, initialized to zero. Every time an item arrives in the stream, look up its sign under the hash function and add that sign to Z. After the entire stream has passed, compute Z squared as the estimate. Why does this work? Expand Z as the sum over all distinct items of the item's frequency times its random sign, then square that sum. Squaring a sum of signed terms produces two kinds of pieces: the square terms, where an item multiplies against itself, and the cross terms, where two different items multiply together. Each square term contributes exactly the item's frequency squared, because a sign of plus one or minus one squares to exactly one, regardless of which sign was drawn. Each cross term contributes the product of two different items' frequencies times the product of their two independent random signs, and because those two signs are independent and each is equally likely to be plus one or minus one, the expected value of their product is exactly zero. Taking the expectation of Z squared over the randomness in the signs, the cross terms vanish and only the square terms survive, leaving exactly the sum of every item's frequency squared, which is F2 by definition. This is why the algorithm is called unbiased: on average, across the randomness of the hash function, the single number Z squared equals F2 exactly, even though any one run will land above or below the true value due to random fluctuation.

Controlling Variance: Repetition and Median of Means

An unbiased estimator that is correct only on average is not yet useful, because a single run of Z squared can be wildly off from F2 due to variance, and it is entirely possible for the cross terms not to fully cancel in any particular random draw. The AMS Sketch controls this in two stages, commonly described as averaging and then taking the median, also known as median of means. In the first stage, run many independent copies of the basic estimator in parallel, each with its own independently drawn four-wise independent hash function and its own running counter, and average their squared values together. Averaging a set of independent, identically distributed unbiased estimators does not change the expected value, since the expectation of an average equals the average of the expectations, but it shrinks the variance by a factor equal to the number of copies being averaged, because variance of an average of independent quantities divides by the count. Choosing the number of parallel copies proportional to one over the square of the desired relative error epsilon squared, using Chebyshev's inequality, guarantees the averaged estimate lands within a small relative error of F2 with reasonably high probability, commonly framed as at least seventy-five percent confidence. The second stage boosts this confidence arbitrarily close to certainty without paying a heavy price in memory: take several independent groups, each internally averaged as above, and report the median across the groups. Because each group's average is correct with probability at least three-quarters, the probability that a majority of groups are simultaneously wrong shrinks exponentially fast as the number of groups grows, by a Chernoff-style tail bound, so doubling or tripling the number of groups pushes the failure probability down to a negligible number while only multiplying the total memory by that same small factor.

Why the Memory Stays Sublinear

The defining promise of the AMS Sketch is that its memory footprint does not scale with n, the number of distinct items possibly appearing in the stream, which can be astronomically large, but instead scales only with the desired accuracy and confidence. Each individual counter Z is a single integer, and because it is a running sum of plus-or-minus-one increments over a stream of length m, its magnitude never exceeds m, so representing it requires only O(log m) bits, a number of bits logarithmic in the stream length rather than linear in the number of distinct items. The four-wise independent hash function needed to generate the signs does not require storing an explicit table with one entry per possible item; instead it can be built from a low-degree polynomial over a finite field defined by a handful of randomly chosen coefficients, so the entire hash function is described by O(1) words of memory per copy, independent of how many distinct items exist. Multiplying by the number of parallel counters needed for the desired relative error epsilon, and by the number of groups needed for the desired confidence delta, the total memory works out to O(1 / epsilon squared times log(1 / delta) times log m) bits, a bound that involves only the accuracy target, the confidence target, and the logarithm of the stream length, with absolutely no dependence on the number of distinct items n. This is what makes the space usage genuinely sublinear, indeed effectively constant with respect to n: whether the stream contains a thousand distinct flows or a billion, the sketch occupies exactly the same amount of memory, in stark contrast to an exact frequency table whose size grows linearly with the number of distinct items actually observed. This space-accuracy tradeoff, formalized rigorously in the original 1996 AMS paper, launched the broader field of streaming algorithms and sketching, and the same random-sign idea reappears, in more elaborate forms, inside later sketches such as Count-Sketch and the AMS-based building blocks of heavy-hitter detection.

Frequently asked questions

Try it live

Everything above runs in your browser — open AMS Sketch: Estimating Stream Skew in a Sliver of Memory and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.