Misra–Gries: find frequent-item candidates in one pass

Last updated: 5 Oct 20269 min read

tutorial

A stream can contain millions of incident codes, but the question may be narrower: which codes could occur more than one third of the time? Misra–Gries retains two counters for that threshold. A matching code increments its counter; an unseen code takes a free counter; if both counters are occupied, one occurrence is canceled from each resident and the incoming code. The remaining keys are candidates, not proven winners. For K counters, every key with true frequency greater than N divided by K plus one must survive. A second pass over a replayable stream, or exact counts maintained elsewhere, is required to report the qualifying keys and their true counts. The stream here is insertion-only and incident codes are hashable strings.

Operational case

In an eleven-record incident feed, pump-47 occurs six times while valve-19 and sensor-61 occur twice each and grid-83 once. With two slots the threshold is eleven divided by three, so pump-47 must appear among the candidates. The summary can also retain a code below that threshold. Its stored count has suffered cancellation and must not be printed as the exact number of pump incidents. This distinction matters if an on-call dashboard drives an alert from the summary: display candidates for investigation, or verify them against durable event records before sending a frequency claim.

Working Python program

class FrequentIncidentCandidates:
    def __init__(self, slots):
        if slots < 1:
            raise ValueError("slots must be positive")
        self.slots = slots
        self.counts = {}
        self.seen = 0

    def record(self, incident_code):
        self.seen += 1
        if incident_code in self.counts:
            self.counts[incident_code] += 1
        elif len(self.counts) < self.slots:
            self.counts[incident_code] = 1
        else:
            for resident in list(self.counts):
                self.counts[resident] -= 1
                if self.counts[resident] == 0:
                    del self.counts[resident]

    def candidates(self):
        return sorted(self.counts)


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 = FrequentIncidentCandidates(2)
for incident_code in incident_stream:
    summary.record(incident_code)
print("seen=", summary.seen, "candidates=", summary.candidates(), sep="")

Output

seen=11candidates=['pump-47', 'sensor-61']

Time, space, and tradeoff

A matching or free-slot update takes expected O(1) dictionary work. When all K slots are occupied, decrementing and deleting counters takes O(K) worst-case time. Space is O(K), independent of stream length; that bound excludes retention of the input for a later verification pass. Total work over N records is O(NK) with this direct Python loop as a conservative bound. The algorithm does not identify the exact top K by rank, handle negative corrections, or promise that every returned key passes the threshold. If exact counts are needed without a replay source, store them separately at the cost of unbounded distinct-key space.

Common Mistakes

Do not interpret residual counter values as exact frequencies.
Do not discard a key above N/(K+1) from the final candidate set.
Do not call every surviving key a verified heavy hitter.
Do not apply insertion-only cancellation to negative updates without another model.

Connected lessons

Compare its result with Space-Saving: ranked candidates with count bounds, HyperLogLog: estimate unique IDs with fixed registers, Reservoir sampling: keep a uniform fixed-size sample, then complete the bounded-stream audit and contract quiz.

data structures

range-query-structures