Questions tagged [streaming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers

Finding lightest k elements in data stream using small space

There has been much research and progress devoted towards algorithms for finding approximate $\ell_p$-Heavy Hitters with parameter $\epsilon$ in the streaming setting (For all 3 of the vanilla, ...
BBenyani's user avatar
6 votes
2 answers

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 ...
Eli's user avatar
  • 63
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
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
5 votes
1 answer

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 \...
jbapple's user avatar
  • 11.2k
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
18 votes
2 answers

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

"Computing on data streams" clarification

In the 1998 technical note "Computing on data streams" by Monika Rauch Henzinger , Prabhakar Raghavan , Sridar Rajagopalan (found here: ...
S0rin's user avatar
  • 113
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
7 votes
1 answer

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,...
Jardine's user avatar
  • 395
0 votes
1 answer

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 ...
Jeigh's user avatar
  • 317
4 votes
1 answer

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 ...
Wei Yu's user avatar
  • 331
5 votes
1 answer

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(...
Vinayak Pathak's user avatar
12 votes
3 answers

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 ...
Suresh Venkat's user avatar