References

Bibliography

This list is not meant to be bibliographically rigorous, but just to help you find links to the papers; that's why sources are often incomplete or not to the final archival version. Better search DBLP if you want to cite propertly.

On the other hand, some of the papers are here for historical completeness, you probably have better sources than the original one if you want to know what they do.

Surveys on stream algorithmics:
Lecture 1:
Lecture 2:
  • Noga Alon, Yossi Matias, Mario Szegedy: The space complexity of approximating frequency moments. J. Comput. Syst. Sci. 58(1): 137-147 (1999). Conference version, Symp. on the Theory of Computing (STOC) 1996.
  •  Piotr Indyk, David P. Woodruff: Optimal approximations of the frequency moments of data streams. STOC 2005: 202-208. The paper concentrates on proving lower bounds, which is out of the scope of this course. 
For more on HyperLogLog and the graph neighborhood estimation:
Lecture 3:
And more on the CM-sketch
Lecture 4:

No comments:

Post a Comment