Search

Browse

• Communities
• Authors
• Year
• Titles
• Subjects

My Space

• Login

Sketch-based querying of distributed sliding-window data streams

Papapetrou Odysseas, Garofalakis Minos, Deligiannakis Antonios

Full record

---

Summary

While traditional data-management systems focus on evaluating single, adhocqueries over static data sets in a centralized setting, several emergingapplications require (possibly, continuous) answers to queries on dynamicdata that is widely distributed and constantly updated. Furthermore,such query answers often need to discount data that is “stale”, and operatesolely on a sliding window of recent data arrivals (e.g., data updates occurringover the last 24 hours). Such distributed data streaming applicationsmandate novel algorithmic solutions that are both time- and space-efficient(to manage high-speed data streams), and also communication-efficient (todeal with physical data distribution). In this paper, we consider the problemof complex query answering over distributed, high-dimensional datastreams in the sliding-window model. We introduce a novel sketching technique(termed ECM-sketch) that allows effective summarization of streamingdata over both time-based and count-based sliding windows with probabilisticaccuracy guarantees. Our sketch structure enables point as wellas inner-product queries, and can be employed to address a broad rangeof problems, such as maintaining frequency statistics, finding heavy hitters,and computing quantiles in the sliding-window model. Focusing ondistributed environments, we demonstrate how ECM-sketches of individual,local streams can be composed to generate a (low-error) ECM-sketchsummary of the order-preserving aggregation of all streams; furthermore,we show how ECM-sketches can be exploited for continuous monitoringof sliding-window queries over distributed streams. Our extensive experimentalstudy with two real-life data sets validates our theoretical claims andverifies the effectiveness of our techniques. To the best of our knowledge,ours is the first work to address efficient, guaranteed-error complex queryanswering over distributed data streams in the sliding-window model.

Services