ColloquiaTalk by Rajeev Rastogi - November 13th, 2002

[Margery Ishmael]

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

DEPARTMENT OF COMPUTER SCIENCE

Wednesday, November 13, 2002 at 2:30 p.m. in Ryerson 251

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


Speaker: RAJEEV RASTOGI

From: Information Sciences Research Center, Bell Laboratories

Title: "Processing Continuous Network-Data Streams"

Abstract: For several network-management applications (e.g. network 
monitoring,
event correlation, fraud/anomaly detection), large volumes of network
data arrive and need to be processed in real time on a continuous (24x7)
basis, without the benefit of several passes over a static, persistent
data image. As a result, there is increasing interest in the design of
data-processing algorithms that work over such continuous data streams,
i.e. algorithms that work with limited memory to answer user queries
while looking at the relevant data items only once and in the fixed
order of arrival.

In this talk, I will discuss our work on providing approximate,
guaranteed-quality results to general SQL queries (with, possibly,
multiple join operations) over continuous data streams with limited
memory. Our method relies on randomizing techniques that compute
small "sketch" synopses of the streams that can then be used to
provide approximate answers with provable probabilistic guarantees
on the approximation error. We also demonstrate how existing statistical
information on the base data (e.g. histograms) can be used in the
proposed framework to improve the quality of the approximation provided
by our algorithms. The key idea is to intelligently partition the domain
of the underlying attribute(s) and, thus, decompose the sketching problem
in a way that provably tightens our guarantees. Finally, I will discuss
some of our ongoing work that aims to extend our techniques to deal with
multiple standing SQL queries as well as richer types of queries and
streaming data.

BIO: Rajeev Rastogi received the B. Tech degree in Computer Science from 
the Indian Institute of Technology, Bombay in 1988, and Masters and Ph.D. 
degrees in Computer Science from the University of Texas, Austin, in 1990 
and 1993 respectively. He joined Bell Laboratories in Murray Hill, New 
Jersey, in 1993 as a member of technical staff in the Information Sciences 
Research Center, and became a distinguished member of technical staff 
(DMTS) in 1998.
In 1999, he became the director of the internet management research department.
http://www.bell-labs.com/user/rastogi/

Host: Svetlozar Nestorov

*The talk will be followed by refreshments in Ryerson 255*

Persons with disabilities who may need assistance should call 773.834.8977
If you would like to meet with the speaker, please send e-mail to 
marge at cs.uchicago.edu


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=