Questions tagged [streaming]
The streaming tag has no usage guidance.
12
questions
6
votes
0answers
141 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 ...
4
votes
1answer
77 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 ...
5
votes
1answer
147 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 \...
4
votes
0answers
235 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 ...
18
votes
2answers
773 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]...
0
votes
1answer
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)
...
3
votes
0answers
370 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 ...
7
votes
1answer
899 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,...
0
votes
1answer
156 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 ...
4
votes
1answer
257 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 ...
4
votes
1answer
258 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(...
12
votes
3answers
457 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 ...
