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 ...
- 26.7k
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 ...
- 131
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 ...
- 18.1k
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.
- 351
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 ...
- 18.1k
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 ...
- 2,196
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'...
- 74
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 ...
- 18.1k
Only top scored, non community-wiki answers of a minimum length are eligible