Group Pattern Mining on Moving Objects’ Uncertain Trajectories


  • Shuang Wang
  • Lina Wu Software College Northeastern University Shenyang, China
  • Fuchai Zhou Software College Northeastern University Shenyang, China
  • Cuicui Zheng Software College Northeastern University Shenyang, China
  • Haibo Wang H. John Heinz III College Carnegie Mellon University Pittsburgh, USA


probabilistic frequent group pattern, uncertain data, trajectory pattern mining, moving object


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.


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.

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.

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.

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.

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).



Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.