AMS F2 Estimation

Estimating Collision Energy with Random Signs

Suppose a network sees flows with frequencies \(f=(3,2,1)\). The first frequency moment \(F_1=\sum_i|f_i|=6\) measures total mass, while the second moment \[ F_2=\sum_i f_i^2=3^2+2^2+1^2=14 \] emphasizes concentration. If the same six events belonged to one key, \(F_2\) would be \(36\). This sensitivity makes \(F_2\), sometimes called collision energy or the squared \(\ell_2\) norm, useful for detecting skew.

The AMS idea compresses the whole vector to one signed number. Give every key a stable random sign \(s(i)\in\{-1,+1\}\), and maintain \[ Z=\sum_i s(i)f_i. \] For an update \((i,\Delta)\), perform \(Z\leftarrow Z+s(i)\Delta\). At query time return \(X=Z^2\). Positive and negative cross-key interactions cancel in expectation, leaving the sum of squares.

As an analogy, imagine placing each key's frequency on one of two pans according to a random sign. The signed imbalance \(Z\) depends strongly on the assignment, but its square contains information about total squared weight. One weighing is noisy; many independent weighings, averaged in groups and then combined by a median, become reliable.

This deep dive builds on frequency moments and norms by supplying a streaming construction for \(F_2\). A Rademacher sign is equally likely to be \(+1\) or \(-1\). The sketch is an inner product \(Z=\langle s,f\rangle\). Its square is unbiased when \(\mathbb E[Z^2]=F_2\). A fourth moment such as \(\mathbb E[Z^4]\) controls \(\operatorname{Var}(Z^2)\). Repetition means independent rows, not repeated queries to an unchanged row.

The canonical sketch is linear, so insertion-only and turnstile updates both work: negative deltas simply subtract signed mass. The boundary is randomness quality. Pairwise-independent signs are enough for unbiasedness, but the standard variance proof needs four-wise independence. A deterministic all-\(+1\) sign map estimates \((\sum_i f_i)^2\), not \(F_2\).

The AMS Projection and Unbiased Square

Let \(f\in\mathbb R^u\) be the current frequency vector. Choose a sign function \(s:U\to\{-1,+1\}\) with \(\mathbb E[s(i)]=0\) and pairwise-independent values. Maintain \[ Z=\sum_i s(i)f_i. \] Because the sketch is linear, update \((i,\Delta)\) costs one sign evaluation and one addition. Squaring gives \[ Z^2=\sum_i s(i)^2f_i^2+2\sum_{i\lt j}s(i)s(j)f_if_j. \] Since \(s(i)^2=1\), the diagonal sum is exactly \(F_2\). Pairwise independence and zero means give \(\mathbb E[s(i)s(j)]=0\) for \(i\ne j\). Therefore \[ \mathbb E[Z^2]=\sum_i f_i^2=F_2. \]

This proof works for negative frequencies because \(f_i f_j\) can be signed while the sign expectation still kills every cross term. It also exposes two implementation obligations: every occurrence of the same canonical key in a row must receive the same sign, and distinct rows must use independent seeds. Assigning a fresh sign per event would estimate event-level noise rather than the frequency vector.

Unbiasedness alone is insufficient. A random variable can have the correct mean and enormous variance. To control \(\operatorname{Var}(Z^2)\), expand \(Z^4\). With four-wise-independent Rademacher signs, only index patterns in which every sign appears an even number of times survive expectation: \[ \mathbb E[Z^4] =\sum_i f_i^4+6\sum_{i\lt j}f_i^2f_j^2 =3F_2^2-2F_4 \le3F_2^2. \] Thus \[ \operatorname{Var}(Z^2)=\mathbb E[Z^4]-F_2^2\le2F_2^2. \]

A counterexample clarifies the independence boundary. Let one random bit \(r\) define \(s(i)=r\) for every key. Each individual sign is fair, but signs are perfectly correlated. Then \(Z^2=(\sum_i f_i)^2\), and cross terms do not vanish. Pairwise independence fixes unbiasedness; four-wise independence supports the stated fourth-moment bound. Full independence is sufficient but not necessary.

flowchart TD
    A[Frequency vector f and updates] --> B[Stable Rademacher sign per key]
    B --> C[Linear projection Z equals sum of sign times frequency]
    C --> D[Expand Z squared]
    D --> E[Diagonal terms equal F2]
    D --> F[Pairwise independence cancels cross terms]
    E --> G[Expected square equals F2]
    F --> G
    G --> H[Expand fourth moment]
    H --> I[Four-wise independence removes odd patterns]
    I --> J[Variance at most 2 times F2 squared]
    J --> K[Average rows then median groups]
    B --> L{Signs correlated or change by event?}
    L -->|yes| M[Bias or variance proof fails]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C,D navy;
    class E,F,G teal;
    class H,I,J,K purple;
    class L,M crimson;

Fourth Moments, Variance and Repetition

One squared row has relative variance at most two, so a single result is not a high-accuracy estimate. Average \(r\) independent squares: \[ Y=\frac1r\sum_{t=1}^r Z_t^2,\qquad \mathbb E[Y]=F_2,\qquad \operatorname{Var}(Y)\le\frac{2F_2^2}{r}. \] Chebyshev's inequality yields \[ \Pr[|Y-F_2|\ge\varepsilon F_2]\le\frac{2}{r\varepsilon^2}. \] Choosing \(r=\lceil8/\varepsilon^2\rceil\) makes a group fail with probability at most \(1/4\). Build an odd number \(g\) of independent groups and return their median. A Chernoff analysis gives exponentially small failure; the conservative choice \(g\ge12\ln(1/\delta)\), rounded upward to an odd integer, is sufficient under this \(1/4\) group-failure bound.

The memory is \(O(\varepsilon^{-2}\log(1/\delta))\) counters plus compact sign seeds. Update time matches the number of counters unless vectorized or accelerated. Constants are intentionally visible: another analysis or estimator family may improve them, but silently quoting only big-O hides operational cost.

For \(f=(2,1)\), one row takes values \(1\) or \(9\) with equal probability. Its mean is \(5\), but variance is \(16\). Averaging four independent rows reduces variance to \(4\). The exact general bound \(2F_2^2=50\) is safe but loose here. If the vector is perturbed to \((2,-1)\), exact \(F_2\) remains \(5\); the sign outcomes swap, demonstrating turnstile compatibility.

Numeric limits remain real. Squaring a 64-bit projection may require wider accumulation or checked arithmetic. Floating-point group means can lose precision when values span huge ranges. Reusing a seed across rows prevents variance reduction, while exposing fixed signs to an adaptive adversary changes the practical threat model even when the nonadaptive theorem is correct.

from hashlib import blake2b
from statistics import median

def sign(seed, row, key):
    raw = f"{seed}|{row}|{key}".encode()
    value = blake2b(raw, digest_size=8, person=b"ams-f2-v1").digest()
    return 1 if value[0] & 1 else -1

class AMSF2:
    def __init__(self, rows_per_group, groups, seed=19):
        if rows_per_group < 1 or groups < 1 or groups % 2 == 0:
            raise ValueError("positive rows and positive odd groups required")
        self.r, self.g, self.seed = rows_per_group, groups, seed
        self.z = [0] * (rows_per_group * groups)

    def update(self, key, delta):
        if not isinstance(delta, int):
            raise TypeError("integer delta required")
        for row in range(len(self.z)):
            self.z[row] += sign(self.seed, row, key) * delta

    def estimate(self):
        means = []
        for group in range(self.g):
            start = group * self.r
            squares = [x * x for x in self.z[start:start + self.r]]
            means.append(sum(squares) / self.r)
        return median(means)

def exact_f2(updates):
    freq = {}
    for key, delta in updates:
        freq[key] = freq.get(key, 0) + delta
    return sum(value * value for value in freq.values()), freq

normal = [("hot", 300)] + [(f"k{i}", i % 5 + 1) for i in range(200)]
truth, _ = exact_f2(normal)
sketch = AMSF2(256,  nine_groups := 9)
for item in normal:
    sketch.update(*item)
assert abs(sketch.estimate() - truth) / truth < 0.20

turnstile = [("a", 20), ("b", 7), ("a", -6), ("debt", -9), ("b", -2)]
turn_truth, vector = exact_f2(turnstile)
turn = AMSF2(256, 9)
for item in turnstile:
    turn.update(*item)
assert abs(turn.estimate() - turn_truth) / turn_truth < 0.25

empty = AMSF2(8, 3)
assert empty.estimate() == 0

all_positive_projection = sum(vector.values())
bad_square = all_positive_projection * all_positive_projection
assert bad_square != turn_truth

try:
    AMSF2(8, 4)
    raise AssertionError("even group count accepted")
except ValueError:
    pass

print("normal:", round(sketch.estimate(), 2), "exact:", truth)
print("turnstile:", round(turn.estimate(), 2), "exact:", turn_truth)
print("correlated-sign failure:", bad_square)

Detecting Skew in Network and Event Streams

In a teaching case, compare two ten-event streams. Ten distinct keys give \(F_2=10\); one key repeated ten times gives \(F_2=100\). AMS demonstrates how a tiny linear state distinguishes diffuse from concentrated frequency vectors without naming the heavy key.

In professional network telemetry, maintain AMS sketches for fixed windows of source–destination flow updates. A rising normalized concentration such as \(F_2/F_1^2\) can signal a shift toward dominant flows. Because sketches are linear, compatible regional tables merge by counterwise addition. The contract must include window, key encoding, row/group layout, sign-family version, seeds, arithmetic width, and update semantics.

An event platform can similarly monitor tenant–event skew, including corrections expressed as negative deltas. AMS measures concentration but does not identify the responsible keys; pair it with a heavy-hitter summary or exact candidate audit. A flat vector and a different vector may share the same \(F_2\), so business interpretation needs additional signals.

Failure cases include adaptive producers that learn signs, accidental seed reuse, inconsistent canonicalization across partitions, overflow before squaring, and merging different sketch versions. Evidence invalidating the choice includes systematic exact-audit bias, group estimates that are strongly correlated, empirical failure exceeding \(\delta\), negative impossible results caused by arithmetic faults, or latency from too many rows exceeding the processing budget.

flowchart TD
    A[Define concentration metric and window] --> B{Need only F2, not key identities?}
    B -->|no| C[Pair with heavy hitters or exact map]
    B -->|yes| D{Stable canonical turnstile updates?}
    D -->|no| E[Reject until input contract is fixed]
    D -->|yes| F[Choose epsilon delta and row groups]
    F --> G[Select four-wise sign family and safe counters]
    G --> H[Validate against exact sampled windows]
    H --> I{Bias failure and latency acceptable?}
    I -->|no| J[Reject resize or repair randomness]
    I -->|yes| K[Version sketch and deploy]
    K --> L[Monitor correlation overflow and drift]
    L --> M{Assumptions still hold?}
    M -->|yes| L
    M -->|no| J
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,D navy;
    class F,G purple;
    class H,K,L teal;
    class C,E,I,J,M crimson;

Simulate and Verify the AMS Estimator

Mastery begins by deriving, not memorizing, the update rule. Expand \(Z^2\), label diagonal and cross terms, and state precisely why each expectation vanishes. Then expand \(Z^4\), enumerate even-multiplicity index patterns, and connect the result to variance, Chebyshev, group size, and median amplification.

Implementation work should maintain an exact oracle on small streams. Test insertion-only, general turnstile, empty, one-key, flat, skewed, overflow-adjacent, and adversarially correlated-sign cases. Distinguish independence across keys inside a row from independence across rows. Verify merge by comparing counterwise-added sketches with a sketch of the concatenated update stream.

For extension, derive the AMS inner-product estimator: use compatible signed projections of \(f\) and \(g\), multiply them, and show the expected product is \(\langle f,g\rangle\). Then connect \(F_2\) estimation to self-join size, heavy-hitter residual energy, and linear-sketch composition.