space-saving · research · also SpaceSaving, Space-Saving summary

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

  1. Metwally, Agrawal and El Abbadi. Efficient Computation of Frequent and Top-k Elements in Data Streams, sections 3-4. (accessed 2026-11-20)
  2. Agarwal, Cormode, Huang, Phillips, Wei and Yi. Mergeable Summaries, section 2, Lemmas 1-2. (accessed 2026-11-20)
  3. Hesela. Frequent-item certificates: exact examples, executable model and tests. (accessed 2026-11-20)
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.

JSON: /data/terms/space-saving.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Space-Saving. Hesela. 2026-11-20. https://hesela.dev/terms/space-saving/