More Web Proxy on the site http://driver.im/

article

Distributed deviation detection in sensor networks

Authors:

Themistoklis Palpanas,

Dimitris Papadopoulos,

Vana Kalogeraki,

Dimitrios GunopulosAuthors Info & Claims

ACM SIGMOD Record, Volume 32, Issue 4

Pages 77 - 82

https://doi.org/10.1145/959060.959074

Published: 01 December 2003 Publication History

Abstract

Sensor networks have recently attracted much attention, because of their potential applications in a number of different settings. The sensors can be deployed in large numbers in wide geographical areas, and can be used to monitor physical phenomena, or to detect certain events.An interesting problem which has not been adequately addressed so far is that of distributed online deviation detection in streaming data. The identification of deviating values provides an efficient way to focus on the interesting events in the sensor network.In this work, we propose a technique for online deviation detection in streaming data. We discuss how these techniques can operate efficiently in the distributed environment of a sensor network, and discuss the tradeoffs that arise in this setting. Our techniques process as much of the data as possible in a decentralized fashion, so as to avoid unnecessary communication and computational effort.

References

[1]

{AAR96} Andreas Arning, Rakesh Agrawal, and Prabhakar Raghavan. A Linear Method for Deviation Detection in Large Databases. In International Conference on Knowledge Discovery and Data Mining, pages 164--169, Portland, OR, USA, August 1996.

[2]

{BDM02} Brain Babcock, Mayur Datar, and Rajeev Motwani. Sampling From a Moving Window Over Streaming Data. In ACM-SIAM Symposium on Discrete Algorithms, pages 633--634, San Francisco, CA, USA, January 2002.

Digital Library

[3]

{BDMOO3} Brain Babcock, Mayur Datar, Rajeeve Motwani, and Liadan O'Callaghan. Maintaining Variance And K-medians Over Data Stream Windows. In ACM PODS International Conference, pages 234--243, San Diego, CA, USA, June 2003.

Digital Library

[4]

{BKNS00} Markus M. Breuing, Hans-Peter Kriegel, Raymond T. Ng, and Jörg Sander. LOF: Identifying Density-Based Local Outliers. In ACM SIGMOD International Conference, pages 21--32, Dallas, TX, USA, May 2000.

Digital Library

[5]

{BL94} V. Barnet and T. Lewis. Outliers in Statistical Data. John Wiley and Sons, Inc., 1994.

[6]

{BSV03} Ahmet Bulut, Ambuj K. Singh, and Roman Vitenberg. An Adaptive and Scalable Middleware for Distributed Indexing of Data Streams. In International Workshop on Databases, Information Systems and Peer-to-Peer Computing, Berlin, Germany, September 2003.

[7]

{CDIM02} Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan. Comparing Data Streams Using Hamming Norms (How to Zero In). In VLDB International Conference, Hong Kong, China, August 2002.

Digital Library

[8]

{Cre93} N. A. C. Cressie. Statistics for Spatial Data. Wiley & Sons, 1993.

[9]

{DM02} Mayur Datar and S. Muthukrishnan. Estimating Rarity and Similarity over Data Stream Windows. In Annual European Symposium (ESA), pages 323--334, Rome, Italy, September 2002.

Digital Library

[10]

{GGK03} Sudipto Guha, Dimitrios Gunopulos, and Nick Koudas. Correlating Synchronous and Asynchronous Data Streams. In International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 2003.

Digital Library

[11]

{GKMS01} Ann. C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin Strauss. Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. In VLDB International Conference, page 79--88, Rome, Italy, sep 2001.

Digital Library

[12]

{GKS01} Johannes Gehrke, Flip Korm, and Divesh Srivastava. On Computing Correlated Aggregates Over Continual Data Streams. In ACM SIGMOD International Conference, page, 13--24, Santa Barbara, CA, USA, may 2001.

Digital Library

[13]

{GKTD00} Dimitrios Gunopulos, George Kollios, Vassilis J. Tsotras, and Carlotta Domeniconi. Approximating Multi-Dimensional Aggregate Range Queries over Real Attributes. In ACM SIGMOD International Conference, pages 463--474, Dallas, TX, USA, May 2000.

Digital Library

[14]

{HHMS03} Joseph M. Hellerstein, Wei Hong, Samuel Madden, and Kyle Stanek. Beyond Average: Toward Sophisticated Sensing with Queries. In International Workshop on Information Processing in Sensor Networks, Palo Alto, CA, USA, April 2003.

[15]

{HSD01} Geoff Hulten, Laurie Spencer, and Pedro Domingos. Mining Time-Changing Data Streams. In International Conference of Knowledge Discovery and Data Mining, pages 71--80, San Fransisco, CA, USA, aug 2001.

Digital Library

[16]

{IEGH02} Chalermek Intanagonwiwat, Deborah Estrin, Ramesh Govindan, and John Heidemann. Impact of network density on data aggregation in wireless sensor networks. In Proceedings of ICDCS, 2002.

Digital Library

[17]

{IGE00} Chalermek Intangonwiwat, Ramesh Govindan, and Deborah Estrin. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of ACM MOBICOM, 2000.

Digital Library

[18]

{KGKB03} George Kollios, Dimitrios Gunopulos, Nick Koudas, and Stefan Berchtold. Efficient Biased Sampling for Approximate Clustering and Outlier Detection in Large Datasets. 15(5):1170--1187, 2003.

Digital Library

[19]

{KN98} Edwin M. Knorr and Raymond T. Ng. Algorithms for Mining Distance-Based Outliers in Large Datasets. In VLDB International Conference, pages 392--403, New York, NY, USA, August 1998.

Digital Library

[20]

{LBA+02} C. Lu, B. Blum, T. Abdelzher, J. Stankovic, and T. He. Rap: A real-time communication architecture for large-scale wireless sensor networks. In Proceedings of the Real-Time Technology and Applications Symposium, San Jose, CA, September 2002.

Digital Library

[21]

{MF02} Samuel Madden and Michael J. Franklin. Fjording the Stream: An Architecture for Queries Over Streaming Sensor Data. In International Conference on Data Engineering, San Jose, CA, USA, February 2002.

Digital Library

[22]

{MFH02} Samuel Madden and Michael J. Franklin, and Joseph M. Hellerstein. TAG: A Tiny AGgregation Service for Ad-Hoc Sensor Networks. In Symposium on Operating Systems Design and Implementation, Boston, MA, USA, December 2002.

Digital Library

[23]

{OC02} C. Okino and M. Corr. Statistically accurate sensor networking. IEEE WCNC, 2002.

[24]

{PK01} Themistoklis Palpanas and Nick Koudas. Entropy Based Approximate Querying and Exploration of Datacubes. In International Conference on Scientific and Statistical Database Management, pages 81--90, Fairfax, VA, USA, July 2001.

Digital Library

[25]

{PVK+04} Themistoklis Palpanas, Michail Vlachos, Eamonn Keogh, Dimitrios Gunopulos, and Wagner Truppel. Online Amnesic Approximation of Streaming Time Series. In International Conference on Data Engineering, Boston, MA, USA, March 2004.

Digital Library

[26]

{RRS00} Sridhar Ramaswamy, Rajeev Rastogi, and Kyuseok Shim. Efficient Algorithms for Mining Ouliers from Large Data Sets. In ACM SIGMOD International Conference, pages 427--438, Dallas, TX, USA, May 2000.

Digital Library

[27]

{SAA03} Y. Sankarasubramaniam, O. B. Akan, and I. F. Akyildiz. Esrt: Event to sink reliable transport protocol in wireless sensor networks. ACM MOBIHOC, 2003.

Digital Library

[28]

{SAM98} Sunita Sarawagi, Rakesh Agrawal, and Nimrod Megiddo. Discovery-driven Exploration of OLAP Data Cubes. In International Conference on Extending Database Technology, pages 168--182, Valencia, Spain, March 1998.

Digital Library

[29]

{Sco92} D. Scott. Multivariate Density Estimation: Theory, Practice and Visualization. Wiley & Sons, 1992.

[30]

{SS02} A. Savvides and M. B. Srivastava. A distributed computation platform for wireless embedded sensing. In Proceedings of ICCD 2002, Freiburg, Germany, September 2002.

Digital Library

[31]

{WLLP01} B. Warneke, M. Last, B. Liebowitz, and K. Pister. Smart dust: Communicating with a cubic-millimeter computer. IEEE Computer Magazine, pages 44--51, January 2001.

[32]

{YG03} Yong Yao and Johannes Gehrke. Query Processing for Sensor Networks. In Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 2003.

Cited By

Zhang WWang XShen SZhao YHao SJiang JZhang D(2024)Analyzing the distribution patterns and dynamic niche of Magnolia grandiflora L. in the United States and China in response to climate changeFrontiers in Plant Science10.3389/fpls.2024.144061015Online publication date: 22-Oct-2024
https://doi.org/10.3389/fpls.2024.1440610
Ducharlet KTravé-Massuyès LLasserre JLe Lann MMiloudi Y(2024)Leveraging the Christoffel function for outlier detection in data streamsInternational Journal of Data Science and Analytics10.1007/s41060-024-00581-2Online publication date: 13-Jun-2024
https://doi.org/10.1007/s41060-024-00581-2
Du HWang YXu XLiu M(2023)Niffler: Real-time Device-level Anomalies Detection in Smart HomeACM Transactions on the Web10.1145/358607317:3(1-27)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1145/3586073
Show More Cited By

Recommendations

Distributed Detection in Wireless Sensor Networks
ICIS '08: Proceedings of the Seventh IEEE/ACIS International Conference on Computer and Information Science (icis 2008)

Wireless sensor networks (WSNs) usually are applied in military systems, surveillance systems, etc. Since WSNs always are deployed in open environments, the security mechanisms in WSNs are very important. Although there are many security mechanisms in ...
A system for distributed event detection in wireless sensor networks
IPSN '10: Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks

Event detection is a major issue for applications of wireless sensor networks. In order to detect an event, a sensor network has to identify which application-specific incident has occurred based on the raw data gathered by individual sensor nodes. In ...
Distributed faulty sensor node detection in wireless sensor networks based on copula theory
ICC '17: Proceedings of the Second International Conference on Internet of things, Data and Cloud Computing

Wireless Sensor Networks (WSNs) are arising from the proliferation of Micro-Electro-Mechanical Systems (MEMS) technology as an important new area in wireless technology. They are composed of tiny devices which monitor physical or environmental ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 32, Issue 4

December 2003

112 pages

ISSN:0163-5808

DOI:10.1145/959060

Issue’s Table of Contents

Copyright © 2003 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2003

Published in SIGMOD Volume 32, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

140
Total Citations
View Citations
1,252
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang WWang XShen SZhao YHao SJiang JZhang D(2024)Analyzing the distribution patterns and dynamic niche of Magnolia grandiflora L. in the United States and China in response to climate changeFrontiers in Plant Science10.3389/fpls.2024.144061015Online publication date: 22-Oct-2024
https://doi.org/10.3389/fpls.2024.1440610
Ducharlet KTravé-Massuyès LLasserre JLe Lann MMiloudi Y(2024)Leveraging the Christoffel function for outlier detection in data streamsInternational Journal of Data Science and Analytics10.1007/s41060-024-00581-2Online publication date: 13-Jun-2024
https://doi.org/10.1007/s41060-024-00581-2
Du HWang YXu XLiu M(2023)Niffler: Real-time Device-level Anomalies Detection in Smart HomeACM Transactions on the Web10.1145/358607317:3(1-27)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1145/3586073
Yaqoob TMaqsood A(2023)Do methods of estimation matter in detecting outliers and forecasting macroeconomic variables?Journal of Chinese Economic and Business Studies10.1080/14765284.2023.227801222:2(231-252)Online publication date: 15-Nov-2023
https://doi.org/10.1080/14765284.2023.2278012
Samara MBennis IAbouaissa ALorenz P(2022)A Survey of Outlier Detection Techniques in IoT: Review and ClassificationJournal of Sensor and Actuator Networks10.3390/jsan1101000411:1(4)Online publication date: 4-Jan-2022
https://doi.org/10.3390/jsan11010004
Zhang SUrsekar VAkoglu LZhang ARangwala H(2022)Sparx: Distributed Outlier Detection at ScaleProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539076(4530-4540)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539076
Chander BKumaravelan G(2022)Outlier detection strategies for WSNs: A surveyJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2021.02.01234:8(5684-5707)Online publication date: Sep-2022
https://doi.org/10.1016/j.jksuci.2021.02.012
Run-Yang MFeng-Guo XFeng-Huang YQuan-Chen B(2021)BPNN anomaly data detection algorithm based on gray wolf algorithm to optimize K-means clustering2021 2nd International Conference on Artificial Intelligence and Computer Engineering (ICAICE)10.1109/ICAICE54393.2021.00038(156-161)Online publication date: Nov-2021
https://doi.org/10.1109/ICAICE54393.2021.00038
Safaei MAsadi SDriss MBoulila WAlsaeedi AChizari HAbdullah RSafaei M(2020)A Systematic Literature Review on Outlier Detection in Wireless Sensor NetworksSymmetry10.3390/sym1203032812:3(328)Online publication date: 25-Feb-2020
https://doi.org/10.3390/sym12030328
Derhab ABouras ABelaoued MMaglaras LKhan F(2020)Two-Hop Monitoring Mechanism Based on Relaxed Flow Conservation Constraints against Selective Routing Attacks in Wireless Sensor NetworksSensors10.3390/s2021610620:21(6106)Online publication date: 27-Oct-2020
https://doi.org/10.3390/s20216106
Show More Cited By

View Options

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 Issue’s Table of Contents