11
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 logspace" and you will find plenty of references. (Typically, past work treats it as a reducibility concept.) The papers that those papers reference should cover ...
8
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 of size $O(\log n)$.
at each step, you read a new letter $a\in\Sigma$ of your stream, and you are allowed to modify your memory $m$
you then have to say whether ...
7
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 a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space.
Approximate bit counting on a sliding ...
6
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. At start, we have an empty word and then we receive updates taking one of the following forms:
Insert a letter at the beginning of the word
Insert a letter at ...
6
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 working in the RAM model with cells of size logarithmic in the maximal size of the window, and that all the operations regarding the automaton are constant time.
...
5
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 $h\in H$ from the family, for any set $S$ of $n$ elements, for any $x\notin S$, $\Pr_{h\in \mathcal{H}}[h(x) < \min_{y\in S} \{h(y)\}] = \frac{1}{n+1}$. ...
4
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.
4
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 suspect students would find this a good motivation. The algorithm that Redis uses, HyperLogLog, may be too difficult to analyze in an undergrad course. But, ...
4
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 that works by only maintaining a linear sketch and uses only slightly more space. So to prove a space lower bound in the turnstile model it is (up to some ...
3
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 the algorithm to a distinct memory configuration. The implied lower bound is then the log of the number of such inputs.
For example, Datar et al. showed (...
2
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 of times it is included in the sample will be proportion to its frequency in the stream. If the frequency of every item is small compared to $1/m$, the ...
2
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 a communication complexity lower bound won't work. By this, I mean that no matter how we cut the input into two parts and give it to two players, A and B, A ...
2
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 shows that with a sketch of size $O(\varepsilon^{-1}\log 1/\delta)$ you can compute a $\tilde{w}_i$ so that $\tilde{w_i} \geq w_i$ always, and $\tilde{w}_i \leq ...
2
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 solution, but it's a start.
Weighted Heavy Hitters Algorithm.
Input: $S=\{(\text{id}_i,\text{weight}_i)\}_{i=1}^N$ a weighted stream.
1. Create an unweighted ...
2
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 precision arithmetic
Suppose we want to sample a discrete random variable $X$ from a distribution with cdf $F$ (i.e., $F(x) = \Pr[X \le x]$). Then one ...
1
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's known that this problem requires Alice to transmit at least $n$ bits to Bob.
Now we first construct a graph which has a path of length $3$ from $s$ to $t$ if ...
1
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 randomly from $D^n$.
For a simple example, consider the case where $B=2$ and $D$ is the uniform distribution on $\Sigma$. Then
$$l_0 \approx {\lg(n^2/2) \...
1
Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.
1
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 cryptographic hash functions will be much more expensive than computing k fast non-cryptographic hash functions, e.g. MurmurHash.
In practice, I think most people use ...
1
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 avoided, because the full strength of cryptographic pseudorandmness is usually a huge overkill for streaming. If your streaming algorithm uses a small amount of ...
Only top voted, non community-wiki answers of a minimum length are eligible
