Questions tagged [streaming]

The tag has no usage guidance.

4 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers

Estimating the cardinality of multisets given some sets of different sizes

The count-distinct problem is: given a stream of elements $x_1, \dots, x_n$ which contains duplicates, find the number of distinct elements using a small amount of space. I also want the following ...
user1246462's user avatar
4 votes
0 answers

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 ...
R B's user avatar
  • 9,448
4 votes
1 answer

Does bisimulation or the approximation lemma work for monadic streams?

For ordinary streams $S_A := \nu X. A \times X$, there is a bisimulation lemma. It says that two streams are equal if there exists a bisimulation between them. A bisimulation is a relation $\sim$ on ...
Turion's user avatar
  • 616
3 votes
0 answers

Streaming Algorithm Lower Bounds by Communication Complexity

I am learning the methods for proving lower bounds on streaming algorithms using communication complexity. My question is about a basic technique to prove lower bounds on streaming models using the ...
echuly's user avatar
  • 549