Group Pattern Mining on Moving Objects’ Uncertain Trajectories
Keywords:
probabilistic frequent group pattern, uncertain data, trajectory pattern mining, moving objectAbstract
Uncertain is inherent in moving object trajectories due to measurement errors or time-discretized sampling. Unfortunately, most previous research on trajectory pattern mining did not consider the uncertainty of trajectory data. This paper focuses on the uncertain group pattern mining, which is to find the moving objects that travel together. A novel concept, uncertain group pattern, is proposed, and then a two-step approach is introduced to deal with it. In the first step, the uncertain objects’ similarities are computed according to their expected distances at each timestamp, and then the objects are clustered according to their spatial proximity. In the second step, a new algorithm to efficiently mining the uncertain group patterns is designed which captures the moving objects that move within the same clusters for certain timestamps that are possibly nonconsecutive. However the search space of group pattern is huge. In order to improve the mining efficiency, some pruning strategies are proposed to greatly reduce the search space. Finally, the effectiveness of the proposed concepts and the efficiency of the approaches are validated by extensive experiments based on both real and synthetic trajectory datasets.
References
Z. Li, B. Ding, et al, Swarm: Mining relaxed temporal moving object clusters, the VLDB Endowment, 3(1-2):723-734.
D. Wegener, D. Hecker, et al, Parallelization of R-programs with GridR in a GPS-trajectory mining application, 1st Ubiquitous Knowledge Discovery Workshop on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, (2008).
X. Li, J. Han, et al, Traffic density-based discovery of hot routes in road networks, the 10th International Symposium on Spatial and Temporal Databases, 441-459, (2007).
Z.Li, J.G. Lee, et al, Incremental Clustering for Trajectories, the 15th Database Systems for Advanced Applications, 32-46, (2010).
X. Li, J. Han, et al, Motion-alert: automatic anomaly detection in massive moving objects, the 4th IEEE International Conference on Intelligence and Security Informatics, 166-177.
N. Pelekis, I. Kopanakis, et al, Clustering uncertain trajectories, Knowledge and Information Systems, 28(1): 117-147. http://dx.doi.org/10.1007/s10115-010-0316-x
M. Chunyang, L. Hua, et al, KSQ: Top-k Similarity Query on Uncertain Trajectories, Knowledge and Data Engineering, IEEE Transactions, 25(9): 2049-2062.
J. Hoyoung, Managing Evolving Uncertainty in Trajectory Databases, IEEE Transactions on Knowledge and Data Engineering, 26(7): 1692-1705. http://dx.doi.org/10.1109/TKDE.2013.141
J. Gudmundsson, M. V. Kreveld, Computing longest duration flocks in trajectory data, the 14th annual ACM international symposium on Advances in geographic information systems, 35-42, (2006).
J. Gudmundsson, M. V. Kreveld, et al, Efficient detection of motion patterns in spatiotemporal data sets, the 12th annual ACM international symposium on Advances in geographic information systems, 250-257, (2004).
H. Jeune, M. Yiu, et al, Discovery of convoys in trajectory databases, the VLDB Endowment, 1(1):1068-1080.
H. Jeune, H. Shen, et al, Convoy queries in spatio-temporal databases, the 24th International Conference on Data Engineering, 1457-1459, (2008).
L.A. Tang, Y. Zheng, et al, A Framework of Traveling Companion Discovery on Trajectory Data Streams, ACM Transaction on Intelligent Systems and Technology, 5(1):3. http://dx.doi.org/10.1145/2542182.2542185
L.A. Tang, Y. Zheng, et al, Discovery of Traveling Companions from Streaming Trajectories, the 28th IEEE International conference on Data Engineering, 186-197, (2012).
K. Zheng, Y. Zheng, et al, Online Discovery of Gathering Patterns over Trajectories, IEEE Transactions on Knowledge and Data Engineering, 26(8): 1974-1988. http://dx.doi.org/10.1109/TKDE.2013.160
Y. Tong, L. Chen, et al., Mining frequent itemsets over uncertain databases, VLDB Endowment, 5(11): 1650-1661.
M. Muzammal, R. Raman, Mining sequential patterns from probabilistic databases, the 15th Pacific-Asia conference, 210-221, (2011).
Z. Zhao, D. Yan, et al, Mining probabilistically frequent sequential patterns in uncertain databases, the 15th International Conference on Extending Database Technology, 74- 85,(2012).
H. Wang, H. Su, K. et al, An Effectiveness Study on Trajectory Similarity Measures, the 24th Australasian Database Conference, 13-22, (2013).
J. Bezdek, R. Ehrlich, et al, FCM: The fuzzy c-means clustering algorithm, Computers Geosciences, 10(2):191-203.
C. Hwang, F. C.-H. Rhee, Uncertain fuzzy clustering: interval type-2 fuzzy approach to c-means, Fuzzy Systems, 15(1):107-120.
T. Bernecker, H.-P. Kriegel, et al, Probabilistic frequent itemset mining in uncertain databases, the 15th ACM SIGKDD on Knowledge discovery and data mining, 119-128,(2009).
Y. Theodoridis, J. R. O. Silva, et al, On the generation of spatiotemporal datasets, the 6th International Symposium on Advances in Spatial Databases, 147-164, (1999).
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
