tag

#heavy-hitters

3 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Space Saving

Space Saving Algorithm Space Saving tracks frequent items in a stream using a fixed number of counters, similar to Misra Gries, but with better accuracy in practice. It maintains estimates for item frequencies and guarantees bounded error. Unlike Misra Gries, it does not decrement all counters. Instead, it replaces the smallest counter when needed. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ maintain approximate counts for the most...
algorithms streaming heavy-hitters approximate
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Streaming Heavy Hitters

Streaming Heavy Hitters Streaming Heavy Hitters finds items that occur frequently in a stream. The stream may be too large to store, so the algorithm keeps only a compact summary. The usual goal is to report all values whose frequency is above a threshold, or to estimate the most frequent values. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ find items whose frequency is large compared with $n$....
algorithms selection streaming heavy-hitters frequency
Wiki › Algorithms › 01. Searching and Sorting › 5. Selection and Order Statistics ›

Misra Gries

Misra Gries Misra Gries is a deterministic streaming algorithm for finding frequent items with bounded memory. It keeps at most $k - 1$ counters and returns a small candidate set that contains every item whose frequency is greater than $n/k$. The algorithm may return extra candidates. A second pass gives exact frequencies and removes false positives. Problem Given a stream $$ x_1, x_2, \dots, x_n $$ and an integer $k...
algorithms streaming heavy-hitters frequency