11 votes
Accepted

How to show that the median cannot be maintained in $O(1)$ time?

If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$: first you compute a value $a$ smaller than all elements in the sequence and a value $...
  • 775
11 votes
Accepted

Complexity class of efficient streaming algorithms

Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it. Search for "one-way ...
8 votes

Streaming algorithms suitable for undergrad course

In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following: Reservoir sampling - maintain ...
  • 9,378
8 votes

Constraints on sliding windows

It seems it would depend on your particular model, in particular what information you have access to. From what I infer, you are thinking of the following model: you have a memory $m$, for instance ...
  • 7,897
6 votes
Accepted

Constraints on sliding windows

Here is a second, simpler and more general answer that was obtained after discussing with a3nm. Problem We fix a regular language $\mathcal{L}$ and we are interested in the following word problem. ...
  • 775
6 votes

Constraints on sliding windows

Context Let $\mathcal{L}$ be a fixed regular language and let ($\mathcal{Q}, \Sigma, \delta, q_0, \mathcal{F})$ be an automaton recognizing $\mathcal{L}$. I will suppose in this post that we are ...
  • 775
5 votes

Streaming algorithms suitable for undergrad course

There are several algorithms for estimating cardinality. This problem seems to be important enough in practice. For example, Redis, which describes itself as a ‘data structure server’, supports it. I ...
  • 4,746
5 votes
Accepted

Reservoir sampling of distinct values

This is something that min-wise independent hashing is good for. (See a wikipedia explanation here. The idea is to use a family $\mathcal{H}$ of hash functions so that when you pick a random function ...
4 votes

New Space Lower-Bound Techniques for Streaming Algorithms

A recent result of Li, Nguyen, and Woodruff shows that for any streaming algorithm in the turnstile model (where the stream consists of insertions and deletions of elements) there exists an algorithm ...
4 votes

Constraints on sliding windows

This seems to be exactly the type of question studied by Moses Ganardi and coauthors in recent years. In particular this paper and this extension prove nice trichotomies.
3 votes

Sublinear finite-precision sampling in a stream

The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number. Building block: sampling without arbitrary ...
  • 11.1k
3 votes

New Space Lower-Bound Techniques for Streaming Algorithms

While not new, (and depending on what you consider to be "streaming algorithms"), a standard lower bound technique is picking a (as large as possible) set of inputs, and proving that each has to lead ...
  • 9,378
2 votes

Computing parity of a permutation in a streaming-fashion way

I would like to ask everyone not to upvote this, as this is not an answer, but an extended comment, in which I would like to argue why this question did not receive any answers. My main point is, that ...
  • 13.8k
2 votes

Algorithm for finding heavy hitters in a weighted stream

If you allow randomization, the CountMin (CM) sketch can be used with weights without modification, and can also handle negative weights. When all weights are positive, the standard analysis of CM ...
2 votes

Algorithm for finding heavy hitters in a weighted stream

Here's a generic randomized solution. (Do we even have deterministic solutions in the unweighted case? Don't Space Saving and Batch Decrement both need hash maps?) This is probably not the ideal ...
  • 2,783
2 votes

Sampling distinct values with probability proportional to their frequency

If the problem is well-defined, I suspect it should be achievable using the following method. Pick a $m$ values uniformly at random from the stream. For each value, the expected value of the number ...
  • 11.1k
1 vote

Finding top-K items in a sliding window

Your problem may be solved (perhaps with small modifications) by the algorithms TiTiCount, TiTiCount+ and TiTiCount+h. These are algorithms that allows you estimating the frequencies and finding ...
1 vote
Accepted

Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph

Consider the communication problem INDEX where Alice has a $n$ bit string $x_1x_2x_3...x_n$ and Bob has an index $i \in [n]$ where Bob's goal is to learn whether the bit $i$ of $x$ is $1$ or not. It'...
1 vote

Estimate the maximum frequency of substring with given length in a very long character stream

If $D$ has high min-entropy, then there's a "sharp cut-off" phenomenom: there's a value $l_0$ depending only on $n,B$ such that the value of $l$ is almost always very close to $l_0$, when $S$ is drawn ...
  • 11.1k
1 vote
Accepted

Single-pass streaming quantile estimation using moments

Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.
  • 11.1k
1 vote

Sketches, using ideal hash functions

Another reason for not using cryptographic algorithms in practice is speed. In the streaming setting, we typically do not want to spend too long processing each item in the stream. Computing k ...
  • 111
1 vote

Sketches, using ideal hash functions

The obvious problem is that if you use a cryptographic pseudorandom number generator (PRNG), the correctness of your algorithm is conditional on a complexity conjecture. However, usually this can be ...

Only top scored, non community-wiki answers of a minimum length are eligible