Hash Join Based Spatial Collocation Pattern Mining

• Autorzy: Boiński P , Zakrzewicz M.
• Języki publikacji: EN

Abstrakty

EN

Every day, new and existing spatial databases, are populated by data from sensors, satellites and other devices providing spatial references. In this enormous flow of data, valuable and interesting patterns can be hidden. For researchers, one of the common tasks is to discover spatial collocations, i.e. subsets of spatial features that are frequently located together in space. The most widely known algorithm has been proposed by Shekhar et al. It is based on a step of spatial neighborhood materialization and a join-less generation of candidate instances, which are filtered in the remaining algorithm steps. We identified one of these steps to be a potential bottleneck of the algorithm. In this paper, we address the problem of efficient filtering of non clique instances and we propose to expand this task by applying hash join techniques. We have implemented and tested the aforementioned solution and shown that it results in better performance of the algorithm.

Słowa kluczowe

EN

spatial collocations; hash join; pattern mining

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2011
• Tom: Vol. 36, No. 1
• Strony: 3--15
• Opis fizyczny: Bibliogr. 13

Twórcy

autor

Boiński P

autor

Zakrzewicz M.

• Poznan University of Technology, Institute of Computing Science, ul. Piotrowo 2, 60- 965 Poznan, Poland,

Bibliografia

• [1] Agrawal R., Imielinski T., Swami A.N., Mining Association Rules between Sets of Items in Large Databases. In P. Buneman, S. Jajodia, eds., Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., ACM Press, 1993,207-216.
• [2] Agrawal R., Srikant R., Fast Algorithms for Mining Association Rules in Large Databases. In VLDB '94: Proceedings of the 20th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994, 487-499.
• [3] DeWitt D.J., Katz R.H., Olken F., Shapiro L.D., Stonebraker M.R., Wood D.A., Implementation techniques for main memory database systems. SIGMOD Rec., 14, 2, 1984, 1-8.
• [4] Fayyad U.M., Piatetsky-Shapiro G., Smyth P., From data mining to knowledge discovery: an overview. Advances in knowledge discovery and data mining, 1996, 1-34.
• [5] Franklin S.E., Remote Sensing for Sustainable Forest Management. CRC Press, Boca Raton, 2001.
• [6] Graf T., Hinrichs K., A Plane-Sweep Algorithm for the All-Nearest-Neighbors Problem for a Set of Convex Planar Objects. In WADS '93: Proceedings of the Third Workshop on Algorithms and Data Structures. Springer-Verlag, London, UK, 1993, 349-360.
• [7] Huang Y., Shekhar S., Xiong H., Discovering Co-location Patterns from Spatial Datasets: A General Approach. IEEE Transactions on Knowledge and Data Engineering, 16, 2004, 1472-1485.
• [8] Koperski K., Han J., Discovery of Spatial Association Rules in Geographic Information Databases. In SSD '95: Proceedings of the 4th International Symposium on Advances in Spatial Databases. Springer-Verlag, London, UK, 1995, 47-66.
• [9] Roddick J.F., Spiliopoulou M., A bibliography of temporal, spatial and spatiotemporal data mining research. SIGKDD Explor. Newsl., 1, 1, 1999, 34-38.
• [10] Shekhar S., Huang Y., Co-location Rules Mining: A Summary of Results. In Proc. of International Symposium on Spatio and Temporal Database(SSTD), 2001.
• [11] Wang Z., Zhou L., Lu J., Yip J. An order-clique based approach for mining maximal co-locations. Information Sciences, 179, 19, 2009, 3370-3382.
• [12] Yoo J.S., Shekhar S., A Partial Join Approach for Mining Co-location Patterns. In Proceedings of ACM International Symposium on Advances in Geographic Information Systems (ACM-GIS). 2004, 241-249.
• [13] Yoo J.S., Shekhar S., Celik M., A Join-Less Approach for Co-Location Pattern Mining: A Summary of Results. In Proceedings of the Fifth IEEE International Conference on Data Mining. IEEE Computer Society, Washington, DC, USA 2005 813-816.