Questions tagged [streaming-algorithms]
The streaming-algorithms tag has no usage guidance.
33
questions
17
votes
1
answer
1k
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 ...
- 511
9
votes
0
answers
303
views
Additive error in counting the number of 1's in a sliding window?
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 ...
- 9,408
8
votes
4
answers
672
views
Constraints on sliding windows
Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.
I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
- 992
8
votes
2
answers
506
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:
...
- 11.3k
8
votes
2
answers
296
views
New Space Lower-Bound Techniques for Streaming Algorithms
Is communication complexity (CC) the only known approach for streaming algorithms lower bounds? Are there any other techniques, even if conditional lower bounds?
In general, are we satisfied with the ...
- 81
7
votes
1
answer
208
views
Complexity class of efficient streaming algorithms
Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words:
$L \in \mathsf{StreamL}$ if there ...
- 852
7
votes
1
answer
1k
views
Reservoir sampling of distinct values
I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible.
In my case, the stream contains many duplicate values, ...
- 509
7
votes
0
answers
276
views
Integer queue summation
As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue.
The setting is as follows: Let $\epsilon>0$. we need to maintain a space-...
- 9,408
6
votes
2
answers
283
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
3
answers
952
views
Algorithm for finding heavy hitters in a weighted stream
The problem of finding heavy hitters in a stream is defined as follows: given a $N$ sized stream of elements, return a set $\mathcal D$, such that every item which arrived at least $N\theta$ times ...
- 9,408
6
votes
0
answers
342
views
Counting distinct elements in a stream with expiration
Counting the number of distinct elements in a stream is a well-known and studied problem in computer science, for example Flajolet-Martin algorithm.
There are algorithms for calculating the number of ...
6
votes
0
answers
156
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
6
votes
0
answers
156
views
Framing the Count-Min Sketch as a Random Projection?
The count-min sketch data structure is used to estimate the frequencies of individual elements in a data stream. The authors note that the analysis of their data structure is simpler than other ...
- 1,921
6
votes
0
answers
113
views
Lower bounds for randomized frequency estimation algorithms
Consider a stream of elements $s_1s_2\ldots s_N$.
A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"?
It ...
- 9,408
5
votes
1
answer
153
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 \...
- 11.1k
5
votes
0
answers
157
views
Reconstruction of sparse vectors from random matrices
In the paper [A], the following linear algebra result (Lemma 5 in [A]) is stated as being well known. Note that a vector is $s$-sparse if it contains at most $s$ non-zero entries.
Lemma: Let $1 \...
4
votes
1
answer
134
views
Sublinear finite-precision sampling in a stream
I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem.
On a ...
- 11.1k
4
votes
0
answers
78
views
Universal Relation
In the paper Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems, the authors consider the universal relation problem in 2-party communication complexity, which is ...
- 41
4
votes
1
answer
176
views
Why not solve s-sparse recovery on a stream by tracking moments?
A slightly simplified version of $s$-sparse recovery streaming problem is the following. We get a stream of $n$ elements of the form $(x, \Delta)$, where $x \in [u]$ is a member of the universe, and $...
- 2,333
4
votes
0
answers
71
views
Constructing a bad sequence for counter algorithm
Assume that we want to construct a sequence $s\in\{a,b\}^{N}$ such that $s$ contains exactly $n$ times the letter '$a$'.
The sequence is then feed to the following probabilistic algorithm:
...
- 9,408
4
votes
0
answers
250
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,408
3
votes
2
answers
832
views
Sampling distinct values with probability proportional to their frequency
This is a variant of my previous question (Reservoir sampling of distinct values)
I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass ...
- 509
3
votes
0
answers
179
views
Finding median in a changing array
Consider the problem of needing to support an $n$ integers array structure with two operations:
Set(k,v) - set the $k$'th integer to value $v$ (i.e. $A[k]=v$).
Median() - return the median value of ...
- 9,408
2
votes
2
answers
307
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-...
- 11.3k
2
votes
0
answers
141
views
On-line pagerank in a streaming DAG (Directed Acyclic Graph)
Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices ...
- 693
2
votes
0
answers
87
views
Dynamic connectivity with known history, for maximal connected component span
Consider a graph in which edges are added and removed over time. Define the span of a connected component as the product of its number of vertices and the longest duration for which it remains a ...
- 693
2
votes
0
answers
33
views
Pagerank update upon vertex removal
Assume we have computed the Pagerank of the vertices of a given graph. Then, remove a vertex from this graph, with all its edges.
How to efficiently compute the Pagerank of remaining vertices in the ...
- 693
2
votes
0
answers
276
views
Streaming algorithms for sum
First of all, I am not sure whether this is a research level question. Please let me know if it is not.
The question is about streaming algorithms for the sum of the given data stream. From ...
- 1,345
2
votes
0
answers
114
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 ...
- 393
1
vote
1
answer
297
views
Estimate the maximum frequency of substring with given length in a very long character stream
Suppose there is a very long string $S\in \Sigma^N$ with length $N$, where $\Sigma$ is a relatively small alphabet (for example, $\Sigma=\{'a', 'b', \ldots, 'z'\}$). Now, given a budget $B$, the goal ...
- 191
0
votes
2
answers
268
views
Finding top-K items in a sliding window
Imagine we have a stream of bank transactions.
Each transaction has a target account and some amount of money.
I'd like to find top K accounts over some period of time (e.g. last 7 days) which ...
- 233
0
votes
0
answers
70
views
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, ...
- 1
-1
votes
1
answer
230
views
Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph
I am asked to prove that an O(1)-pass randomized streaming algorithm that solves s-t connectivity problem in a simple directed graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility $>\frac{...
- 13