Robust approximate aggregation in sensor data management systems

ABSTRACT

In the emerging area of sensor-based systems, a significant challenge is to develop scalable, fault-tolerant methods to extract useful information from the data the sensors collect. An approach to this data management problem is the use of sensor database systems, which allow users to perform aggregation queries such as MIN, COUNT, and AVG on the readings of a sensor network. In addition, more advanced queries such as frequency counting and quantile estimation can be supported. Due to energy limitations in sensor-based networks, centralized data collection is generally impractical, so most systems use in-network aggregation to reduce network traffic. However, even these aggregation strategies remain bandwidth-intensive when combined with the fault-tolerant, multipath routing methods often used in these environments. To avoid this expense, we investigate the use of approximate in-network aggregation using small sketches. We present duplicate-insensitive sketching techniques that can be implemented efficiently on small sensor devices with limited hardware support and we analyze both their performance and accuracy. Finally, we present an experimental evaluation that validates the effectiveness of our methods.

REFERENCES

• 1: A. Pavan , Srikanta Tirthapura, Range-Efficient Computation of F" over Massive Data Streams, Proceedings of the 21st International Conference on Data Engineering, p.32-43, April 05-08, 2005 [doi>10.1109/ICDE.2005.118]
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 3: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, Counting Distinct Elements in a Data Stream, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.1-10, September 13-15, 2002
• 4: Bawa, M., Garcia-Molina, H., Gionis, A., and Motwani, R. 2003. Estimating aggregates on a peer-to-peer network. Tech. rep., Stanford University.
• 5: Chakrabarti, D., Leskovec, J., Faloutsos, C., Madden, S., Guestrin, C., and Faloutsos, M. 2007. Information survival threshold in sensor and p2p networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom'07), 1316--1324.
• 6: Jeffrey Considine , Feifei Li , George Kollios , John Byers, Approximate Aggregation Techniques for Sensor Databases, Proceedings of the 20th International Conference on Data Engineering, p.449, March 30-April 02, 2004
• 7: Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing Data Streams Using Hamming Norms (How to Zero In), IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.529-540, March 2003 [doi>10.1109/TKDE.2003.1198388]
• 8: Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005 [doi>10.1016/j.jalgor.2003.12.001]
• 9: Graham Cormode , S. Muthukrishnan, Space efficient mining of multigraph streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065201]
• 10: Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Compressing historical information in sensor networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007628]
• 11: Deligiannakis, A., Kotidis, Y., and Roussopoulos, N. 2004b. Hierarchical in-network data aggregation with quality guarantees. In Proceedings of the International Conference on Extending Database Technology (EDBT'04), 658--675.
• 12: Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Bandwidth-constrained queries in sensor networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.3, p.443-467, May 2008 [doi>10.1007/s00778-006-0016-z]
• 13: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 14: Amol Deshpande , Samuel Madden, MauveDB: supporting model-based user views in database systems, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142483]
• 15: Devroye, L. 1986. Non-Uniform Random Variate Generation. Springer.
• 16: Durand, M. and Flajolet, P. 2003. Loglog counting of large cardinalities. In Proceedings of the European Symposium on Algorithms (ESA'03), 605--617.
• 17: P. Flajolet, On adaptive sampling, Computing, v.43 n.4, p.391-400, February 1990 [doi>10.1007/BF02241657]
• 18: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 19: Robert W. Floyd , Ronald L. Rivest, Expected time bounds for selection, Communications of the ACM, v.18 n.3, p.165-172, March 1975 [doi>10.1145/360680.360691]
• 20: Deepak Ganesan , Ramesh Govindan , Scott Shenker , Deborah Estrin, Highly-resilient, energy-efficient multipath routing in wireless sensor networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.4, October 2001 [doi>10.1145/509506.509514]
• 21: Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Processing set expressions over continuous update streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872790]
• 22: Garofalakis, M., Hellerstein, J. M., and Maniatis, P. 2007. Proof sketches: Verifiable in- network aggregation. In Proceedings of the International Conference on Data Engineering (ICDE'07), 996--1005.
• 23: Phillip B. Gibbons , Srikanta Tirthapura, Estimating simple functions on the union of data streams, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.281-291, July 2001, Crete Island, Greece [doi>10.1145/378580.378687]
• 24: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 25: Michael B. Greenwald , Sanjeev Khanna, Power-conserving computation of order-statistics over sensor networks, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055597]
• 26: Horton, M., Culler, D., Pister, K., Hill, J., Szewczyk, R., and Woo, A. 2002. Mica, the commercialization of microsensor motes. IEEE Sensors J. 19, 4, 40--48.
• 27: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin , John Heidemann , Fabio Silva, Directed diffusion for wireless sensor networking, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.2-16, February 2003 [doi>10.1109/TNET.2002.808417]
• 28: Abhinav Kamra , Vishal Misra , Dan Rubenstein, CountTorrent: ubiquitous access to query aggregates in dynamic and mobile sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322269]
• 29: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 30: Yannis Kotidis, Snapshot Queries: Towards Data-Centric Sensor Networks, Proceedings of the 21st International Conference on Data Engineering, p.131-142, April 05-08, 2005 [doi>10.1109/ICDE.2005.134]
• 31: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 32: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 33: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 34: Amit Manjhi , Suman Nath , Phillip B. Gibbons, Tributaries and deltas: efficient and robust aggregation in sensor network streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066191]
• 35: Munro, J. I. and Paterson, M. 1980. Selection and sorting with limited storage. Theor. Comput. Sci. 12, 315--323.
• 36: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 37: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 38: Papoulis, A. 1965. Probability, Random Variables, and Stochastic Processes. McGraw-Hill, New York.
• 39: Bartosz Przydatek , Dawn Song , Adrian Perrig, SIA: secure information aggregation in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958521]
• 40: A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , K. Chrysanthis, Balancing energy efficiency and quality of aggregate data in sensor networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.384-403, December 2004 [doi>10.1007/s00778-004-0138-0]
• 41: Nisheeth Shrivastava , Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, Medians and beyond: new aggregation techniques for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031524]
• 42: Stoev, S., Hadjieleftheriou, M., Kollios, G., and Taqqu, M. S. 2007. Norm, point, and distance estimation over multiple signals using max-stable distributions. In Proceedings of the International Conference on Data Engineering (ICDE'07), 1006--1015.
• 43: U.S. Census Bureau. 2009.TIGER/Line datasets. http://www.census.gov/geo/www/tiger/.
• 44: Alastair J. Walker, An Efficient Method for Generating Discrete Random Variables with General Distributions, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.253-256, Sept. 1977 [doi>10.1145/355744.355749]
• 45: Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601861]
• 46: Yao, Y. and Gehrke, J. 2003. Query processing in sensor networks. In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR'03).
• 47: Fan Ye , Gary Zhong , Songwu Lu , Lixia Zhang, GRAdient broadcast: a robust data delivery protocol for large scale sensor networks, Wireless Networks, v.11 n.3, p.285-298, May 2005 [doi>10.1007/s11276-005-6612-9]
• 48: Zhao, J., Govindan, R., and Estrin, D. 2003. Computing aggregates for monitoring wireless sensor networks. In Proceedings of the IEEE International Workshop on Sensor Network Protocols and Applications (SNPA'03),139--148.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
Sensor databases, aggregation, approximation algorithms, sketches, synopses