4
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 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$
    – Sasho Nikolov
    Jun 18, 2014 at 15:35

0

Reset to default

Your Answer

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