ISU Electrical and Computer Engineering Archives

Time-Decaying Sketches for Sensor Data Aggregation

Cormode, Graham and Srikanta, Tirthapura and Bojian, Xu (2007) Time-Decaying Sketches for Sensor Data Aggregation. Publisher UNSPECIFIED, Ames, Iowa, U.S.A..

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.
PDF - Requires Adobe Acrobat Reader or other PDF viewer.


We present a new sketch for summarizing network data. The sketch has the following properties which make it useful in communication-efficient aggregation in distributed streaming scenarios, such as sensor networks: the sketch is duplicate-insensitive, i.e. re-insertions of the same data will not affect the sketch, and hence the estimates of aggregates. Unlike previous duplicate-insensitive sketches for sensor data aggregation, it is also time-decaying, so that the weight of a data item in the sketch can decrease with time according to a user-specified decay function. The sketch can give provably approximate guarantees for various aggregates of data, including the sum, median, quantiles, and frequent elements. The size of the sketch and the time taken to update it are both polylogarithmic in the size of the relevant data. Further, multiple sketches computed over distributed data can be combined without losing the accuracy guarantees. To our knowledge, this is the first sketch that combines all the above properties.

EPrint Type:Technical Report
Subjects:Computer Engineering > SOFTWARE SYSTEMS > Parallel and Distributed Computing
Computer Engineering > INFORMATION SYSTEMS SECURITY & NETWORKING > Computer Networking and Security
ID Code:353
Identification Number:TR-2007-06-0
Deposited By:Bojian Xu
Deposited On:10 June 2007

Archive Staff Only: edit this record