Mergeable Summaries for Heavy Hitters

202503031501
Status: #idea
Tags: UtahDB

Mergeable Summaries for Heavy Hitters - Misra-Gries and SpaceSaving Algorithms

Maintains $k$ counters
Steps
1. If item is tracked, counter++
2. If not tracked
  1. If space → Add with count 1
  2. If no spacee → counters--, and if counter=0, remove it

Info

Dropping things as a batch improves runtime, which is why we prefer to remove all 0’s aggressively, instead of dropping as we need space.

Merge the matching elements
If we have more than $k$ elements, we prune (repeatedly)
- Find the $(k + 1)$ th element, call it $C_{k + 1}$
- Subtract $C_{k + 1}$ from all elements
- Prune all elements $\leq 0$

Attention

We could alternatively sort it, and prune everything after the largest $k$ elements

Tldr

When you merge multiple MG summaries, you are not worse-off in terms of error