Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Sketching streams through the net: distributed approximate query tracking

Cormode, Graham, 1977-, Garofalakis Minos

Full record

---

Summary

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.

Services