Algorithms for Big Data

• the lecture notes: CS 598: Algorithms for Big Data

1 Introduction

2 Estimating Number of Distinct Elements in a Stream

3 Estimating \(F_k\) norms via AMS sampling

4 Estimating \(F_2\) norm, Sketching, Johnson-Lindenstrauss Lemma

5 Estimating \(F_p\) norm for \(0 < p < 2\), Misra-Greis algorithm for frequent items