Questions tagged [streaming]
The streaming tag has no usage guidance.
13
questions
6
votes
2
answers
232
views
How to show that the median cannot be maintained in $O(1)$ time?
Suppose that we have a stream of numbers $x_1,x_2,\ldots$ such that we wish to track the median of the values observed so far.
This task is easy to do with $O(\log n)$ update time (where $n$ is the ...
- 63
6
votes
0
answers
142
views
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 ...
- 87
4
votes
1
answer
78
views
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 ...
- 574
5
votes
1
answer
151
views
Single-pass streaming quantile estimation using moments
Is it possible to estimate within $\epsilon$ the quantiles of a set of integers $\{x_1, x_2, \dots, x_n\}$ given only the values $\sum x_i^0,\sum x_i^1, \sum x_i^2, \dots, \sum x_i^{f(n)}$ where $f \...
- 11k
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,358
18
votes
2
answers
789
views
Bounds on the size of the smallest NFA for L_k-distinct
Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal:
$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]...
- 9,358
0
votes
1
answer
84
views
"Computing on data streams" clarification
In the 1998 technical note "Computing on data streams" by Monika Rauch Henzinger , Prabhakar Raghavan , Sridar Rajagopalan (found here: http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf)
...
- 113
3
votes
0
answers
374
views
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 ...
- 549
7
votes
1
answer
910
views
Streaming Algorithms: Motivations for estimating frequency moments
The celebrated AMS paper "The space complexity of approximating the frequency moments" defines the problem as following:
Let $a_1, a_2,\dotsc, a_m$ be a sequence of integers where each $a_j \in \{1,2,...
- 395
0
votes
1
answer
158
views
Functions and Counting Problems in Streaming Computation
I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08（Paul Beame and Trinh Huynh. On the ...
- 317
4
votes
1
answer
262
views
What's the strict definition of random coins in streaming algorithm?
I have a very basic question about random bits in streaming. How could a streaming algorithm use them? Can the algorithm use the same random bit at the start of the execution and look at it again ...
- 331
5
votes
1
answer
266
views
Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?
I was reading the paper "Recognizing Well-Paranthesized Expressions in the Streaming Model" by Magniez, Mathieu and Nayak where they give upper and lower bounds on the space required to recognize DYCK(...
- 1,631
12
votes
3
answers
462
views
Streaming derandomization
Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been ...
- 31.7k