# Questions tagged [streaming-algorithms]

The tag has no usage guidance.

30 questions
Filter by
Sorted by
Tagged with
82 views

192 views

911 views

### Computing parity of a permutation in a streaming-fashion way

I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of ...
499 views

### Streaming algorithms suitable for undergrad course

I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course. Good choices should probably satisfy the following requirements: ...
290 views

### Sketches, using ideal hash functions

I've been reading about sketches for processing streaming data (the CountMin sketch, the Count sketch, the tug-of-war sketch, FM sketches, etc.). They use hash functions that are required to be 2-...
107 views

### Which paper to cite when referring to reservoir sampling *with replacement*?

As far as I can tell, the term "reservoir sampling" is commonly used to refer to sampling without replacement and references [1], [2], and [3] are cited while mentioning it. When referring to ...
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 ...
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 ...