Spatiotemporal Pattern Mining Technique for Location-Based Service System

ETRI Journal

关键词: location-based services;    location prediction;    movement pattern;    Spatiotemporal data mining;   

Others  :  1185680
DOI  :  10.4218/etrij.08.0107.0238

【 摘 要 】

In this paper, we offer a new technique to discover frequent spatiotemporal patterns from a moving object database. Though the search space for spatiotemporal knowledge is extremely challenging, imposing spatial and timing constraints on moving sequences makes the computation feasible. The proposed technique includes two algorithms, AllMOP and MaxMOP, to find all frequent patterns and maximal patterns, respectively. In addition, to support the service provider in sending information to a user in a push-driven manner, we propose a rule-based location prediction technique to predict the future location of the user. The idea is to employ the algorithm AllMOP to discover the frequent movement patterns in the user’s historical movements, from which frequent movement rules are generated. These rules are then used to estimate the future location of the user. The performance is assessed with respect to precision and recall. The proposed techniques could be quite efficiently applied in a location-based service (LBS) system in which diverse types of data are integrated to support a variety of LBSs.

   

【 参考文献 】

• [1]S. Jensen, A. Kligys, T.B. Pedersen, and I. Timko, "Multidimensional Data Modeling for Location-Based Services," Proc. VLDB, vol. 13, no. 1, 2004, pp.1-21.
• [2]K.W. Min, K.W. Nam, and J.W. Kim, "Multilevel Location Trigger in Distributed Mobile Environments for Location-Based Services," ETRI J., vol. 29, no. 1, 2007, pp. 107-109.
• [3]R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules," Proc. VLDB, 1994, pp. 487-499.
• [4]R. Srikant and R. Agrawal, "Mining Sequential Patterns: Generalizations and Performance Improvements," Proc. EDBT, 1996, pp. 3-17.
• [5]N. Mamoulis, H. Cao, G. Kollios, M. Hadjieleftheriou, Y. Tao, and D.W. Cheung, "Mining, Indexing, and Querying Historical Spatiotemporal Data," Proc. SIGKDD, 2004, pp. 236-245.
• [6]I. Tsoukatos and D. Gunopulos, "Efficient Mining of Spatiotemporal Patterns," Proc. SSTD, LNCS, vol. 2121, 2001, pp. 425-442.
• [7]D. Katsaros, A. Nanopoulos, M. Karakaya, G. Yavas, O. Ulusoy, and Y. Manolopoulos, "Clustering Mobile Trajectories for Resource Allocation in Mobile Environments," Proc. Intelligent Data Analysis Conference, vol. 2810, 2003, pp. 319-329.
• [8]G. Yava, D. Katsaros. O.Ulusoy, and Y. Manolopoulus, "A Data Mining Approach for Location Prediction in Mobile Environments," Data and Knowledge Engineering, vol. 54, no. 2, Aug. 2005, pp. 121-146.
• [9]M. Ester, H.P. Kriegel, J. Sander, and X. Xu, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise," Proc. ACM Knowledge Discovery and Data Mining, 1996, pp. 226-231.
• [10]J.F. Allen, "Maintaining Knowledge about Temporal Intervals," Communication of ACM, vol. 26, 1983, pp. 832-843.
• [11]D. Pfoser and C.S. Jensen, "Capturing the Uncertainty of Moving-Object Representations," Proc. Advances in Spatial Databases, 6th International. Symposium SSD, 1999, pp. 111-132.
• [12]N. Meratnia and R.D. By, "Aggregation and Comparison of Trajectories," Proc. GIS, ACM, 2002, pp. 49-54.