Rapid detection of rare geospatial events: earthquake warning applications

ABSTRACT

The paper presents theory, algorithms, measurements of experiments, and simulations for detecting rare geospatial events by analyzing streams of data from large numbers of heterogeneous sensors. The class of applications are rare events - such as events that occur at most once a month - and that have very high costs for tardy detection and for false positives. The theory is applied to an application that warns about the onset of shaking from earthquakes based on real-time data gathered from different types of sensors with varying sensitivities located at different points in a region. We present algorithms for detecting events in Cloud computing servers by exploiting the scalability of Cloud computers while working within the limits of state synchronization across different servers in the Cloud. Ordinary citizens manage sensors in the form of mobile phones and tablets as well as special-purpose stationary sensors; thus the geospatial distribution of sensors depends on population densities. The distribution of the locations of events may, however, be different from population distributions. We analyze the impact of population distributions (and hence sensor distributions as well) on the efficacy of event detection. Data from sensor measurements and from simulations of earthquakes validate the theory.

References

1. K. M. Chandy, O. Etzion, and R. von Ammon, "10201 Executive Summary and Manifesto -- Event Processing," in Event Processing, ser. Dagstuhl Seminar Proceedings, no. 10201. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2011. {Online}. Available: http://drops.dagstuhl.de/opus/volltexte/2011/2985
2. A. Campbell, S. Eisenman, N. Lane, E. Miluzzo, R. Peterson, H. Lu, X. Zheng, M. Musolesi, K. Fodor, and G.-S. Ahn, "The rise of people-centric sensing," Internet Computing, IEEE, vol. 12, no. 4, pp. 12--21, 7--8 2008.
3. E. Cochran and J. Lawrence, "The quake-catcher network: Citizen science expanding seismic horizons," Seismological Research Letters, vol. 80, p. 26, Jan 2009.
4. (2011, 3) Measuring shaking intensity with mobile phones. {Online}. Available: http://ishakeberkeley.appspot.com/mission\BIBentrySTDinterwordspacing
5. S. Schneidert, H. Andrade, B. Gedik, K.-L. Wu, and D. S. Nikolopoulos, "Evaluation of streaming aggregation on parallel hardware architectures," in Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems, ser. DEBS '10. New York, NY, USA: ACM, 2010, pp. 248--257.
6. (2011, 3) Google app engine. {Online}. Available: http://code.google.com/appengine/BIBentrySTDinterwordspacing
7. M. Olson and K. M. Chandy, "Performance issues in cloud computing for cyber-physical applications," in Proceedings of the 4th IEEE International Conference on Cloud Computing. IEEE, 2011.
8. S. S. Roman Nurik. (2011, 3) Geospatial queries with google app engine using geomodel. {Online}. Available: http://code.google.com/apis/maps/articles/geospatial.htm
9. geohash.org. (2011, 3) Geohash. {Online}. Available: http://en.wikipedia.org/wiki/Geohash
10. DMATM 8358.2 The Universal Grids: Universal Transverse Mercator (UTM) and Universal Polar Stereographic (UPS), Defense Mapping Agency, Fairfax, VA, 9 1989.
11. DMATM 8358.1 Datums, Ellipsoids, Grids, and Grid Reference Systems, Defense Mapping Agency, Fairfax, VA, 9 1990.
12. Locating a position using utm coordinates. {Online}. Available: http://en.wikipedia.org/wiki/Universal_Transverse_Mercator
13. L. Nault, "Nga introduces global area reference system," PathFinder, 11 2006.
14. (2011, 3) Georef. {Online}. Available: http://en.wikipedia.org/wiki/Georef
15. N. G. P. Inc. (2011, 3) The natural area coding system. {Online}. Available: http://www.nacgeo.com/nacsite/documents/nac.asp
16. M. Faulkner, M. Olson, R. Chandy, J. Krause, K. M. Chandy, and A. Krause, "The Next Big One: Detecting Earthquakes and Other Rare Events from Community-based Sensors," in Proceedings of the 10th ACM/IEEE International Conference on Information Processing in Sensor Networks. ACM, 2011.
17. (2011, 3) Netquakes. {Online}. Available: http://earthquake.usgs.gov/monitoring/netquakes/
18. R. Herring, A. Hofleitner, S. Amin, T. Nasr, A. Khalek, P. Abbeel, and A. Bayen, "Using mobile phones to forecast arterial traffic through statistical learning," Submitted to Transportation Research Board, 2009.
19. A. Krause, E. Horvitz, A. Kansal, and F. Zhao, "Toward community sensing," in Proceedings of the 7th international conference on Information processing in sensor networks. IEEE Computer Society, 2008, pp. 481--492.
20. M. Mun, S. Reddy, K. Shilton, N. Yau, J. Burke, D. Estrin, M. Hansen, E. Howard, R. West, and P. Boda, "Peir, the personal environmental impact report, as a platform for participatory sensing systems research," in Proceedings of the 7th international conference on Mobile systems, applications, and services. ACM, 2009, pp. 55--68.
21. P. Völgyesi, A. Nádas, X. Koutsoukos, and Á. Lédeczi, "Air quality monitoring with sensormap," in Proceedings of the 7th international conference on Information processing in sensor networks. IEEE Computer Society, 2008, pp. 529--530.
22. J. Tsitsiklis, "Decentralized detection by a large number of sensors," Mathematics of Control, Signals, and Systems (MCSS), vol. 1, no. 2, pp. 167--182, 1988.
23. J. Chamberland and V. Veeravalli, "Decentralized detection in sensor networks," Signal Processing, IEEE Transactions on, vol. 51, no. 2, pp. 407--416, 2003.
24. F. Martincic and L. Schwiebert, "Distributed event detection in sensor networks," in Systems and Networks Communications, 2006. ICSNC'06. International Conference on. IEEE, 2006, p. 43.
25. K. Yamanishi, J. Takeuchi, G. Williams, and P. Milne, "On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms," Data Mining and Knowledge Discovery, vol. 8, no. 3, pp. 275--300, 2004.
26. M. Davy, F. Desobry, A. Gretton, and C. Doncarli, "An online support vector machine for abnormal events detection," Signal processing, vol. 86, no. 8, pp. 2009--2025, 2006.
27. S. Subramaniam, T. Palpanas, D. Papadopoulos, V. Kalogeraki, and D. Gunopulos, "Online outlier detection in sensor data using non-parametric models," in Proceedings of the 32nd international conference on Very large data bases. VLDB Endowment, 2006, pp. 187--198.
28. I. Onat and A. Miri, "An intrusion detection system for wireless sensor networks," in Wireless And Mobile Computing, Networking And Communications, 2005.(WiMob'2005), IEEE International Conference on, vol. 3. IEEE, 2005, pp. 253--259.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Mathematics of computing

  • Probability and statistics

• Networks

  • Network architectures