Naming a key versus finding one
The previous note answered a post-hoc question: given a key chosen in advance, estimate how often occurred. A Count-Min sketch can do this, but it cannot tell us which keys to ask about. Its counters mix many keys and record no identities. A positive estimate does not even show that a key occurred.
This note addresses a different task, called candidate discovery. We read a finite stream once without knowing beforehand which keys matter. At the end we want a short list of key identities that is guaranteed to contain every key occurring more than a fixed fraction of the time. The method below is deterministic: no hashing and no failure probability. It is often called the Misra–Gries frequent-items summary.
The claims below state their own assumptions and are proved in full.
Model and assumptions
A stream is a finite sequence of keys, with . Keys may come from any universe, and the algorithm needs only exact equality tests between keys. Every update is a single insertion of one occurrence. There are no weights, no deletions of occurrences, and no negative updates. For a prefix of length , with , write
Fix an integer . The summary is a table holding at most pairs (key, positive integer counter), together with an integer that counts full-decrement events. Write for the counter of after items, with the convention when is not in the table. All arithmetic is exact integer arithmetic. The stream is finite, so every counter is bounded by .
FREQUENT-CANDIDATES(stream, k) // k >= 1
T <- empty dictionary // key -> positive integer
D <- 0; N <- 0
for each key y of the stream, in order:
N <- N + 1
if y is in T:
T[y] <- T[y] + 1
else if |T| < k:
T[y] <- 1 // insert with count one
else: // |T| = k and y is not in T
for each key z in T:
T[z] <- T[z] - 1
delete every z with T[z] = 0
D <- D + 1 // y is NOT inserted
return (T, D, N)
On the empty stream the loop body never runs. The output is an empty table with and , and every statement below holds for this case.
Two invariants follow directly from the three branches. First, : insertion happens only when . Second, every stored counter is at least : increments and insertions produce positive values, and the decrement branch deletes every counter that reaches zero. The second invariant matters in the main proof. When a full decrement happens, exactly counters are present and each of them is at least one.
The accounting identity and the error bound
The intuition is as follows. A full decrement takes one occurrence away from each of distinct stored keys, and it also refuses one occurrence of the incoming key, which is distinct from all of them. So each event discards exactly occurrences, belonging to different keys. Everything not discarded is still recorded in the counters.
Theorem 15.1.1
(Invariants of the -counter summary)
For every prefix length with :
- ;
- for every key , including keys not in the table, .
Proof
(Induction over the three branches)
Let . We use induction on . At the table is empty and no key has occurred, so and all are zero. Both claims hold.
Assume both claims for prefix , and let . Only changes among the frequencies, and it increases by one.
Case 1: is in the table. The value increases by one and is unchanged. The sum of counters increases by , matching the increase of . Both and grow by one, so is unchanged. All other are untouched.
Case 2: is absent and . The counter goes from to and is unchanged. Again the sum of counters rises by and is unchanged.
Case 3: is absent and . Each of the stored counters is at least one, so subtracting one from each lowers by exactly . Deleting counters that are now zero leaves the sum unchanged, because a deleted key's counter becomes under our convention. The key is not inserted, so stays . Hence
For the error terms, rises by one because rises and does not. Each of the stored keys also has rising by one, because its counter fell and its frequency did not change. Every other key is unaffected.
In every case, each either stays the same or increases by exactly one, and it can increase only in a step where also increases by one. Since , it follows that .
Proof X-ray
Why the two claims are the same bookkeeping
Summing over all keys gives , so claim 1 is the total of the per-key losses. Case 3 explains the factor : the stored keys and the incoming key are pairwise distinct, so one event adds one unit of loss to different keys. Because the keys are distinct, no single key can lose more than one occurrence per event, and this is exactly the bound . If the incoming key could coincide with a stored key, Case 1 would apply instead, which is why the branch order in the pseudocode matters.
Consequences. Every quantity in claim 1 is nonnegative, so . Since is an integer,
Claim 2 also says that each counter is a lower bound, never an exact count in general: . For a key absent from the table, the estimate is low by at most . So the table also answers post-hoc queries for any named key, with deterministic additive error at most .
Common mistake
(Reading a counter as the frequency)
A stored counter is only a lower bound: . In the trace below, while . Reporting as the count, or ranking keys by as if the ranking were exact, ignores the up to occurrences each key may have lost. Exact counts need the second pass.
Every strictly heavy key survives
Call heavy if , where . At most keys can be heavy. If keys were heavy, their frequencies alone would sum to more than .
Theorem 15.1.2
(Retention of strictly heavy keys)
After the whole stream, every key with has , so it is in the final table.
Proof
(Counter minus loss stays positive)
By the error bound and the bound on ,
The counter is an integer, so , which means is stored.
The inequality must be strict. The final table, called the candidate set, is a superset of the heavy keys and may contain false positives. Nothing in the proof prevents a light key from occupying a free slot near the end of the stream.
Common mistake
(Reporting the candidate set as the heavy keys)
The guarantee is one-sided: every heavy key is a candidate, but a candidate need not be heavy. A key arriving after the last full decrement is inserted with counter whatever its frequency, as is in the trace below. Without a second pass or one of the certificates discussed later, the final table must be reported as a superset of the heavy keys.
Worked example 15.1.3
(Trace with on )
| Item | Branch | Table after | |
|---|---|---|---|
| insert | 0 | ||
| insert | 0 | ||
| full decrement; reach 0 and are deleted; not inserted | empty | 1 | |
| insert | 1 | ||
| increment | 1 | ||
| insert | 1 | ||
| increment | 1 |
Thus , and the final table is . The true counts are , with .
The identity checks out: . The losses and are all at most , and they sum to . The bound holds.
The threshold is . Only is heavy, since , and is retained as the theorem promises. The candidate is a false positive, because . Note also that understates .
The explorer below replays the -counter summary one arrival at a time, showing the table, the count of full decrements and the identity after every prefix, and finishes with the heavy keys, the false positives and the second exact pass.
Counterexample mode
Equality at the threshold does not guarantee retention
Take and the stream . The first two items fill the table. The third triggers a full decrement that deletes both, and is not inserted. The final table is empty and .
Each key has , yet none is retained. Therefore the statement "every with is retained" is false. The proof breaks exactly where it needs : here . When the threshold is compared in code, use the exact integer test , not a floating-point quotient.
A second pass recovers exactly the heavy keys
Suppose the same stream can be read again, for example because it is stored or replayable. Allocate exact counters for the at most candidates and count only those keys:
EXACT-HEAVY(stream, T, N, k) // stream must be the one summarized
for each key z in T: E[z] <- 0
for each key y of the stream:
if y is in E: E[y] <- E[y] + 1
return { z in E : (k+1) * E[z] > N }
Theorem 15.1.4
(Two-pass exact recovery)
If the second pass reads the same sequence that produced , the output equals .
Proof
(Exact counts on a superset)
In the second pass, exactly for every candidate . A candidate is output if and only if it is heavy, so the output is . By the retention theorem , hence .
Counting is unaffected by order, so the second pass needs the same multiset of keys rather than the same arrangement. If the contents change, however, the candidate list loses its meaning: a key that is heavy in the new data may never have become a candidate. On the empty stream both passes do nothing, and the output is correct.
What one pass cannot settle from this summary
The first pass does give partial certificates. If , then is certainly heavy, because . If , then is certainly not heavy. In the worked example these certificates happen to decide both candidates. In general they do not, as the next comparison shows.
Worked example 15.1.5
(Certificates for the two candidates in the trace)
In the trace with and , the final state is with . For , , so forces : is certainly heavy. For , , so gives : is certainly not heavy. A key absent from the table, such as , has and , so it is also certified light. Both certificates are read from the summary alone; they would be inconclusive for a candidate with, say, , because .
Counterexample mode
Identical final states, different answers
Let . The stream ends with table , , . The stream ends in exactly the same state.
In the first stream , so is heavy. In the second stream , so is not heavy. No rule that reads only can classify correctly for both streams.
This shows that this summary does not support one-pass exact classification. It is not a general lower bound for all algorithms.
The theorems hold for every ordering of the input, but the final table can depend on the order.
Worked example 15.1.6
(The same multiset in a different order)
Take and rearrange the multiset of the first trace as . The keys and fill the table; triggers a full decrement that deletes both, is not inserted, and sets . The four copies of are then inserted and incremented, ending with and . The identity reads , the losses are and , and the counter of is now exact. The table differs from , yet both outcomes satisfy every guarantee, and here no false positive remains.
Small streams. If , which includes , no full decrement ever occurs. A decrement at step requires stored keys after items, and each stored key has occurred at least once, which is impossible. Hence , and every counter is exact by the error bound. The threshold satisfies , so the heavy keys are precisely the keys that occur at all, and the table is exactly that set. For , nothing is stored and nothing is heavy.
Memory and update cost
The summary stores at most key–counter pairs plus and , which is counters. The bit cost is not words in an absolute sense. Each counter needs bits. Each stored key needs its own representation: bits for a finite universe, and possibly much more for long strings. Dictionary overhead comes on top of that. On fixed-width hardware the exact-arithmetic model assumes counters cannot overflow, which a known bound on makes checkable.
With a naive exact-equality linear scan of the table, each arrival costs in the worst case, including the possible full decrement, so arrivals cost in total. Separately, the identity gives counter decrements in aggregate. This aggregate bound does not count lookups and does not make an individual full decrement constant-time. Removal of zero counters is internal table housekeeping, not a deletion of an input occurrence; such removals are bounded by the number of insertions, at most . Faster dictionary operations require a stated data structure and cost model.
The main argument does not rely on merging tables, and this note does not claim that weighted or negative updates are supported or that one pass classifies exactly.
Exercises
Exercise 15.1.7
(Run the algorithm with on . Give the final table and , name the deleted keys, and verify both invariants and the retention theorem.)
Core
Solution(4)
- 1
Process the first five items
After four items the table is . The item finds the table full, so a decrement gives . Both and reach zero and are deleted, is not inserted, and .
- 2
Finish the stream
Then is inserted and is inserted. The final table is with and .
- 3
Check both invariants
Key step
The identity holds: . The true counts are . The losses are , all at most , and they sum to .
- 4
Check retention
The threshold is . The heavy keys are and , and both are retained. The candidate is a false positive.
Exercise 15.1.8
(With and stream , find the final state. Does the outcome contradict the retention theorem?)
Foundation
Solution(2)
- 1
Trace the stream
Each is inserted into the empty table, and each following finds it full and triggers a decrement that deletes . The final table is empty and , so the bound on is attained.
- 2
Compare with the theorem
Both frequencies equal . Neither key is strictly heavy, so the empty table does not contradict the theorem.
Exercise 15.1.9
(Use the candidates from the first trace (). Suppose the second pass instead reads with . What is output, and what is wrong?)
Core
Solution(2)
- 1
Run the second pass on the new data
The counts are , and neither exceeds , so the output is empty.
- 2
Compare with both heavy sets
The new data has , so its heavy set is , while the original stream's heavy set is . The output is correct for neither stream.
Because: The two-pass theorem requires the same stream, or at least the same multiset of keys.
Exercise 15.1.10
(Take , , and 64-bit keys. Bound , state the heavy test, and estimate the bits for the table, and without dictionary overhead. Then bound the worst single-update decrement work and the total decrement work.)
Core
Solution(3)
- 1
Bound and state the test
. A key is heavy exactly when .
- 2
Count the bits
Counters reach at most , so they need 20 bits each. The table needs bits. Storing needs 20 bits, and needs 14 bits, for a total of bits.
- 3
Bound the decrement work
A single full decrement touches 99 counters. The whole stream performs at most counter decrements.
This unit covers deterministic insertion-only candidate discovery, its invariants, and two-pass exact recovery. Merging, weighted and signed streams, and space lower bounds are outside its scope.