Media Summary: MapReduce: TeraSort, minimum spanning tree, triangle counting. External memory model: linked list, matrix multiplication, B-tree, buffered repository tree, sorting. ℓ1/ℓ1 recovery, RIP1, unbalanced expanders, Sequential Sparse Matching Pursuit.
Algorithms For Big Data Compsci 229r Lecture 24 - Detailed Analysis & Overview
MapReduce: TeraSort, minimum spanning tree, triangle counting. External memory model: linked list, matrix multiplication, B-tree, buffered repository tree, sorting. ℓ1/ℓ1 recovery, RIP1, unbalanced expanders, Sequential Sparse Matching Pursuit. Linear least squares via subspace embeddings, leverage score sampling, non-commutative Khintchine, oblivious subspace ... Necessity of randomized/approximate guarantees, linear sketching, AMS sketch, p-stable sketch for p less than 2. Low-rank approximation, column-based matrix reconstruction, k-means, compressed sensing.
Khintchine, decoupling, Hanson-Wright, proof of distributional JL lemma. Amnesic dynamic programming (approximate distance to monotonicity). P-stable sketch analysis, Nisan's PRG, ℓp estimation for p Communication complexity (indexing, gap hamming) + application to median and F0 lower bounds.
