Maintain a $t \times k$ array $C$ of counters and $t$ hash functions $h_j$ mapping items to $[k]$, plus $t$ sign hash functions $g_j$ mapping items to $\{-1, +1\}$. Update: For item $i$, $C[j][h_j(i)] += g_j(i)$ for $j = 1, \dots, t$. Query: $\hat{f}_i = \text{median}_j C[j][h_j(i)] \cdot g_j(i)$

Find items with frequency $> \phi n$ (where $n$ is stream length). Misra-Gries: $O(k)$ space, guarantees $\phi = 1/(k+1)$. Count-Min + Heap: Track top items in a min-heap alongside sketch. Join Discord PreviousRandomized OptimizationNextSublinear Algorithms