Streaming Algorithms

3 Credits · Level: Graduate, Undergraduate

This course will cover streaming algorithms for processing massive datasets. These are algorithms that process their inputs in a single pass, using very limited memory -- much less than the size of the input. They output small summaries, or "sketches", that are capable of (approximately) answering many questions about the input. Topics covered will include algorithms for counting the number of distinct elements in a stream, identifying frequent items, estimating a distribution from a stream of values, frequency moments, clustering, and computing properties of graphs. Efficient hash-based data structures will also be covered, including linear probing, double hashing, cuckoo hashing, and k-wise independence. Familiarity with basic probability theory is expected.