Questions tagged [sliding-window]
The sliding-window tag has no usage guidance.
3
questions
9
votes
0
answers
291
views
Additive error in counting the number of 1's in a sliding window?
The setting is as follows:
We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
- 9,378
8
votes
4
answers
627
views
Constraints on sliding windows
Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.
I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
- 992
4
votes
0
answers
239
views
What is known about finding heavy hitters in a sliding window?
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 ...
- 9,378