Article

Time-decaying sketches for sensor data aggregation

Authors:

Graham Cormode,

Srikanta Tirthapura,

Bojian XuAuthors Info & Claims

PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing

Pages 215 - 224

https://doi.org/10.1145/1281100.1281132

Published: 12 August 2007 Publication History

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. 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 [26,12], 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.

References

[1]

C. C. Aggarwal. On biased reservoir sampling in the presence of stream evolution. In VLDB, 2006.

Digital Library

[2]

I. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci. A survey on sensor networks. IEEE Commun. Mag. 40 (8) (2002) 102--114

Digital Library

[3]

N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137--147, 1999.

Digital Library

[4]

A. Arasu and G. Manku. Approximate counts and quantiles over sliding windows. In PODS, 2004.

Digital Library

[5]

B. Babcock, M. Datar, and R. Motwani. Sampling from a moving window over streaming data. In SODA, 2002.

Digital Library

[6]

B. Babcock, M. Datar, R. Motwani, and L. O'Callaghan. Maintaining variance and k-medians over data stream windows. In PODS, 2003.

Digital Library

[7]

A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher. Min-wise independent permutations. In STOC, 1998.

Digital Library

[8]

C. Busch and S. Tirthapura. A deterministic algorithm for summarizing asynchronous streams over a sliding window. In STACS, 2007.

Digital Library

[9]

J. L. Carter and M. L. Wegman. Universal classes of hash functions. J. of Comp. and System Sciences, 18(2):143--154, 1979.

[10]

Y. Chen, H. V. Leong, M. Xu, Jiannong Cao, K. C. C Chan and A. T. S Chan. In-network data processing for wireless sensor networks. In MDM (International Conference on Mobile Data Management) 2006

Digital Library

[11]

E. Cohen and M. Strauss. Maintaining time-decaying stream aggregates. In PODS, 2003.

Digital Library

[12]

J. Considine, F. Li, G. Kollios, and J. Byers. Approximate aggregation techniques for sensor databases. In ICDE, 2004.

Digital Library

[13]

G. Cormode and S. Muthukrishnan. Space efficient mining of multigraph streams. In PODS, 2005.

Digital Library

[14]

G. Cormode, S. Tirthapura, B. Xu. Time-Decaying Sketches for Sensor Data Aggregation. Technical Report TR-2007-06-0, Department of Electrical and Computer Engineering, Iowa State University.

[15]

M. Datar, A. Gionis, P. Indyk, and R. Motwani. Maintaining stream statistics over sliding windows. SIAM J. on Computing, 31(6):1794--1813, 2002.

Digital Library

[16]

P. Flajolet and G. N. Martin. Probabilistic counting. In FOCS, 1983.

Digital Library

[17]

P. Gibbons and S. Tirthapura. Estimating simple functions on the union of data streams. In SPAA, 2001.

Digital Library

[18]

P. Gibbons and S. Tirthapura. Distributed streams algorithms for sliding windows. In SPAA, 2002.

Digital Library

[19]

P. Indyk, D. Woodruff. Tight lower bounds for the distinct elements problem. In FOCS, 2003.

Digital Library

[20]

N. Kimura and S. Latifi. A survey on data compression in wireless sensor networks. In ITCC International Conference on Information Technology Coding and Computing, 2005

Digital Library

[21]

E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.

Digital Library

[22]

L. K. Lee and H. F. Ting. A simpler and more efficient deterministic scheme for finding frequent items over sliding windows. In PODS, 2006.

Digital Library

[23]

S. Madden, M. Franklin, J. Hellerstein, and W. Hong. Tag: a tiny aggregation service for ad-hoc sensor networks. SIGOPS Operating Systems Review, 36(SI):131--146, 2002.

Digital Library

[24]

J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315--323, 1980.

[25]

S. Muthukrishnan. Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science. Now Publishers, August 2005.

Digital Library

[26]

S. Nath, P. B. Gibbons, S. Seshan, and Z. Anderson. Synopsis diffusion for robust aggregation in sensor networks. In SENSYS, 2004.

Digital Library

[27]

A. Pavan and S. Tirthapura. Range-efficient computation of F₀ over massive data streams. In SIAM Journal on Computing, 37(2):359--379, 2007.

Digital Library

[28]

S. Tirthapura, B. Xu, and C. Busch. Sketching asynchronous streams over a sliding window. In PODC, 2006.

Digital Library

Cited By

Chaieb SMrad AHnich B(2023)Obsolete personal information update system: towards the prevention of falls in the elderlyApplied Intelligence10.1007/s10489-022-04289-353:14(18061-18084)Online publication date: 23-Jan-2023
https://doi.org/10.1007/s10489-022-04289-3
Chaieb SHnich BMrad A(2022)Data obsolescence detection in the light of newly acquired valid observationsApplied Intelligence10.1007/s10489-022-03212-052:14(16532-16554)Online publication date: 24-Mar-2022
https://doi.org/10.1007/s10489-022-03212-0
Yang JMunagala KSilberstein A(2018)Data Aggregation in Sensor NetworksEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_93(725-730)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_93
Show More Cited By

Index Terms

Time-decaying sketches for sensor data aggregation
1. Information systems
2. Networks
  1. Network services
    1. Network monitoring

Recommendations

Time-decaying Sketches for Robust Aggregation of Sensor Data

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, ...
Sketching asynchronous streams over a sliding window
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing

We study the problem of maintaining sketches of recent elements of a data stream. Motivated by applications involving network data, we consider streams that are asynchronous, in which the observed order of data is not the same as the time order in which ...
An Efficient Data Streams Mining Method for Wireless Sensor Network's Data Aggregation
ETCS '09: Proceedings of the 2009 First International Workshop on Education Technology and Computer Science - Volume 03

Wireless distributed sensor systems will enable the reliable monitoring of a variety of environments for both civil and military applications. The data model generated by sensor network is data streams. Because of the rapid data arriving speed and huge ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing

August 2007

424 pages

ISBN:9781595936165

DOI:10.1145/1281100

General Chair:
Indranil Gupta
UIUC, USA
,
Program Chair:
Rogert Wattenhofer
ETH Zurich, Switzerland

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 August 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC07

Sponsor:

PODC07: ACM Symposium on Principles of Distributed Computing 2007

August 12 - 15, 2007

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
434
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chaieb SMrad AHnich B(2023)Obsolete personal information update system: towards the prevention of falls in the elderlyApplied Intelligence10.1007/s10489-022-04289-353:14(18061-18084)Online publication date: 23-Jan-2023
https://doi.org/10.1007/s10489-022-04289-3
Chaieb SHnich BMrad A(2022)Data obsolescence detection in the light of newly acquired valid observationsApplied Intelligence10.1007/s10489-022-03212-052:14(16532-16554)Online publication date: 24-Mar-2022
https://doi.org/10.1007/s10489-022-03212-0
Yang JMunagala KSilberstein A(2018)Data Aggregation in Sensor NetworksEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_93(725-730)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_93
Cohen E(2018)Decay ModelsEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_126(1008-1012)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_126
Yang JMunagala KSilberstein A(2017)Data Aggregation in Sensor NetworksEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_93-2(1-6)Online publication date: 8-Aug-2017
https://doi.org/10.1007/978-1-4899-7993-3_93-2
Cohen E(2017)Decay ModelsEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_126-2(1-5)Online publication date: 2-Jan-2017
https://doi.org/10.1007/978-1-4899-7993-3_126-2
Keller FMüller EBöhm K(2015)Estimating mutual information on data streamsProceedings of the 27th International Conference on Scientific and Statistical Database Management10.1145/2791347.2791348(1-12)Online publication date: 29-Jun-2015
https://dl.acm.org/doi/10.1145/2791347.2791348
Tirthapura SWoodruff D(2015)A General Method for Estimating Correlated Aggregates Over a Data StreamAlgorithmica10.1007/s00453-014-9917-173:2(235-260)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s00453-014-9917-1
Theodoridis EChatzigiannakis IDulman S(2012)Post-processing in wireless sensor networksJournal of Network and Computer Applications10.1016/j.jnca.2010.12.02035:2(548-561)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1016/j.jnca.2010.12.020
Jin CGao MZhou A(2011)Handling ER-topk query on uncertain streamsProceedings of the 16th international conference on Database systems for advanced applications - Volume Part I10.5555/1997305.1997338(326-340)Online publication date: 22-Apr-2011
https://dl.acm.org/doi/10.5555/1997305.1997338
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents