skip to main content
10.1145/1055558.1055597acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

Power-conserving computation of order-statistics over sensor networks

Published: 14 June 2004 Publication History

Abstract

We study the problem of power-conserving computation of order statistics in sensor networks. Significant power-reducing optimizations have been devised for computing simple aggregate queries such as COUNT, AVERAGE, or MAX over sensor networks. In contrast, aggregate queries such as MEDIAN have seen little progress over the brute force approach of forwarding all data to a central server. Moreover, battery life of current sensors seems largely determined by communication costs --- therefore we aim to minimize the number of bytes transmitted. Unoptimized aggregate queries typically impose extremely high power consumption on a subset of sensors located near the server. Metrics such as total communication cost underestimate the penalty of such imbalance: network lifetime may be dominated by the worst-case replacement time for depleted batteries.In this paper, we design the first algorithms for computing order-statistics such that power consumption is balanced across the entire network. Our first main result is a distributed algorithm to compute an ε-approximate quantile summary of the sensor data such that each sensor transmits only O(log2 n/ε) data values, irrespective of the network topology, an improvement over the current worst-case behavior of Ω(n). Second, we show an improved result when the height, h, of the network is significantly smaller than n. Our third result is that we can exactly compute any order statistic (e.g., median) in a distributed manner such that each sensor needs to transmit O(log3 n) values.Further, we design the aggregates used by our algorithms to be decomposable. An aggregate Q over a set S is decomposable if there exists a function, f, such that for all S = S1S2, Q(S) = f(Q(S1), Q(S2)). We can thus directly apply existing optimizations to decomposable aggregates that increase error-resilience and reduce communication cost.Finally, we validate our results empirically, through simulation. When we compute the median exactly, we show that, even for moderate size networks, the worst communication cost for any single node is several times smaller than the corresponding cost in prior median algorithms. We show similar cost reductions when computing approximate order-statistic summaries with guaranteed precision. In all cases, our total communication cost over the entire network is smaller than or equal to the total cost of prior algorithms.

References

[1]
Daniel Barbara, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond Ng, Viswanath Poosala, Kenneth A. Ross, and Kenneth C. Sevcik. The New Jersey Data Reduction Report. Data Engineering Bulletin, 20(4):3--45, December 1997.]]
[2]
Phillipe Bonnet, Johannes Gehrke, and Praveen Seshadri. Towards sensor database systems. In Proceedings of Conference on Mobile Data Management, January 2001.]]
[3]
Graham Cormode and S. Muthukrishnan. An improved data stream summary: The count-min sketch and its applications. In to appear in Proceedings of Latin American Theoretical Informatics (LATIN 2004), April 2004. Buenos Aires, Argentina (also available as DIMACS Tech Report TR-2003-20).]]
[4]
Crossbow Technology, Inc. Wireless sensor networks: MICA, MICA2, and MICA2DOT. http://www.xbow.com/Products/Wireless_Sensor_Networks.htm.]]
[5]
Alin Dobra, Minos Garofalakis, Johannes Gehrke, and Rajeev Rastoghi. Processing complex aggregate queries over data stream. In Proceedings of the 2002 ACM SIGMOD Intl. Conference on Management of Data, pages 61--72, June 4--6 2002. Madison, WI.]]
[6]
Deepak Ganesan, Sylvia Ratnasamy, Hanbiao Wang, and Deborah Estrin. Coping with irregular spatio-temporal sampling in sensor networks. In Proceedings of Second Annual Workshop on Hot Topics in Networking (HOTNETS-II), November 20--21 2003. Cambridge, MA.]]
[7]
Minos Garofalakis and Phillip B. Gibbons. Wavelet synopses with error guarantees. In Proceedings of the 2002 ACM SIGMOD Intl. Conference on Management of Data, pages 476--487, June 4--6 2002. Madison, WI.]]
[8]
Jim Gray, Adam Bosworth, Andrew Layman, and Hamid Pirahesh. Data Cube: A relational operator generalizing group-by, cross-tabl and sub-totals. In Proceedings of the 12th International Conference on Data Engineering (ICDE '96), pages 152--159, 1996.]]
[9]
Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. In Proceedings of the 2001 ACM SIGMOD Intl. Conference on Management of Data, pages 58--66, May 2001.]]
[10]
Joseph M. Hellerstein, Wei Hong, Samuel Madden, and Kyle Stanek. Beyond average: Toward sophisticated sensing with queries. In Proceedings of 2nd International Workshop on Information Processing in Sensor Networks (IPSN '03), pages 63--79. (Lecture Notes in Computer Science 2634), Springer Verlag, April 2003. Palo Alto, CA.]]
[11]
Chalermek Intanagonwiwat, Ramesh Govndan, and Deborah Estrin. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th annual ACM/IEEE Conference on Mobile Computing and Networking (MobiCOM '00), pages 56--67, August 2000. Boston, MA.]]
[12]
Samuel Madden and Michael J. Franklin. Fjording the stream: An architechture for queries over streaming sensor data. In Proceedings of the ICDE, 2002. San Jose, CA.]]
[13]
Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. TAG: a Tiny AGgregation service for ad-hoc sensor networks. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI '02), pages 131--146, December 9--11 2002. Boston, MA.]]
[14]
Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. The design of an acquisitional query processor for sensor networks. In Proceedings of the 2003 ACM SIGMOD International Conference on the Management of Data, pages 491--502, June 9--12 2003. San Diego, CA.]]
[15]
Samuel Madden, Robert Szewezyk, Michael J. Franklin, and David Culler. Supporting aggregate queries over ad-hoc wireless sensor networks. In In Proceedings of Workshop on Mobile Computing and Systems Applications, 2002.]]
[16]
Stephane Mallat. A Wavelet tour of signal processing. Academic Press, 2nd edition, 1999. London, UK.]]
[17]
Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. Approximate medians and other quantiles in one pass and with limited memory. SIGMOD Record (ACM Special Interest Group on Management of Data), 27(2):426--435, June 1998. Seattle, WA.]]
[18]
Rajeev Motwani, Jennifer Widom, Arvind Arasu, Brian Babcock, Shivnath Babu, Mayur Datar, Gurmeet Singh Manku, Chris Olston, Justin Rosenstein, and Rohit Varma. Query processing, approximation, and resource management in a data stream management system. In CIDR, 2003.]]
[19]
J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12:315--323, 1980.]]
[20]
G. Pottie and W. Kaiser. Wireless integrated network sensors. Communications of the ACM, 43(5):51--58, May 2000.]]
[21]
Yong Yao and Johannes Gehrke. Query processing for sensor networks. In CIDR, 2003.]]
[22]
Jerry Zhao, Ramesh Govindan, and Deborah Estrin. Computing aggregates for monitoring wireless sensor networks. In Proceedings of the 1st IEEE International Workshop on Sensor Net Protocols and Applications (SNPA 2003), May 11 2003. Anchorage, AK.]]

Cited By

View all
  • (2023)Together is Better: Heavy Hitters Quantile EstimationProceedings of the ACM on Management of Data10.1145/35889371:1(1-25)Online publication date: 30-May-2023
  • (2023)Niffler: Real-time Device-level Anomalies Detection in Smart HomeACM Transactions on the Web10.1145/358607317:3(1-27)Online publication date: 22-May-2023
  • (2023)Online Feature Screening for Data Streams With Concept DriftIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323275235:11(11693-11707)Online publication date: 1-Nov-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
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: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)11
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Together is Better: Heavy Hitters Quantile EstimationProceedings of the ACM on Management of Data10.1145/35889371:1(1-25)Online publication date: 30-May-2023
  • (2023)Niffler: Real-time Device-level Anomalies Detection in Smart HomeACM Transactions on the Web10.1145/358607317:3(1-27)Online publication date: 22-May-2023
  • (2023)Online Feature Screening for Data Streams With Concept DriftIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323275235:11(11693-11707)Online publication date: 1-Nov-2023
  • (2023)Efficient and Secure Quantile Aggregation of Private Data StreamsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.327277518(3058-3073)Online publication date: 1-Jan-2023
  • (2023)On distributed data aggregation and the precision of approximate histogramsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.104722180:COnline publication date: 1-Oct-2023
  • (2023)Variable Selection for Distributed Sparse Regression Under Memory ConstraintsCommunications in Mathematics and Statistics10.1007/s40304-022-00291-w12:2(307-338)Online publication date: 1-Feb-2023
  • (2023)Global debiased DC estimations for biased estimators via pro forma regressionTEST10.1007/s11749-023-00850-532:2(726-758)Online publication date: 1-Mar-2023
  • (2022)Streaming Quantiles Algorithms with Small Space and Update TimeSensors10.3390/s2224961222:24(9612)Online publication date: 8-Dec-2022
  • (2022)Efficient and error-bounded spatiotemporal quantile monitoring in edge computing environmentsProceedings of the VLDB Endowment10.14778/3538598.353860015:9(1753-1765)Online publication date: 1-May-2022
  • (2022)Controlled Intentional Degradation in Analytical Video SystemsProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517899(2105-2119)Online publication date: 10-Jun-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media