Data Stream Theory & Summer School

One of the areas where theoretical computer science has been successful is in introducing the data stream model for processing massive data sets, developing key algorithms, and connecting it to fundamental problems in communication complexity, embeddings and others. The basic theory arises from:

• Henzinger, Raghavan and Rajagopalan (HRR): Computing on data streams.
• Alon, Matias and Szegedy (AMS): The space complexity of approximating frequency moments.
• Indyk: Stable distributions, ...

Since then, the model and algorithms have found tremendous success with applications in databases and networking; AMS got the Godel prize; basic problems now have tight bounds (lower bounds eg by Woodruff, upper bounds eg by Ganguly). The area is thriving with new directions (Graph, geometric streams and recent works by Guha and others that connects to problems in Statistics).

It is now good to see a summer school on data stream theory. This is organized by the MADALGO center in Aarhus, Denmark, and the syllabus looks very well balanced between algorithmic and lower bound techniques (as well as Univ and Industry!). Wish I could be there to learn!