8
$\begingroup$

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:

  • Solve a problem that is useful in practice or easy to motivate, or alternatively, illustrate techniques that are beautiful or useful.

  • Be suitable for presentation in an undergraduate algorithms course. This means the algorithm and analysis can't be too complex. Also they shouldn't require too much heavy probability theory to analyze (sadly, this rules out many beautiful algorithms).

What would be a good candidate?

One beautiful algorithm is the deterministic algorithm to find an element that occurs with frequency at least 50% (if any such element exists), using $O(1)$ space; or its generalization, find all items that occur with frequency at least $1/k$, using $O(k)$ space. Are there any others that would be an excellent choice for an undergraduate course?

Improve this question
$\endgroup$
2

2 Answers 2

Reset to default
8
$\begingroup$

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:

  1. 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.

  2. Approximate bit counting on a sliding window - given a bit-stream, answer queries approximating the number of $1$'s in the last $N$ bits, and do so using $O(\log N)$ space.

  3. Sampling from a sliding window (at any point, give a sample of $k$ elements uniformly chosen from the last $N$ elements of a stream).

  4. Exact item counting - answer queries of the form "how many times did $x$ appear in the stream" such that the answer will be correct w.h.p. using only sublinear space (modern data structures are quite complex, but Count–min sketch seems to fit undergrad course).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Exact item counting with high probability requires linear space. CM sketch approximates the item count by a factor proportional to the total count of all items. But I agree it's a good choice. $\endgroup$
    – Sasho Nikolov
    Commented Dec 1, 2014 at 18:44
  • $\begingroup$ Only issue is you have to handwave-away the fact that the hash functions can be stored in small space. $\endgroup$
    – arnab
    Commented Dec 2, 2014 at 8:37
5
$\begingroup$

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, there are some alternative algorithms that seem good for an undergrad course. One is to use the minimum value of all hash values seen. Another is to keep the maximum $k$ such that $2^k$ divides at least one of the hash values. The HyperLogLog paper is a good starting point for even more alternatives:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.