{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T20:36:17Z","timestamp":1765485377823,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007523","name":"Advanced Cyberinfrastructure","doi-asserted-by":"publisher","award":["ANI-9986397ANI-0093296ANI-0205294IIS-0133825IIS-0308213"],"award-info":[{"award-number":["ANI-9986397ANI-0093296ANI-0205294IIS-0133825IIS-0308213"]}],"id":[{"id":"10.13039\/100007523","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["ANI-9986397ANI-0093296ANI-0205294IIS-0133825IIS-0308213"],"award-info":[{"award-number":["ANI-9986397ANI-0093296ANI-0205294IIS-0133825IIS-0308213"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1508857.1508863","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T14:14:44Z","timestamp":1240323284000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Robust approximate aggregation in sensor data management systems"],"prefix":"10.1145","volume":"34","author":[{"given":"Jeffrey","family":"Considine","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marios","family":"Hadjieleftheriou","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs, Florham Park, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Byers","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Kollios","sequence":"additional","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,4,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.118"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"volume-title":"Proceedings of the International Workshop on Randomization and Approximation Techniques (RANDOM'02)","author":"Bar-Yossef Z.","key":"e_1_2_1_3_1","unstructured":"Bar-Yossef , Z. , Jayram , T. S. , Kumar , R. , Sivakumar , D. , and Trevisan , L . 2002. Counting distinct elements in a data stream . In Proceedings of the International Workshop on Randomization and Approximation Techniques (RANDOM'02) , 1--10. Bar-Yossef, Z., Jayram, T. S., Kumar, R., Sivakumar, D., and Trevisan, L. 2002. Counting distinct elements in a data stream. In Proceedings of the International Workshop on Randomization and Approximation Techniques (RANDOM'02), 1--10."},{"key":"e_1_2_1_4_1","unstructured":"Bawa M. Garcia-Molina H. Gionis A. and Motwani R. 2003. Estimating aggregates on a peer-to-peer network. Tech. rep. Stanford University.  Bawa M. Garcia-Molina H. Gionis A. and Motwani R. 2003. Estimating aggregates on a peer-to-peer network. Tech. rep. Stanford University."},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom'07)","author":"Chakrabarti D.","key":"e_1_2_1_5_1","unstructured":"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. 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."},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'04)","author":"Considine J.","key":"e_1_2_1_6_1","unstructured":"Considine , J. , Li , F. , Kollios , G. , and Byers , J . 2004. Approximate aggregation techniques for sensor databases . In Proceedings of the International Conference on Data Engineering (ICDE'04) , 449--461. Considine, J., Li, F., Kollios, G., and Byers, J. 2004. Approximate aggregation techniques for sensor databases. In Proceedings of the International Conference on Data Engineering (ICDE'04), 449--461."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198388"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065201"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007628"},{"volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT'04)","author":"Deligiannakis A.","key":"e_1_2_1_11_1","unstructured":"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. 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."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0016-z"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases (VLDB'04)","author":"Deshpande A.","key":"e_1_2_1_13_1","unstructured":"Deshpande , A. , Guestrin , C. , Madden , S. , Hellerstein , J. , and Hong , W . 2004. Model-Driven data acquisition in sensor networks . In Proceedings of the International Conference on Very Large Data Bases (VLDB'04) , 588--599. Deshpande, A., Guestrin, C., Madden, S., Hellerstein, J., and Hong, W. 2004. Model-Driven data acquisition in sensor networks. In Proceedings of the International Conference on Very Large Data Bases (VLDB'04), 588--599."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142483"},{"volume-title":"Non-Uniform Random Variate Generation","author":"Devroye L.","key":"e_1_2_1_15_1","unstructured":"Devroye , L. 1986. Non-Uniform Random Variate Generation . Springer . Devroye, L. 1986. Non-Uniform Random Variate Generation. Springer."},{"volume-title":"Proceedings of the European Symposium on Algorithms (ESA'03)","author":"Durand M.","key":"e_1_2_1_16_1","unstructured":"Durand , M. and Flajolet , P . 2003. Loglog counting of large cardinalities . In Proceedings of the European Symposium on Algorithms (ESA'03) , 605--617. Durand, M. and Flajolet, P. 2003. Loglog counting of large cardinalities. In Proceedings of the European Symposium on Algorithms (ESA'03), 605--617."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241657"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/360680.360691"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/509506.509514"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872790"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'07)","author":"Garofalakis M.","key":"e_1_2_1_22_1","unstructured":"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. 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."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055597"},{"key":"e_1_2_1_26_1","first-page":"40","article-title":"Mica, the commercialization of microsensor motes","volume":"19","author":"Horton M.","year":"2002","unstructured":"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 . 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.","journal-title":"IEEE Sensors J."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.808417"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322263.1322269"},{"volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS'03)","author":"Kempe D.","key":"e_1_2_1_29_1","unstructured":"Kempe , D. , Dobra , A. , and Gehrke , J . 2003. Gossip-Based computation of aggregate information . In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS'03) , 482. Kempe, D., Dobra, A., and Gehrke, J. 2003. Gossip-Based computation of aggregate information. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS'03), 482."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.134"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844142"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872817"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061322"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066191"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031525"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775059"},{"volume-title":"Random Variables, and Stochastic Processes","author":"Papoulis A.","key":"e_1_2_1_38_1","unstructured":"Papoulis , A. 1965. Probability , Random Variables, and Stochastic Processes . McGraw-Hill , New York . Papoulis, A. 1965. Probability, Random Variables, and Stochastic Processes. McGraw-Hill, New York."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958521"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0138-0"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'07)","author":"Stoev S.","key":"e_1_2_1_42_1","unstructured":"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. 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."},{"key":"e_1_2_1_43_1","unstructured":"U.S. Census Bureau. 2009.TIGER\/Line datasets. http:\/\/www.census.gov\/geo\/www\/tiger\/.  U.S. Census Bureau. 2009.TIGER\/Line datasets. http:\/\/www.census.gov\/geo\/www\/tiger\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355749"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601861"},{"volume-title":"Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR'03)","author":"Yao Y.","key":"e_1_2_1_46_1","unstructured":"Yao , Y. and Gehrke , J . 2003. Query processing in sensor networks . In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR'03) . Yao, Y. and Gehrke, J. 2003. Query processing in sensor networks. In Proceedings of the Biennial Conference on Innovative Data Systems Research (CIDR'03)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-005-6612-9"},{"volume-title":"Proceedings of the IEEE International Workshop on Sensor Network Protocols and Applications (SNPA'03)","author":"Zhao J.","key":"e_1_2_1_48_1","unstructured":"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. 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."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1508857.1508863","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1508857.1508863","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:42Z","timestamp":1750253382000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1508857.1508863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1508857.1508863"],"URL":"https:\/\/doi.org\/10.1145\/1508857.1508863","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}