TITLE: Processing Aggregate Queries over Continuous Data Streams

In this talk, I will describe techniques for given approximate answers for aggregate queries over data streams using probabilistic "sketches" of the data streams that give approximate query answers with provable error guarantees. I will introduce sketches, and then talk about two recent technical advances, sketch partitioning and sketch sharing. In sketch partitioning, existing statistical information about the stream is used to significantly decrease error bounds. Sketch sharing allows to improve the overall space utilization among multiple queries. I will conclude with some open research problems and challenges in data stream processing.

Part of this talk describes joint work with Al Demers, Alin Dobra, and Mirek Riedewald at Cornell and Minos Garofalakis and Rajeev Rastogi at Lucent Bell Labs.