A generalized framework for mining spatio-temporal patterns in scientific data

ABSTRACT

In this paper, we present a general framework to discover spatial associations and spatio-temporal episodes for scientific datasets. In contrast to previous work in this area, features are modeled as geometric objects rather than points. We define multiple distance metrics that take into account objects' extent and thus are more robust in capturing the influence of an object on other objects in spatial neighborhood. We have developed algorithms to discover four different types of spatial object interaction (association) patterns. We also extend our approach to accommodate temporal information and propose a simple algorithm to derive spatio-temporal episodes. We show that such episodes can be used to reason about critical events. We evaluate our framework on real datasets to demonstrate its efficacy. The datasets originate from two different areas: Computational Molecular Dynamics and Computational Fluid Flow. We present results highlighting the importance of the identified patterns and episodes by using knowledge from the underlying domains. We also show that the proposed algorithms scale linearly with respect to the dataset size.

REFERENCES

• 1: M. J. Atallah. A linear time algorithm for the hausdorff distance between convex polygons. Information Processing Letters, 17:207--209, 1983.
• 2: Chris Bailey-Kellogg , Feng Zhao, Qualitative spatial reasoning: extracting and reasoning with spatial aggregates, AI Magazine, v.24 n.4, p.47-60, January 2004
• 3: J. P. Christiansen, Numerical simulation of hydrodynamics by the method of point vortices, Journal of Computational Physics, v.135 n.2, p.189-197, Aug. 1997 [doi>10.1006/jcph.1997.5701]
• 4: A. G. Cohn , S. M. Hazarika, Qualitative spatial representation and reasoning: an overview, Fundamenta Informaticae, v.46 n.1-2, p.1-29, May 2001
• 5: N. Cressie. Spatial Statistics. John Wiley and Sons, 1991.
• 6: J. Fernyhough et al. Event recognition using qualitative reasoning on automatically generated spatio-temporal models from visual input. In IJCAI97 Workshop on Spatial and Temporal Reasoning.
• 7: Chris Henze, Feature detection in linked derived spaces, Proceedings of the conference on Visualization '98, p.87-94, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 8: M. Jiang et al. Feature mining paradigms for scientific data. In SDM, 2003.
• 9: H. Mannila and H. Toivonen. Discovering generalised episodes using minimal occurences. In SIGKDD, 1996.
• 10: S. Mehta et al. Dynamic classification of defect structures in molecular dynamics simulation data. In SDM, 2005.
• 11: Sameep Mehta , Kaden Hazzard , Raghu Machiraju , Srinivasan Parthasarathy , John Wilkins, Detection and Visualization of Anomalous Structures in Molecular Dynamics Simulation Data, Proceedings of the conference on Visualization '04, p.465-472, October 10-15, 2004 [doi>10.1109/VIS.2004.23]
• 12: Yasuhiko Morimoto, Mining frequent neighboring class sets in spatial databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.353-358, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502564]
• 13: Robert Munro , Sanjay Chawla , Pei Sun, Complex Spatial Relationships, Proceedings of the Third IEEE International Conference on Data Mining, p.227, November 19-22, 2003
• 14: C. R. Rao and S. Suryawanshi. Statistical analysis of shape of objects based on landmark data. Proc Natl Acad Sci USA, 93(22):12132--12136, 1996.
• 15: D.A. Richie et al. Real-time multiresolution analysis for accelerated molecular dynamics simulations. In American Phy. Soc. Mar. Mtng, 2001.
• 16: Ari Sadarjoen , Frits H. Post , Bing Ma , David C. Banks , Hans-Georg Pagendarm, Selective visualization of vortices in hydrodynamic flows, Proceedings of the conference on Visualization '98, p.419-422, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 17: Shashi Shekhar , Yan Huang, Discovering Spatial Co-location Patterns: A Summary of Results, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.236-256, July 12-15, 2001
• 18: Deborah Silver , X. Wang, Volume tracking, Proceedings of the 7th conference on Visualization '96, p.157-ff., October 28-29, 1996, San Francisco, California, United States
• 19: W. R. Tobler. A computer movie simulating urban growth in the detroit region. Economic Geography 46:234--230, 1970.
• 20: H. Xiong et al. A framework for discovering co-location patterns in data sets with extended spatial objects. In SDM, 2004.
• 21: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 22: H. Yang et al. Discovering spatial relationships between approximately equivalent patterns. In BIOKDD, 2004.
• 23: H. Yang et al. A generalized framework for mining spatio-temporal patterns in scientific data. In OSU-CISRC-5/05-TR14, Ohio State University, 2005.
• 24: Kenneth Yip. Structural inferences from massive datasets. In IJCAI, 1997.
• 25: Mohammed J. Zaki , Srinivasan Parthasarathy , Mitsunori Ogihara , Wei Li, Parallel Algorithms for Discovery of Association Rules, Data Mining and Knowledge Discovery, v.1 n.4, p.343-373, December 1997 [doi>10.1023/A:1009773317876]
• 26: Xin Zhang , Nikos Mamoulis , David W. Cheung , Yutao Shou, Fast mining of spatial collocations, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014095]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Scientific databases; Spatial databases and GIS

General Terms:
Algorithms, Experimentation

Keywords:
scientific data, spatial object association, spatio-temporal association/episode