# Frequent-item certificates

A small counter table is useful for finding hot request identities. Its output
still needs to be read as bounds, not an exact popularity leaderboard.

## Two worked examples

The model counts **unit arrivals for exact string identities**. The letters below
are constructed inputs, not a storage trace. There is no sampling, random seed,
timing measurement, byte weighting, aging or deletion.

| Stream | Slots | Result | What can be concluded |
| --- | --- | --- | --- |
| A B C A B D A A A B | 2 Misra-Gries | A:3, B:1; two decrement rounds | A has 3-5 arrivals; B has 1-3. B cannot exceed 10/3. |
| A A A B C D E | 2 Space-Saving | D:3 with error 2; E:4 with error 3 | A, the unique most frequent key, is absent. D and E each actually occur once. |
| A B C | 2 Misra-Gries | Empty table | An item exactly at N/3 need not survive. |

The first stream has exact counts A:5, B:3, C:1, D:1.
Its residual mass is 4, so (10-4)/3 = 2 decrement rounds.
The additional pruning rule removes B without a second pass. A remaining
candidate is not automatically confirmed as heavy; use its lower bound or recount.

Space-Saving resolves equal minimum counts by evicting the lexically smallest
identity in this model. In the second stream A and D both have counters of 3
before E arrives. Evicting A is permitted. E then has count 4 and error 3.
The true count of E is inside [1,4], so an incorrect ranking is compatible with
valid frequency bounds. A has count 3, equal to the untracked upper bound.

## Reproduce

Download these files together, then run with Node.js (tested with v24.22.2):

- [model.mjs](model.mjs): readable implementation and deterministic result generator.
- [model.test.mjs](model.test.mjs): independent exact counts and invariant assertions.
- [results.json](results.json): complete inputs, outputs and assumptions.

```sh
node model.mjs --check
node --test model.test.mjs
```

The tests enumerate all 21,845 streams over A-D of length 0-7 with capacities
1, 2 and 3: 65,535 stream/capacity cases. They check capacity, conserved mass,
frequency intervals, strict heavy-hitter retention and residual pruning.
They also check the correspondence between Misra-Gries with m counters and
Space-Saving with m+1 counters. This is bounded implementation testing,
not a proof for all streams; the general results come from the papers.

The simple implementation scans counters and is written for inspection.
It is not a performance implementation or a recommended production dependency.
Input validation rejects weights, non-string identities and invalid capacities.

## Evidence

- [Misra, A Proof of a Heavy Hitters Algorithm (2018), section 3](https://www.cs.utexas.edu/~misra/Notes.dir/HeavyHitters.pdf): cancellation and residual pruning.
- [Metwally, Agrawal and El Abbadi, Efficient Computation of Frequent and Top-k Elements in Data Streams, sections 3-4](https://www.cs.emory.edu/~cheung/Courses/584/Syllabus/papers/Frequency-count/2005-Metwally-Top-k-elements.pdf): Space-Saving updates and intervals.
- [Agarwal et al., Mergeable Summaries, section 2](https://users.cs.utah.edu/~jeffp/papers/merge-summ.pdf): the residual error certificate and different-budget correspondence.

Hesela-authored worked examples, 20 November 2026. No third-party implementation,
figure or full paper is redistributed. Source manuscripts were reviewed, not
their empirical benchmarks reproduced. No cache hit-ratio or SEO benefit is claimed.
