Data Stream Algorithms
Notes from Barbados 09 Complexity Theory Meeting, by S. Muthukrishnan
The course covered: 1. Data stream model. CM Sketch and its applications to point estimates, rangesum, heavy hitters, quantiles etc. These use 1/\eps log (1/\delta) space, get accuracy upto additive \eps X with prob at least 1\delta, and rely on pairwise hash functions. The same structure with 4wise independent hash functions gives relative error (1+\eps) approximation for F_2 (sum of squares of frequencies) and inner product with additive L_2 error guarantees using space (1/\eps^2)... The results are in
 Reading material: Book pdf
Overall comments:

I will keep tweaking these notes.