The Online Event-Detection Problem

Michael A. Bender, Jonathan W. Berry, Martin Farach-Colton +5

Given a stream $S=(s_1,s_2,...,s_N)$, a $\varphi$-heavy hitter is an item $s_i$ that occurs at least $\varphi N$ times in $S$. The problem of finding heavy-hitters has been extensively stu…