This question is strongly related to another question I asked here a few weeks ago.In this problem setting we have a stream of elements $s_1,s_2,...$, such that $\forall i: s_i\in \mathcal X$ for some set $\mathcal X$.At time $t$ we get $s_t$, and required to update our data structure to be able to answer queries of the form did $x$ ($x\in \mathcal X$) appear at least $N\epsilon$ times in the last $N$ elements in the stream ($s_{t-N+1},s_{t-N+2},\dots ,s_{t}$)?.What is the best algorithm (memory-wise, and then runtime as a secondary objective) that answers these queries correctly w.p. 1?Two related papers, which implement a sliding bloom filter (answering queries of the form did $x$ appear at least once in the last $N$ elements) appeared last year, one by Naor and Yogev and the other by Dautrich and Ravishankar.These results can be seen as a special case of the sliding heavy hitters problem for $\epsilon=\frac{1}{N}$.
What is known about finding heavy hitters in a sliding window?
ds.algorithms;streaming;streaming algorithms;sliding window