ColloquiaTalk by Alin Dobra on April 4, 2003

[Margery Ishmael]

-------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE - TALK

Friday, April 4, 2003 at 2:30 pm in Ryerson 251

--------------------------------------------------------------------------

Alin Dobra, Cornell University
http://www.cs.cornell.edu/people/dobra

Title: Processing Aggregate Queries over Continuous Data Streams

Abstract:
Data management techniques for data streams has gained much importance
recently. The talk addresses techniques for approximately answering
aggregate SQL queries over continuous data streams with limited
memory. Our method relies on randomizing techniques that compute small
"sketches" of the streams that can be used to provide approximate
query answers with provable guarantees on the approximation error.
In this talk we give an introduction to sketches and we present our
two main contributions. First, we show how existing statistical
information about the data (e.g., histograms) can be used to improve
the quality of the approximations provided by our algorithms. The key
idea is to intelligently partition the domain of the join attributes
in a way that provably improves the approximation guarantees. Second,
in the presence of multiple queries, intelligent sharing of sketches
among concurrent queries can result in dramatic improvements in the
utilization of the available sketching space and in the quality of the
resulting approximation error. We will discuss some of the novel
optimization problems that arise in the context of multi-query sketch
sharing and describe our solutions.

(Joint work with Johannes Gehrke, Minos Garofalakis and Rajeev Rastogi)

Host: Partha Niyogi

*Refreshments will follow the talk in Ryerson 255*

People in need of assistance should call 773-834-8977 in advance.


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977 fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-