A framework for mining topological patterns in spatio-temporal databases

ABSTRACT

Mining topological patterns in spatial databases has received a lot of attention. However, existing work typically ignores the temporal aspect and suffers from certain efficiency problems. They are not scalable for mining topological patterns in spatio-temporal databases. In this paper, we study the problem for mining topological patterns by incorporating the temporal aspect in the mining process. We introduce a summary-structure that records the instances' count information of a feature in a region within a time window. Using this structure, we design an algorithm, TopologyMiner, to find interesting topological patterns without the need to generate candidates. Experimental results show that TopologyMiner is effective and scalable in finding topological patterns and outperforms Apriori-like algorithm by a few orders of magnitudes.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 3: Jiawei Han , Jian Pei, Mining frequent patterns by pattern-growth: methodology and implications, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.14-20, Dec. 2000 [doi>10.1145/380995.381002]
• 4: Yan Huang , Hui Xiong , Shashi Shekhar , Jian Pei, Mining confident co-location rules without a support threshold, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952630]
• 5: Krzysztof Koperski , Jiawei Han, Discovery of Spatial Association Rules in Geographic Information Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.47-66, August 06-09, 1995
• 6: M. Ester, A. Frommelt, J. Han, and J. Sander. Algorithms for characterization and trend detection in spatial databases. ACM SIGKDD, 1998.
• 7: 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]
• 8: 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
• 9: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 10: Jörg Sander , Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications, Data Mining and Knowledge Discovery, v.2 n.2, p.169-194, June 1998 [doi>10.1023/A:1009745219419 ]
• 11: 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
• 12: 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

General Terms:
Algorithms, Design

Keywords:
data mining, spatio-temporal database