Class Description

Data Mining is concerned with efficiently extracting statistics, patterns, structures, or meanings from raw data. This task becomes challenging when the volume of data is massive, as is standard in modern datasets. This course surveys foundational algorithms, mathematical concepts, and data structures for analyzing large-scale datasets, with a particular emphasis on randomization and the streaming model — where items (integers, strings, documents, sets, or matrix entries) arrive one at a time and must be processed under severe space limitations.

Topics covered include data sampling and reservoir sampling, finding frequent items and itemsets in data streams, Bloom filters and sketches, counting distinct elements and general frequency moment estimation, random projections and the Fast Johnson-Lindenstrauss Transform (FJLT), Singular Value Decomposition (SVD), matrix sampling and deterministic matrix sketching (Frequent Directions), k-means clustering, spectral graph theory, and exact and approximate nearest neighbor search (Locality Sensitive Hashing) in high dimensions.

The lecture notes present algorithms in their most basic form for didactic clarity. Correctness proofs are designed to be as simple and self-contained as possible, each presentable in roughly one long frontal session. An advanced undergraduate or graduate student with experience in probability, linear algebra, algorithms, and combinatorics should be able to follow the course. The class is devoted to ideas, algorithms, and proofs — as one student memorably noted in course feedback: “you think you’re going to get an interesting course and you end up getting a load of math.”

Syllabus & Class Notes

Below is the complete curriculum organized by lecture topic, linking to the primary Fall 2013 lecture notes alongside earlier editions from Fall 2012 and Fall 2011.

Lecture 1 — Probability Recap (PDF) & Mark and Recapture (PDF) [2012 Recap · 2012 M&R · 2011 Prelim · 2011 M&R]
- Discrete and continuous random variables, probability distributions, and expectation.
- Conditional expectation, dependence vs. independence, linearity of expectation, and additivity of variance.
- Markov’s inequality and Chebyshev’s inequality.
- Mark and recapture: estimating population size n from two independent samples of size k via collision counts and linearity of expectation.
Lecture 2 — Probabilistic Inequalities (PDF) & Sampling from Streams (PDF) [2012 Chernoff · 2012 Sampling · 2011 Sampling]
- Chernoff’s bound: full proof via exponential moment generating functions and multiplicative forms for sums of independent Bernoulli trials.
- Subset size estimation via uniform random sampling and sample complexity bounds.
- The union bound: simultaneous accuracy guarantees across m subsets with only logarithmic overhead.
- Uniform sampling from streams of unknown length, Fisher–Yates shuffling, and Reservoir Sampling.
Lecture 3 — Item Frequency Estimation in Streams (PDF) [2012 Notes · 2011 Count Sketches · 2011 Bloom Filters]
- The heavy hitters and item frequency estimation problem in data streams using sublinear o(n) memory.
- Count-Min Sketch (Cormode & Muthukrishnan; Manku & Motwani): reducing space dependence on ε from O(1/ε²) to O(log(n/δ)/ε).
- Deterministic Frequent Items / Lossy Counting (Misra & Gries; Demaine et al.; Karp, Papadimitriou & Shenker): O(1/ε) space and O(1) amortized update time.
- Count Sketch (Charikar, Chen & Farach-Colton): random sign hashes and median-of-buckets aggregation for ℓ₂ residual tail guarantees.
- Bit-hashes vs. Bloom filters (2011 Notes): reducing space from O(n/δ) to O(n log(1/δ)) bits using k = O(log(1/δ)) hash functions.
- Frequent itemsets in market-basket data (2011 Agenda · Dynamic Itemset Counting): Apriori, prefix tries, and DIC.
Lecture 4 — Frequency Moment Estimation in Streams (PDF) [2012 Notes · 2011 Notes]
- Frequency moments f_k = ∑_i n_i^k: distinct elements (f₀), stream length (f₁), and repeat rate / skew (f₂).
- Estimating f₀ (distinct elements) via minimum hash values (Alon, Matias & Szegedy; Cohen).
- Estimating general frequency moments f_k (k > 0) via the AMS estimator X = N(r^k − (r−1)^k).
- Estimating the second moment f₂ in O(1/(ε²δ)) space via random ±1 projections (Tug-of-War sketch) and its connection to norm-preserving random projections.
Lecture 5 — Random Projection & The Johnson-Lindenstrauss Lemma (PDF) [2012 Notes · 2011 Notes]
- Metric distortion and dimensionality reduction for pairwise Euclidean distances.
- The Johnson-Lindenstrauss Lemma: embedding n points into k = O(log(n)/ε²) dimensions with (1 ± ε) distortion.
- Random projections via matrices with independent normally distributed (Gaussian) entries and sub-Gaussian tail bounds.
Lecture 6 — Fast Random Projection (FJLT) (PDF) [2012 Notes (Sec. 3–5)]
- Accelerating Johnson-Lindenstrauss projections from O(kd) to O(d log d) time (Ailon & Chazelle; Ailon & Liberty).
- Fast vector ℓ₄-norm reduction (vector spreading) via randomized Walsh–Hadamard transforms and Khintchine’s inequality.
- Importance sampling and sparse random projections on vectors with bounded ℓ₄ norm (‖x‖₄ = O(d^−1/4)).
Lecture 7 — Singular Value Decomposition (SVD) & PCA (PDF) [2012 Notes · 2011 SVD · 2011 Power Method]
- Geometry, existence proof, and fundamental properties of the Singular Value Decomposition A = UΣV^T.
- Eckart–Young–Mirsky Theorem: optimal rank-k matrix approximation in both the spectral norm and Frobenius norm.
- Data mining applications: least-squares linear regression (pseudo-inverse), Principal Component Analysis (PCA), and closest orthogonal matrix.
- Computing the SVD of large matrices via the Power Method (simultaneous iteration).
Lecture 8 — Matrix Sampling and Rank-k Approximation (PDF) [2012 Notes · 2011 Ahlswede–Winter Notes]
- Accelerating eigenvector and SVD computation by sparsifying dense matrices.
- Element-wise matrix sampling: picking entries with probability proportional to squared magnitude (Arora, Hazan & Kale; Drineas & Zouzias).
- Matrix concentration inequalities: the Matrix Bernstein / Chernoff bound and the Ahlswede–Winter inequality.
Lecture 9 — Matrix Approximation Continued: Column Sampling & Deterministic Matrix Sketching (PDF)
- PCA with an approximate covariance matrix and additive-error rank-k bounds.
- Column subset selection by row/column norm-squared sampling (Drineas & Kannan; Rudelson & Vershynin; Boutsidis, Drineas & Magdon-Ismail).
- Deterministic Matrix Sketching / Frequent Directions (Liberty, 2012): streaming matrix covariance approximation analogous to the Misra–Gries frequent items algorithm.
Lecture 10 — k-Means Clustering (PDF) [2012 Notes]
- The k-means clustering objective (sum of squared Euclidean distances) and Lloyd’s iterative algorithm.
- Connection between k-means and PCA: spectral relaxation of cluster indicator matrices (Zha et al.; Ding & He) and 2-approximation via rank-k SVD projection.
- ε-net argument for k-means in fixed low dimensions.
- Sampling-based seeding, coresets, and k-means++ (Arthur & Vassilvitskii).
Lecture 11 — Nearest Neighbor Search and the Curse of Dimensionality (PDF) [2012 Notes]
- Exact and (1 + ε)-approximate nearest neighbor search problem formulations.
- Space-partitioning data structures: k-d trees (Bentley, 1975), construction, and range/nearest-neighbor query traversal.
- The Curse of Dimensionality: why k-d trees inspect Ω(2^d) cells in high dimensions, concentration of volume near the boundary of high-dimensional balls and cubes, and near-orthogonality of random vectors.
Lecture 12 — Approximate Nearest Neighbor Search & Locality Sensitive Hashing (PDF) [2012 Notes · 2011 Notes]
- Reduction from Approximate Nearest Neighbor Search to the (c, r)-Approximate Near Neighbor decision problem.
- Locality Sensitive Hashing (LSH) families (Gionis, Indyk & Motwani): amplifying collision probability gaps via concatenation and multiple hash tables in O(n^ρ) query time, where ρ = log(p₁)/log(p₂).
- LSH constructions: bit sampling on the Hamming cube {0,1}^d with ρ = 1/c, similarity search, and random hyperplane rounding (SimHash, Charikar) on the unit sphere S^d−1.
Additional Topics (2011 & 2012 Editions) — Spectral Graph Theory (PDF), Tree Metric Embeddings (PDF) & Partial Match (PDF)
- Very Short Intro to Spectral Graph Theory (2012 Lecture 12): Adjacency matrix eigenvalue bounds and chromatic number; Markov transition matrices and stationary distributions of random walks; Graph Laplacian L = D − A, positive semi-definiteness, connected components, and the Fiedler vector for spectral clustering.
- Metric Embedding into Random Trees (2012 Lecture 8): Probabilistic embeddings of finite metric spaces into dominating tree metrics (notes from a course by Avner Magen).
- The Partial Match & Containment Query Problem (2011 Lecture 12): Inverted indexes, posting list intersection in search engines,equivalence of subset and containment queries, and sublinear-time randomized algorithms via dictionary sampling and representative sets (Charikar, Indyk & Panigrahy).

Course Editions & Materials Matrix (2011–2013)

Below is a side-by-side index of all lecture notes, home assignments, and exams across the three academic years taught at Tel Aviv University.

Session	Fall 2013	Fall 2012	Fall 2011
1	Probability Recap • Mark & Recapture	Probability Recap • Mark & Recapture	Preliminaries • Mark & Recapture
2	Probabilistic Inequalities • Sampling	Chernoff Bound • Sampling	Sampling
3	Item Frequency Estimation in Streams	Frequent Items in Streams HW 1: Assignment (Solutions)	Frequent Itemsets Agenda • Dynamic Itemset Counting
4	Frequency Moments in Streams HW 1: Assignment (Solutions)	Frequency Moments	Bit Hashes & Bloom Filters • Count Sketches
5	Random Projection	Random Projections & FJLT	Estimating Frequency Moments
6	Fast Random Projection (FJLT)	SVD and PCA HW 2: Assignment (Solutions)	Random Projections
7	Singular Value Decomposition	Matrix Sampling	Fast Random Projections
8	Matrix Sampling & Rank-k Approx. HW 2: Assignment (Solutions)	Metric Embedding into Trees	Singular Value Decomposition
9	Matrix Approximation Continued	Nearest Neighbor Search & k-d Trees	The Power Method • Ahlswede–Winter Recap
10	k-Means Clustering	ANNS & LSH HW 3: Assignment	Nearest Neighbor Search & k-d Trees
11	Nearest Neighbor Search & Curse of Dim.	k-Means Clustering	ANNS & Locality Sensitive Hashing
12	Approximate Nearest Neighbor Search	Intro to Spectral Graph Theory	The Partial Match Problem
Exams	Moed Alef: Exam (PDF)	Moed Alef: Exam (Solutions) Moed Beit: Exam (Solutions)	Moed Alef: Exam (Solutions) Moed Beit: Exam (Solutions)

Home Assignments & Exams

Self-contained problem sets and final examinations (Moed Alef and Moed Beit) with full worked solutions:

Home Assignments

Fall 2013, Assignment 1 — Problems (PDF) • Solutions (PDF)
- Probabilistic inequalities, approximating the size of a graph via neighborhood sampling, streaming approximate median, and simple high-capacity hashing.
Fall 2013, Assignment 2 — Problems (PDF) • Solutions (PDF)
- Randomized meta-algorithms (amplifying success probability via median-of-means), set intersections in streams, weak random projections, and SVD via the power method.
Fall 2012, Assignment 1 — Problems (PDF) • Solutions (PDF)
- Approximating the size of a tree via random root-to-leaf walks and streaming approximate histograms.
Fall 2012, Assignment 2 — Problems (PDF) • Solutions (PDF)
- Weak random projections and constant-factor norm preservation.
Fall 2012, Assignment 3 — Problems (PDF)
- Randomized meta-algorithms and spectral norm approximation via the power method.

Final Examinations (Moed Alef & Moed Beit)

Fall 2013, Exam Alef — Exam (PDF)
- Probabilistic inequalities, approximate item frequencies in streams, approximate median, and k-means clustering with equal cluster sizes.
Fall 2012, Exam Alef — Exam (PDF) • Solutions (PDF)
- Probabilistic inequalities, Monte Carlo integration of black-box functions, matrix sampling, and 2-means clustering.
Fall 2012, Exam Beit — Exam (PDF) • Solutions (PDF)
- Probabilistic inequalities, estimating the number of stars in the sky, estimating the number of users on Facebook via random walks, and simple high-capacity hashing.
Fall 2011, Exam Alef — Exam (PDF) • Solutions (PDF)
Fall 2011, Exam Beit — Exam (PDF) • Solutions (PDF)

Grading & Student Projects

Course evaluation is structured differently for undergraduate and graduate students:

Undergraduate Students: Home assignments (50% of the grade) and a Final Exam (50% of the grade). An optional final project is available for extra credit.
Master’s & PhD Students: Home assignments (50% of the grade) and a Final Project (50% of the grade; in Fall 2013, graduate students could elect either the Final Exam or the Final Project).

Final Project Guidelines

Scope & Effort: Projects can contain both theoretical and experimental elements and should require roughly one to two weeks of dedicated work — comparable to studying for and taking the final exam.
Deliverable: A single self-contained PDF report covering project motivation, background literature, dataset review, mathematical derivations, experimental results, pseudocode, and discussion.

Selected Literature

Foundational papers in streaming algorithms, sketching, random projections, randomized numerical linear algebra, clustering, and high-dimensional similarity search cited in the lecture notes:

A Fast Random Sampling Algorithm for Sparsifying Matrices — Sanjeev Arora, Elad Hazan, and Satyen Kale (2006)
A Note on Element-wise Matrix Sparsification via Matrix-Valued Chernoff Bounds — Petros Drineas and Anastasios Zouzias (2010)
A Note on Sums of Independent Random Matrices After Ahlswede–Winter — Roman Vershynin (2011)
A Simple Algorithm for Finding Frequent Elements in Streams and Bags — Richard M. Karp, Christos H. Papadimitriou, and Scott Shenker (2003)
An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform — Nir Ailon and Edo Liberty (2011)
An Elementary Proof of the Johnson-Lindenstrauss Lemma — Sanjoy Dasgupta and Anupam Gupta (1999)
An Improved Data Stream Summary: The Count-Min Sketch and Its Applications — Graham Cormode and S. Muthukrishnan (2005)
Approximate Frequency Counts over Data Streams — Gurmeet Singh Manku and Rajeev Motwani (2002)
Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform — Nir Ailon and Bernard Chazelle (2006)
Clustering Data Streams: Theory and Practice — Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan (2003)
Exact Matrix Completion via Convex Optimization — Emmanuel Candès and Benjamin Recht (2012)
Extensions of Lipschitz Mappings into a Hilbert Space — William B. Johnson and Joram Lindenstrauss (1984)
Finding Frequent Items in Data Streams — Moses Charikar, Kevin Chen, and Martin Farach-Colton (2002)
Finding Repeated Elements — Jayadev Misra and David Gries (1982)
Frequency Estimation of Internet Packet Streams with Limited Space — Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro (2002)
K-Means Clustering via Principal Component Analysis — Chris H. Q. Ding and Xiaofeng He (2004)
k-means++: The Advantages of Careful Seeding — David Arthur and Sergei Vassilvitskii (2007)
Least Squares Quantization in PCM — Stuart P. Lloyd (1982)
Multidimensional Binary Search Trees Used for Associative Searching — Jon Louis Bentley (1975)
Near Optimal Column-Based Matrix Reconstruction — Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail (2011)
New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems — Moses Charikar, Piotr Indyk, and Rina Panigrahy (2002)
Pass Efficient Algorithms for Approximating Large Matrices — Petros Drineas and Ravi Kannan (2003)
Probabilistic Counting Algorithms for Data Base Applications — Philippe Flajolet and G. Nigel Martin (1985)
Sampling from Large Matrices: An Approach Through Geometric Functional Analysis — Mark Rudelson and Roman Vershynin (2007)
Similarity Estimation Techniques from Rounding Algorithms — Moses Charikar (2002)
Similarity Search in High Dimensions via Hashing — Aristides Gionis, Piotr Indyk, and Rajeev Motwani (1999)
Simple and Deterministic Matrix Sketching — Edo Liberty (2012)
Size-Estimation Framework with Applications to Transitive Closure and Reachability — Edith Cohen (1997)
Smaller Coresets for k-Median and k-Means Clustering — Sariel Har-Peled and Akash Kushal (2005)
Sparser Johnson-Lindenstrauss Transforms — Daniel M. Kane and Jelani Nelson (2012)
Sparsity Lower Bounds for Dimensionality Reducing Maps — Jelani Nelson and Huy L. Nguyen (2012)
Spectral Relaxation for K-Means Clustering — Hongyuan Zha, Xiaofeng He, Chris H. Q. Ding, Ming Gu, and Horst D. Simon (2001)
Streaming k-Means Approximation — Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni (2009)
Strong Converse for Identification via Quantum Channels — Rudolf Ahlswede and Andreas Winter (2002)
The Space Complexity of Approximating the Frequency Moments — Noga Alon, Yossi Matias, and Mario Szegedy (1996)

Contribute & Open Course Materials

All class notes, assignments, and exams are intended to be used freely by academics anywhere, students and professors alike. Contributions and corrections are highly encouraged in the form of pull requests or issues on GitHub.

On Unix-like systems (e.g., macOS or Linux) with bibtex and pdflatex available, you can compile all LaTeX lecture notes directly from source:

git clone https://github.com/edoliberty/algorithms-in-data-mining.git
cd algorithms-in-data-mining
./build.sh

Algorithms in Data Mining (0368-3248-01, Tel Aviv University, Fall 2011–2013)