- [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 toolsOn 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
- [Boucheron+04] S. Boucheron, O. Bousquet, G. Lugosi (2004). Concentration inequalities (much more material than we'll need in this seminar)
- [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.