Questions tagged [streaming-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers
63 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 ...
user avatar
  • 51
6 votes
2 answers
237 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 ...
user avatar
  • 63
2 votes
1 answer
101 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 $...
user avatar
  • 2,293
2 votes
0 answers
100 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 ...
user avatar
0 votes
2 answers
213 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 ...
user avatar
  • 223
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 ...
user avatar
2 votes
0 answers
32 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 ...
user avatar
6 votes
0 answers
209 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 ...
user avatar
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 ...
user avatar
7 votes
1 answer
195 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 ...
user avatar
  • 842
8 votes
4 answers
627 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 ...
user avatar
  • 992
-1 votes
1 answer
198 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{...
user avatar
  • 13
4 votes
1 answer
130 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 ...
user avatar
  • 11k
1 vote
1 answer
269 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 ...
user avatar
  • 191
6 votes
0 answers
152 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 ...
user avatar
2 votes
0 answers
254 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 ...
user avatar
  • 1,345
3 votes
0 answers
175 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 ...
user avatar
  • 9,378
6 votes
0 answers
103 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 ...
user avatar
  • 9,378
4 votes
0 answers
70 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: ...
user avatar
  • 9,378
6 votes
3 answers
903 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 ...
user avatar
  • 9,378
7 votes
0 answers
258 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-...
user avatar
  • 9,378
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 \...
user avatar
  • 11k
3 votes
2 answers
793 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 ...
user avatar
7 votes
1 answer
959 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, ...
user avatar
8 votes
2 answers
291 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 ...
user avatar
5 votes
0 answers
154 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 \...
user avatar
16 votes
1 answer
938 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 ...
user avatar
2 votes
2 answers
299 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-...
user avatar
  • 10.4k
8 votes
2 answers
501 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: ...
user avatar
  • 10.4k
2 votes
0 answers
109 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 ...
user avatar
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 ...
user avatar
  • 9,378
9 votes
0 answers
291 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 ...
user avatar
  • 9,378