References & links

They will be added as the course progresses. Please tell me about interesting ones that could be added.

General

• [Gama2010] J. Gama, ``Knowledge Discovery from Data Streams'', CRC Press 2010.
• [LibertyNelson] Edo Liberty, Jelani Nelson, ``Streaming Data Mining''.
• [Indyk2010] Piotr Indyk, ``Sketching, streaming, and sub-linear space algorithms''.
• [Bifetetal2012tutorial] Albert Bifet et al., ``Advanced Topics on Data Stream Mining''. Tutorial in ECML PKDD 2012.
• [MOA] MOA: Massive Online Analysis. 

Lecture 1: The data stream model. Counting. Probability tools

On approximate counting:

• [Morris77] Morris, R. Counting large numbers of events in small registers. Communications of the ACM 21, 10 (1977), 840–842.
• [Flajolet85] Flajolet, P. Approximate Counting: A Detailed Analysis. BIT 25, (1985), 113-134 (if you really want the analysis)
• [VanDurme+09] Benjamin Van Durme, Ashwin Lall. Probabilistic Counting with Randomized Storage. IJCAI 2009, 1574-1579.
• [Flajolet04] P. Flajolet. Counting by coin tossings. ASIAN 2004, Higher-Level Decision Making, 9th Asian Computing Science Conference.
• Sketch of the Day: HyperLogLog 

On large deviation bounds:

• [Boucheron+04] S. Boucheron, O. Bousquet, G. Lugosi (2004). Concentration inequalities (much more material than we'll need in this seminar) 

Lecture 2 

• [AMS99] Noga Alon, Yossi Matias, Mario Szegedy. The space complexity of approximating frequency moments. J. Computer and System Sciences 1999. Preliminary version in FOCS 1996.