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}$.

  • 1
    $\begingroup$ Just a thought: if you can get a sliding window version of the CM sketch (which is very related to the Bloom filter), then well-known reductions should give a heavy-hitters algorithm as well. I imagine some dyadic intervals trick could give a sliding window CM sketch. $\endgroup$ Jun 18, 2014 at 15:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.