Institutional Repository
Technical University of Crete
EN  |  EL



My Space

Sketching streams through the net: distributed approximate query tracking

Cormode, Graham, 1977-, Garofalakis Minos

Full record

Year 2005
Type of Item Conference Full Paper
Bibliographic Citation G. Cormode and M. Garofalakis, "Sketching streams through the net: distributed approximate query tracking", in 31st International Conference on Very Large Data Bases, August 2005, pp. 13-24.
Appears in Collections


Emerging large-scale monitoring applications requirecontinuous tracking of complex dataanalysisqueries over collections of physicallydistributedstreams. Effective solutions have tobe simultaneously space/time efficient (at eachremote monitor site), communication efficient(across the underlying communication network),and provide continuous, guaranteed-quality approximatequery answers. In this paper, we proposenovel algorithmic solutions for the problemof continuously tracking a broad class of complexaggregate queries in such a distributed-streamssetting. Our tracking schemes maintain approximatequery answers with provable error guarantees,while simultaneously optimizing the storagespace and processing time at each remotesite, and the communication cost across the network.They rely on tracking general-purpose randomizedsketch summaries of local streams at remotesites along with concise prediction modelsof local site behavior in order to producehighly communication- and space/time-efficientsolutions. The result is a powerful approximatequery tracking framework that readily incorporatesseveral complex analysis queries (includingdistributed join and multi-join aggregates, and approximatewavelet representations), thus givingthe first known low-overhead tracking solution forsuch queries in the distributed-streams model.