Skip to main content
Article
Time-decaying Sketches for Robust Aggregation of Sensor Data
SIAM Journal on Computing
  • Graham Cormode, AT&T Labs–Research
  • Srikanta Tirthapura, Iowa State University
  • Bojian Xu, Iowa State University
Document Type
Article
Publication Date
1-1-2009
DOI
10.1137/08071795X
Abstract

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., reinsertions of the same data will not affect the sketch and hence the estimates of aggregates. Unlike previous duplicate-insensitive sketches for sensor data aggregation [S. Nath et al., Synposis diffusion for robust aggregation in sensor networks, in Proceedings of the 2nd International Conference on Embedded Network Sensor Systems, (2004), pp. 250–262], [J. Considine et al., Approximate aggregation techniques for sensor databases, in Proceedings of the 20th International Conference on Data Engineering (ICDE), 2004, pp. 449–460], 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 loss of accuracy. To our knowledge, this is the first sketch that combines all the above properties.

Comments

This article is from SIAM Journal on Computing 39 (2009): 1309, doi: 10.1137/08071795X. Posted with permission.

Copyright Owner
Society for Industrial and Applied Mathematics
Language
en
File Format
application/pdf
Citation Information
Graham Cormode, Srikanta Tirthapura and Bojian Xu. "Time-decaying Sketches for Robust Aggregation of Sensor Data" SIAM Journal on Computing Vol. 39 Iss. 4 (2009) p. 1309 - 1339
Available at: http://works.bepress.com/srikanta-tirthapura/6/