Space-Saving: ranked candidates with count bounds

Last updated: 5 Oct 20269 min read

tutorial

Space-Saving maintains a fixed number of tracked incident codes. A hit increments its estimate. An unseen code uses a free slot, or replaces a code with the minimum estimate when the summary is full. The replacement receives estimate minimum plus one and error minimum. For a tracked code, its true frequency lies between estimate minus error and estimate, inclusive. A tracked code with zero error has an exact count. The bound is more informative than printing an unlabeled approximate count, but it does not turn the candidate list into an exact ranking. This program resolves equal-minimum ties by incident-code order to make runs repeatable. It accepts insertion-only events and assumes codes are strings.

Operational case

A monitoring feed repeatedly emits pump-47, with occasional valve-19, sensor-61, and grid-83 records. A two-slot summary reports candidates ordered by estimated count. Its pump entry may have an error range after earlier replacements; the tuple states that uncertainty rather than hiding it. If a responder needs the actual two most frequent codes, replay the feed and count all candidate codes or use an exact index. When two codes share a minimum estimate, removing the alphabetical one is merely this implementation's stable tie rule; another tie rule can change which borderline code survives without violating the count bounds.

Working Python program

class SpaceSavingIncidents:
    def __init__(self, capacity):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.entries = {}

    def record(self, incident_code):
        if incident_code in self.entries:
            estimate, error = self.entries[incident_code]
            self.entries[incident_code] = (estimate + 1, error)
        elif len(self.entries) < self.capacity:
            self.entries[incident_code] = (1, 0)
        else:
            victim = min(self.entries, key=lambda code: (self.entries[code][0], code))
            minimum = self.entries[victim][0]
            del self.entries[victim]
            self.entries[incident_code] = (minimum + 1, minimum)

    def candidates(self):
        return sorted(self.entries.items(), key=lambda pair: (-pair[1][0], pair[0]))


incident_stream = ["pump-47", "valve-19", "pump-47", "sensor-61",
                   "pump-47", "valve-19", "pump-47", "grid-83",
                   "pump-47", "sensor-61", "pump-47"]
summary = SpaceSavingIncidents(2)
for incident_code in incident_stream:
    summary.record(incident_code)
print("candidates=", summary.candidates(), sep="")

Output

candidates=[('pump-47', (6, 0)), ('sensor-61', (5, 4))]

Time, space, and tradeoff

This direct implementation stores O(K) entries. Existing-key updates use expected O(1) dictionary work; insertion into a full summary scans K entries to locate a minimum, so its worst-case time is O(K). Producing the sorted display costs O(K log K). Heap-indexed implementations can reduce minimum selection work but need careful updates to avoid stale heap records. Counts and error bounds refer to the insertion-only prefix seen so far. Deletion, sliding windows, distributed merges, and adversarial key ordering need separate algorithms or contracts. A small fixed K is useful when storing exact counts for every distinct incident code would be too costly.

Common Mistakes

Do not label estimated counts as exact counts when error is positive.
Do not omit the replaced minimum from the new key's error field.
Do not claim O(1) replacement for this linear minimum search.
Do not promise exact top-K membership for a bounded candidate summary.

Connected lessons

Compare its result with Misra–Gries: find frequent-item candidates in one pass, HyperLogLog: estimate unique IDs with fixed registers, Reservoir sampling: keep a uniform fixed-size sample, then complete the bounded-stream audit and contract quiz.

Count Sketch: estimate signed incident frequencies with row medians adds a related structure with a different operation boundary.

All-one frequency buckets: increment, decrement, and read both extremes examines a related structure with a different operation boundary.

data structures

range-query-structures