Space-Saving
Space-Saving estimates frequent items with labelled counters, replacing a minimum-count item when a new identity arrives at a full summary.
For unit insertions, increment a tracked key. Otherwise use a free slot or replace a minimum counter q with the new key at q+1, recording q as its error allowance. A tracked key's true count lies in [count-error, count]; an untracked key's frequency is at most the current minimum, or zero while slots remain unused. [1]
With m counters and N arrivals, the counter sum is N and the minimum is at most N/m. Every key strictly above N/m is retained. Ranking estimates alone does not certify an exact top-k set: overlapping count intervals can leave the order unresolved. [1]
With two counters and lexical eviction tie-breaking, A A A B C D E ends with D:(count 3, error 2) and E:(count 4, error 3). A is absent even though it occurs three times and every other key occurs once. E's interval [1,4] includes its true count 1; the bound remains valid while the ranking is wrong. [3]
A less obvious relation uses different budgets. Misra-Gries with m counters corresponds to Space-Saving with m+1. Subtracting Space-Saving's minimum from its estimates gives Misra-Gries counters, treating missing keys as that minimum or zero, respectively. This is not an equivalence at the same counter count. [2]
Relations
- related
- Misra-Gries summary, Count-Min sketch, TinyLFU
Citations
- Metwally, Agrawal and El Abbadi. Efficient Computation of Frequent and Top-k Elements in Data Streams, sections 3-4.
- Agarwal, Cormode, Huang, Phillips, Wei and Yi. Mergeable Summaries, section 2, Lemmas 1-2.
- Hesela. Frequent-item certificates: exact examples, executable model and tests.
Sources & caveats
- UCSB identifies the authors' technical report as 2005-23, dated 1 May 2005. The linked full manuscript supplies the update rule and frequency bounds; no speedup or workload distribution is imported.
- The example's eviction tie-break is explicitly fixed. Other valid tie-breaks can retain different identities; deterministic frequency guarantees do not imply a unique output representation.
- This record covers cumulative unit insertions without aging, deletions, weighted updates or saturated counters. Estimated request popularity is not a complete cache-admission policy.