Fast mining of spatial collocations

ABSTRACT

Spatial collocation patterns associate the co-existence of non-spatial features in a spatial neighborhood. An example of such a pattern can associate contaminated water reservoirs with certain deceases in their spatial neighborhood. Previous work on discovering collocation patterns converts neighborhoods of feature instances to itemsets and applies mining techniques for transactional data to discover the patterns. We propose a method that combines the discovery of spatial neighborhoods with the mining process. Our technique is an extension of a spatial join algorithm that operates on multiple inputs and counts long pattern instances. As demonstrated by experimentation, it yields significant performance improvements compared to previous approaches.

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: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 3: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 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: K. Koperski, J.Han, and N.Stefanovic. An efficient two-step method for classification of spatial data. In Proc. Symp. on Spatial Data Handling (SDH '98), 1998.
• 7: Nikos Mamoulis , Dimitris Papadias, Multiway spatial joins, ACM Transactions on Database Systems (TODS), v.26 n.4, p.424-475, December 2001 [doi>10.1145/503099.503101]
• 8: M. Ester, A.Frommelt, H.-P.Kriegel, and J.Sander. Algorithms for characterization and trend detection in spatial databases. In Proc. of the 4th Int. Conf. on Knowledge Discovery and Data Mining, pages 44--50, 1998.
• 9: M. Ester, A.Frommelt, J.Han, and J.Sander. Spatial data mining: Database primitives, algorithms and efficient dbms support. In Proc. of Int. Conf. on Databases in Office, Engineering and Science, 1999.
• 10: 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]
• 11: 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
• 12: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 13: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 14: 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
• 15: 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]
• 16: 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
• 17: S. Shekhar and S. Chawla. Spatial Databases: A Tour. Prentice Hall, 2003.
• 18: 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
• 19: Mohammed J. Zaki , Karam Gouda, Fast vertical mining using diffsets, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956788]

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: Spatial databases and GIS

General Terms:
Algorithms

Keywords:
collocation pattern, spatial databases