Joint Colloquium Distinguished Lecture Series

Sketching Streams through the Net: Distributed Approximate Query Tracking

Wednesday, November 30th HP Auditorium, Soda Hall 4:00 Minos Garofalakis Senior Research Scientist Intel Research, Berkeley

Abstract:

While traditional database systems optimize for performance on one-shot query processing, emerging large-scale monitoring applications require continuous tracking of complex data-analysis queries over collections of physically-distributed streams. Thus, effective solutions have to be simultaneously space/time efficient (at each remote monitor site), communication efficient (across the underlying communication network), and provide continuous, guaranteed-quality approximate query answers. We discuss novel algorithmic solutions for the problem of continuously tracking a broad class of complex aggregate queries in such a distributed-streams setting. Our tracking schemes maintain approximate query answers with provable error guarantees, while simultaneously optimizing the storage space and processing time at each remote site, as well as the communication cost across the network. In a nutshell, our algorithms rely on tracking general-purpose randomized sketch summaries of local streams at remote sites along with concise prediction models of local site behavior in order to produce highly communication-and space/time-efficient solutions. The end result is a powerful approximate query tracking framework that readily incorporates several complex analysis queries (including distributed join and multi-join aggregates, and approximate wavelet representations), thus giving the first known low-overhead tracking solution

Biography:

Minos Garofalakis is a Senior Research Scientist with Intel Research Berkeley. He obtained his PhD from the University of Wisconsin-Madison in 1998, and joined Intel Research in July 2005, after spending 6.5 years as a Member of Technical Staff with Bell Labs in Murray Hill, NJ. His current research interests include data streaming, approximate query processing, and XML databases. In addition to serving on a number of program committees for conferences in the data-management area, Minos also currently serves as an associate editor for the IEEE Data Engineering Bulletin, and will be the Core Database Technology PC Chair for the upcoming VLDB'2007 Conference in Vienna, Austria.

Return to EECS Joint Colloquium