A partial join approach for mining co-location patterns

ABSTRACT

Spatial co-location patterns represent the subsets of events whose instances are frequently located together in geographic space. We identified the computational bottleneck in the execution time of a current co-location mining algorithm. A large fraction of the join-based co-location miner algorithm is devoted to computing joins to identify instances of candidate co-location patterns. We propose a novel <i>partial-join</i> approach for mining co-location patterns efficiently. It transactionizes continuous spatial data while keeping track of the spatial information not modeled by transactions. It uses a transaction-based <i>Apriori</i> algorithm as a building block and adopts the instance join method for residual instances not identified in transactions. We show that the algorithm is correct and complete in finding all co-location rules which have prevalence and conditional probability above the given thresholds. An experimental evaluation using synthetic datasets and a real dataset shows that our algorithm is computationally more efficient than the join-based algorithm.

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: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• 3: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 4: C. Borgelt. Efficient implementations of apriori and eclat. In Workshop of Frequent Item Set Mining Implementations FIMI, 2003.
• 5: Ramez Elmasri , Shamkant B. Navathe, Fundamentals of database systems (2nd ed.), Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 6: George Karypis , Vipin Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, v.48 n.1, p.96-129, Jan. 1998 [doi>10.1006/jpdc.1997.1404]
• 7: B. Goethals. Frequent pattern mining implementations. http://www.cs.helsinki../u/goethals/software/index.html.
• 8: Jochen Hipp , Ulrich Güntzer , Gholamreza Nakhaeizadeh, Algorithms for association rule mining — a general survey and comparison, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.58-64, June, 2000 [doi>10.1145/360402.360421]
• 9: 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
• 10: Scott T. Leutenegger , Mario A. Lopez, The Effect of Buffering on the Performance of R-Trees, Proceedings of the Fourteenth International Conference on Data Engineering, p.164-171, February 23-27, 1998
• 11: 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]
• 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: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 14: S. Shekhar and S. Chawla. Spatial Databases: A Tour. Prentice Hall, ISBN 0130174807, 2003.
• 15: S. Shekhar and Y. Huang. Co-location Rules Mining: A Summary of Results. In Proc. of Symposium on Spatio and Temporal Database, 2001.
• 16: P. Tan, M. Steinbach, V. Kumar, C. Potter, S. Klooster, and A. Torregrosa. Finding spatio-temporal patterns in earth science data. In Proc. of KDD Workshop on Temporal Data Mining, 2001.
• 17: H. Xiong, S. Shekhar, Y. Huang, V. Kumar, X. Ma, and J. S. Yoo. A Framework for Discovering Co-location Patterns in Data Sets with Extended Spatial Objects. In Proc. 2004 SIAM International Conference on Data Mining (SDM), 2004.
• 18: M. J. Zaki and S. Parthasarathy. New algorithms for fast discovery of association rules. In Proc. of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1997.
• 19: 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]
• 20: Ying Zhao , George Karypis, Evaluation of hierarchical clustering algorithms for document datasets, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584877]

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:
association rule, co-location, join, spatial data mining