Frequency Estimation & Point Queries

How Often Did This Key Appear?

Picture a shop recording views of product pages. The sequence A, B, A, C, B, A contains six views, but the question “How often was A viewed?” has answer three. Keeping a counter for every possible product ID may be too expensive when most IDs are rare. A frequency sketch keeps a small grid of counters, sending each key to a position in each row. Shared positions cause interference; several rows give different chances to avoid a harmful collision.

For a tiny illustration, suppose A has count 3, B has count 2, and C has count 1. In one row A and C share a counter, so reading A there gives 4. In another row A has its own counter and gives 3. Taking the smaller reading recovers 3. This is the Count-Min idea for nonnegative updates. It does not promise that every small reading is exact: a key may collide in every row. Count Sketch uses random signs to make collision noise sometimes positive and sometimes negative, then combines row estimates by a median. Its error scale and update model differ.

The preceding chapters supply the frequency-vector model, concentration bounds, and hash-family assumptions. Here a point query asks for one coordinate of that vector. We will state whether updates can be negative, what quantity sets the error allowance, what randomness the probability covers, and whether a promised answer concerns a fixed key or many adaptively chosen keys.

Point Queries in a Compressed Frequency Vector

Let $U$ be a universe of keys. Updates $(x,\Delta)$ define $f_x=\sum_{(x,\Delta)}\Delta$. In a cash-register stream every $\Delta\ge0$, so all $f_x\ge0$ and $N=\lVert f\rVert_1=\sum_xf_x$. In a general turnstile stream $\Delta$ may be negative and intermediate frequencies may be signed. A strict-turnstile stream permits negative updates while maintaining $f_x\ge0$ after every prefix. These are different premises for a proof, even when two streams end with the same final vector.

A Count-Min Sketch (CMS) has $d$ rows, $w$ nonnegative counters per row, and hash functions $h_r:U\to\{0,\ldots,w-1\}$. On $(x,\Delta)$ with $\Delta\ge0$, add $\Delta$ to counter $(r,h_r(x))$ for every row $r$. A point query returns $\widehat f_x=\min_r C_{r,h_r(x)}$. In each row the queried counter is $f_x$ plus nonnegative mass from colliding keys. Therefore $\widehat f_x\ge f_x$ deterministically for a valid cash-register sketch. The upper error bound is probabilistic under assumptions on the hashes. A direct signed decrement can make a CMS row smaller than the queried final frequency; the standard one-sided claim cannot simply be carried over to general turnstile streams.

A Count Sketch also has $d$ rows and $w$ counters, but each row uses a bucket hash $h_r$ and a sign hash $s_r:U\to\{-1,+1\}$. On update $(x,\Delta)$ add $s_r(x)\Delta$ to $C_{r,h_r(x)}$. Query row $r$ with $Y_r(x)=s_r(x)C_{r,h_r(x)}$ and return the median of row estimates. With suitable independent hash and sign families, $\mathbb E[Y_r(x)]=f_x$ and its collision-noise variance is at most $\lVert f_{-x}\rVert_2^2/w$, where $f_{-x}$ excludes coordinate $x$. Signed updates remain linear, provided arithmetic does not overflow and the update stream matches the vector model. The estimate may lie above or below truth.

An inner-product query asks for $\langle f,g\rangle=\sum_xf_xg_x$, not one coordinate. Compatible linear sketches can form estimators for such products, but a point-query guarantee alone does not supply an inner-product guarantee. State the shared randomness, which arrays are multiplied, the update models, and the resulting variance separately. Conservative update for CMS increments only the addressed counters currently at the row minimum, by an appropriate amount; it can reduce empirical overestimation for insert-only workloads, but the update is nonlinear and its merge and error claims must be checked for the chosen variant.

flowchart TD
    U["Updates define frequency vector f"] --> M{"Update model"}
    M -->|Nonnegative| C["Count-Min: add to hashed counters"]
    C --> N["Query minimum: one-sided overestimate"]
    M -->|Signed allowed| S["Count Sketch: signed counter updates"]
    S --> D["Query signed rows, then median"]
    N --> Q["Point query for one key"]
    D --> Q
    U --> I["Inner product requires separate analysis"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class U,M navy; class C,N,Q teal; class S,D purple; class I crimson;

Collisions, Error Scales and Confidence Rows

For one CMS row and fixed key $x$, write the excess as $Z_r(x)=\sum_{y\ne x}f_y I_{\{h_r(y)=h_r(x)\}}$. Under a universal collision bound $1/w$, linearity gives $\mathbb E[Z_r(x)]\le (N-f_x)/w\le N/w$. The sum is nonnegative. Markov's inequality then gives $\Pr(Z_r(x)>\varepsilon N)\le1/(w\varepsilon)$ (using a non-strict threshold is also possible with the corresponding inequality). If $w\ge e/\varepsilon$, the bound is at most $1/e$ for each row. With independently seeded rows, the minimum exceeds $f_x+\varepsilon N$ only when every row is bad, giving probability at most $e^{-d}$. Choosing $d\ge\ln(1/\delta)$ therefore suffices for failure at most $\delta$ for that fixed query. The familiar dimensions $w=\lceil e/\varepsilon\rceil$ and $d=\lceil\ln(1/\delta)\rceil$ express a sufficient design, not a promise against seed-aware adaptive queries.

For a Count Sketch row, expand the signed reading: $Y_r(x)=f_x+\sum_{y\ne x}f_y s_r(x)s_r(y) I_{\{h_r(y)=h_r(x)\}}$. Balanced sufficiently independent signs make the noise mean zero; cross terms vanish in its second moment under the required sign independence. Pairwise bucket collision control gives $\operatorname{Var}(Y_r(x))\le\lVert f_{-x}\rVert_2^2/w$. Chebyshev makes a deviation of $\sqrt{3/w}\,\lVert f_{-x}\rVert_2$ occur with probability at most $1/3$ in a row. A median of sufficiently many independently seeded rows drives down the chance that a majority are bad exponentially in $d$. This is a two-sided $L_2$-scale statement, unlike the CMS $L_1$ one-sided statement; constants and independence requirements depend on the exact construction.

Why not infer relative error? With $N=1{,}000{,}000$ and $\varepsilon=0.01$, CMS permits absolute error up to $10{,}000$ on a count of $3$, under its successful event. Conversely, a large heavy key can dominate $\lVert f\rVert_2$ and contaminate a Count Sketch row if it collides with the queried key. Increase width or choose an appropriate heavy-hitter and recovery procedure when the target asks for small relative errors or an unknown list of important keys. A simultaneous bound over $Q$ predetermined point queries can allocate $\delta/Q$ to each and apply a union bound; it is not automatically an adaptive-query theorem.

The standard arrays are linear in updates when hashes are fixed: two compatible CMS arrays or Count Sketch arrays can be added counterwise to summarize the sum of their frequency vectors, subject to each method's update-model guarantee. Identical hash definitions, signs, seeds, width, and row order are required. Conservative-update variants alter only some counters based on current minima, so this simple linear merge proof does not apply. An inner-product estimator likewise needs its own collision and variance proof even if the arrays are mergeable.

flowchart TD
    A["Fix query key x and random hashes"] --> B{"Sketch type"}
    B -->|CMS, nonnegative| C["Collision mass Z is nonnegative"]
    C --> D["Expected Z at most N/w"]
    D --> E["Markov: one bad row at most 1/e"]
    E --> F["Independent rows: min fails at most e^-d"]
    B -->|Count Sketch, signs| G["Noise mean zero, variance L2²/w"]
    G --> H["Chebyshev: each row usually close"]
    H --> I["Median boosts confidence"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class A,B navy; class C,D,E,F teal; class G,H,I purple;

Network Flows, Product Views and Abuse Counters

Approachable product views. A store counts A, B, A, C, B, A. If page-view events only add one, CMS can estimate each product's views. With the two-row trace above, A and B happen to read exactly despite one collision per row. An observed estimate for a rare product should still be interpreted with an additive total-traffic bound, not as an exact small count. If traffic includes bot events, sketch accuracy says nothing about whether those events are genuine views.

Production network flows. Suppose a telemetry worker receives $100{,}000$ flow updates per second across millions of flow IDs and has $8$ MiB for hashed counters. A fixed-key CMS design for additive allowance $\varepsilon N$ and failure $\delta$ needs $w=\lceil e/\varepsilon\rceil$ and $d=\lceil\ln(1/\delta)\rceil$ counters per row. For $\varepsilon=0.001$ and $\delta=0.01$, that is $w=2{,}719$, $d=5$, or $13{,}595$ counters before counter widths and hash seeds; at eight bytes each, about $106.2$ KiB of counter storage. This is comfortably below the stated budget but does not solve key discovery, identity normalization, late-event correction, or exact billing. If flow updates can subtract bytes, a signed Count Sketch or another justified turnstile method may fit better than CMS's one-sided proof.

Abuse or misleading case. A public API uses a sketch to track request counts per account. A client may choose account IDs after watching responses or may split traffic across many IDs. A fixed-key randomized guarantee does not automatically handle adaptive key selection or sybil identities. A CMS overestimate may wrongly flag an innocent account if the estimate itself is treated as proof of abuse; an exact verification step or conservative escalation policy is needed. Similarly, corrections, refunds, and expirations change the update model. The mathematical bound is about the chosen vector and hash randomness, not about whether the logged events, account identities, or enforcement decision are correct.

Specify and Test a Frequency Contract

Select a point-query method by update signs, the acceptable absolute error baseline, and whether the output is informational or consequential. Then verify its hash assumptions and resource costs. The practice below moves from a tiny collision trace to a specification that can be tested on production data.