{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,14]],"date-time":"2026-06-14T07:27:00Z","timestamp":1781422020334,"version":"3.54.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0626954CCF-0514738"],"award-info":[{"award-number":["CNS-0626954CCF-0514738"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CNS-0626954CCF-0514738"],"award-info":[{"award-number":["CNS-0626954CCF-0514738"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>\n            We propose a scalably efficient scheme for detecting large-scale physically correlated events in sensor networks. Specifically, we show that in a network of\n            <jats:italic>n<\/jats:italic>\n            sensors arbitrarily distributed in the plane, a sample of\n            <jats:italic>O<\/jats:italic>\n            (1\/\u03f5 log 1\/\u03f5) sensor nodes (\n            <jats:italic>mice<\/jats:italic>\n            ) is sufficient to catch any, and\n            <jats:italic>only those<\/jats:italic>\n            , events that affect \u03a9 (\u03f5\n            <jats:italic>n<\/jats:italic>\n            ) nodes (\n            <jats:italic>elephants<\/jats:italic>\n            ), for any 0 &lt; \u03f5 &lt; 1, as long as the\n            <jats:italic>geometry<\/jats:italic>\n            of the event has a bounded Vapnik-Chervonenkis (VC) dimension. In fact, the scheme is provably able to estimate the size of an event within the approximation error of \u00b1\u03f5\n            <jats:italic>n<\/jats:italic>\n            \/4, which can be improved further at the expense of more mice. The detection algorithm itself requires knowledge of the event geometry (e.g., circle, ellipse, or rectangle) for the sake of computational efficiency, but the combinatorial bound on the sample size (set of mice) depends only on the VC, dimension of the event class and not the precise shape geometry.\n          <\/jats:p>\n          <jats:p>\n            While nearly optimal in theory, due to implicit constant factors, these \u201cscale-free\u201d bounds still prove too large in practice if applied blindly. We therefore propose heuristic improvements and perform empirical parameter tuning to counter the pessimism inherent in these theoretical estimates. Using a variety of data distributions and event geometries, we show through simulations that the final scheme is eminently scalable and practical, say, for\n            <jats:italic>n<\/jats:italic>\n            \u2265 1000. The overall simplicity and generality of our technique suggests that it is well suited for a wide class of sensornet applications, including monitoring of physical environments, network anomalies, network security, or any abstract binary event that affects a significant number of nodes in the network.\n          <\/jats:p>","DOI":"10.1145\/1653760.1653761","type":"journal-article","created":{"date-parts":[[2010,1,5]],"date-time":"2010-01-05T15:05:08Z","timestamp":1262703908000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Catching elephants with mice"],"prefix":"10.1145","volume":"6","author":[{"given":"Sorabh","family":"Gandhi","sequence":"first","affiliation":[{"name":"University of California Santa Barbara, Santa Barbara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara, Santa Barbara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emo","family":"Welzl","sequence":"additional","affiliation":[{"name":"ETH Zurich, Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Agarwal P. K. and Matou\u0161ek J. 1992. On range searching with semialgebraic sets. In Mathematical Foundations of Computer Science. 1--13.   Agarwal P. K. and Matou\u0161ek J. 1992. On range searching with semialgebraic sets. In Mathematical Foundations of Computer Science. 1--13.","DOI":"10.1007\/3-540-55808-X_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2004.06.007"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Boyd S. and Vandenrberghe L. 2004. Convex Optimization. Cambridge University Press.   Boyd S. and Vandenrberghe L. 2004. Convex Optimization. Cambridge University Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11776178_22"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms. 281--290","author":"Chazelle B."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications. 59--70","author":"Chintalapudi K."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation.","author":"Dhariwal A.","year":"2006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080810.1080819"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236360.1236411"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/647909.740295"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187876"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the Conference on Information Processing In Sensor Networks (IPSN). 63--79","author":"Hellerstein J."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796551"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms. 76--85","author":"Kleinberg J."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109668"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Conference on Communications. 3202--3206","author":"Liao P."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570751"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek J. 2002. Lectures in Discrete Geometry (Graduate Texts In Mathematics). Springer.  Matou\u0161ek J. 2002. Lectures in Discrete Geometry (Graduate Texts In Mathematics). Springer.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185401"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Computer Communications and Networks.","author":"Mayer K."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Information Processing In Sensor Networks (IPSN). 80--95","author":"Nowak R."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Information Processing in Sensor Networks. 210--217","author":"Shrivastava N."},{"key":"e_1_2_1_24_1","unstructured":"Singh M. Bakshi A. and Prasanna V. 2004. Constructing topographic maps in networked sensor systems. In Algorithms for Wireless and Mobile Networks.  Singh M. Bakshi A. and Prasanna V. 2004. Constructing topographic maps in networked sensor systems. In Algorithms for Wireless and Mobile Networks."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/MOBIQUITOUS.2005.26"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1098918.1098925"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1161089.1161104"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Welzl E. 1991. Smallest enclosing disks (balls and ellipsoids). New Results and New Trends in Computer Science. Lecture Notes in Computer Science 359--370.  Welzl E. 1991. Smallest enclosing disks (balls and ellipsoids). New Results and New Trends in Computer Science. Lecture Notes in Computer Science 359--370.","DOI":"10.1007\/BFb0038202"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/EWSN.2005.1462003"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2002.1039518"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142491"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22163"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE Wireless Communications and Networking Conference.","author":"Zhao Y."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1653760.1653761","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1653760.1653761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:37Z","timestamp":1750249417000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1653760.1653761"}},"subtitle":["Sparse sampling for monitoring sensor networks"],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1653760.1653761"],"URL":"https:\/\/doi.org\/10.1145\/1653760.1653761","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"value":"1550-4859","type":"print"},{"value":"1550-4867","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2008-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-01-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}