Algorithmic Techniques for Taming Big Data (DS-563/CS-543, Spring 2024)

Course Description: Growing amounts of available data lead to significant challenges in processing them efficiently. In many cases, it is no longer possible to design feasible algorithms that can freely access the entire data set. Instead of that, we often have to resort to techniques that allow for reducing the amount of data such as sampling, sketching, dimensionality reduction, and core sets. Apart from these approaches, the course will also explore scenarios in which large data sets are distributed across several machines, or even geographical locations, and the goal is to design efficient communication protocols or MapReduce algorithms.

The course will include a final project and programming assignments in which we will explore the performance of our techniques when applied to publicly available data sets. Throughout the course, we will explore various strategies for implementing techniques that have theoretical guarantees in practice.

Syllabus: [pdf]

Instructor: Krzysztof Onak (konak@bu.edu)
Office Hours: Mondays 3–5pm, CCDS 1443 (or the adjacent common area)

Teaching Assistant: Rathin Desai (rathin@bu.edu)
Office Hours: Friday 1–3pm, CCDS 15th floor, yellow southwest corner

Lecture: Tuesday/Thursday 3:30–4:45pm, CDS 264
Discussion sections:
• Wednesday 1:25–2:15pm, IEC B07
• Wednesday 2:30–3:20pm, IEC B07

Piazza (announcements and discussions): https://piazza.com/bu/spring2024/ds563cs543
Gradescope code for submitting homework: 6G4V6G

Lectures

Thursday 1/18: Class topics and logistics. Introductions. [Syllabus]
Tuesday 1/23: CountMin Sketch. [Notes]
Thursday 1/25: CountMin Sketch (continued). Streaming and linear sketching algorithms. [Notes]
Tuesday 1/30: Deterministic estimates (Misra–Gries). [Notes]
Thursday 2/1: Frequency moments. AMS sketch for $F_2$. [Notes]
Tuesday 2/6: Approximating the number of distinct elements. [Notes]
Thursday 2/8: Dangers of randomness. Insertion–only adversarially robust streaming algorithm for distinct elements. [Typed notes]
Tuesday 2/13: Snow day.
Thursday 2/15: Insertion–only adversarially robust streaming algorithm for distinct elements (continued). [Notes] [Typed notes]
Tuesday 2/20: Insertion/deletion adversarially robust streaming algorithm for distinct elements. [Typed notes]
Thursday 2/22: The Johnson–Lindenstrauss Lemma. [Typed notes]
Tuesday 2/27: The Johnson-Lindenstrauss Lemma (continued). Locality Sensitive Hashing for Near Neighbor Search.
Thursday 2/29: Locality Sensitive Hashing for Near Neighbor Search (continued).
Tuesday 3/5: Graph connectivity sketches. [Typed notes]
Thursday 3/7: Graph connectivity sketches (continued). [Typed notes] Coresets for quantiles.
Tuesday 3/19: Coresets for quantiles (continued).
Thursday 3/21: Coresest for $k$–median clustering.
Tuesday 3/26: Coresets for $k$-median clustering (continued). New themes: algorithms for distributions.
Thursday 3/28: Learning discrete distributions.
Tuesday 4/2: Uniformity testing. [Notes]
Thursday 4/4: Uniformity testing (continued). [Notes]
Tuesday 4/9: Uniformity testing (continued). Testing monotonicity of a sequence.
Thursday 4/11: Testing monotonicity of a sequence (continued).
Tuesday 4/16: Estimating the minimum vertex cover (and maximum matching) size.

Homework

Useful Auxiliary Materials

Useful probabilistic inequalities and more
There is no textbook. A good list of resources—including books, surveys, lectures notes, and presentations—on many topics covered in this class can be found at https://sublinear.info/index.php?title=Resources.
Another list of related courses: https://www.sketchingbigdata.org.