›› 2018, Vol. 33 ›› Issue (4): 792-806.doi: 10.1007/s11390-018-1856-x

• Computer Networks and Distributed Computing • Previous Articles     Next Articles

Complete Your Mobility: Linking Trajectories Across Heterogeneous Mobility Data Sources

Guo-Wei Wang, Jin-Dou Zhang, Jing Li, Member, CCF, ACM   

  1. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China
  • Received:2017-05-09 Revised:2018-01-26 Online:2018-07-05 Published:2018-07-05
  • About author:Guo-Wei Wang is a Ph.D. student in School of Computer Science and Technology at University of Science and Technology of China (USTC), Hefei. He received his Bachelor's degree at USTC, Hefei, in 2012. His current research interests include trajectory data mining and cloud computing.
  • Supported by:

    The work was supported by the National Key Research and Development Program of China under Grant No. 2016YFB0201402.

Nowadays, human activities and movements are recorded by a variety of tools, forming different trajectory sets which are usually isolated from one another. Thus, it is very important to link different trajectories of one person in different sets to provide massive information for facilitating trajectory mining tasks. Most prior work took advantages of only one dimensional information to link trajectories and can link trajectories in a one-to-many manner (providing several candidate trajectories to link to one specific trajectory). In this paper, we propose a novel approach called one-to-one constraint trajectory linking with multi-dimensional information (OCTL) that links the corresponding trajectories of one person in different sets in a one-to-one manner. We extract multidimensional features from different trajectory datasets for corresponding relationships prediction, including spatial, temporal and spatio-temporal information, which jointly describe the relationships between trajectories. Using these features, we calculate the corresponding probabilities between trajectories in different datasets. Then, we formulate the link inference problem as a bipartite graph matching problem and employ effective methods to link one trajectory to another. Moreover, the advantages of our approach are empirically verified on two real-world trajectory sets with convincing results.

[1] Zheng Y. Trajectory data mining:An overview. ACM Trans. Intelligent Systems and Technology (TIST), 2015, 6(3):Article No. 29.

[2] Wang Y Z, Yuan N J, Lian D F, Xu L L, Xie X, Chen E H, Rui Y. Regularity and conformity:Location predic tion using heterogeneous mobility data. In Proc. the 21st ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, August 2015, pp.1275-1284.

[3] Zheng Y, Zhang L Z, Ma Z X, Xie X, Ma W Y. Recom mending friends and locations based on individual location history. ACM Trans. the Web (TWEB), 2011, 5(1):Article No. 5.

[4] Xiao X Y, Zheng Y, Luo Q, Xie X. Inferring social ties be tween users with human location history. Journal of Am bient Intelligence and Humanized Computing, 2014, 5(1):3-19.

[5] Zheng Y, Capra L, Wolfson O, Yang H. Urban computing:Concepts, methodologies, and applications. ACM Trans. Intelligent Systems and Technology (TIST) 2014, 5(3):Article No. 38.

[6] Esling P, Agon C. Time-series data mining. ACM Computing Surveys (CSUR), 2012, 45(1):Article No. 12.

[7] Cao W, Wu Z W, Wang D, Li J, Wu H S. Automatic user identification method across heterogeneous mobility data sources. In Proc. the 32nd Int. Conf. Data Engineering, May 2016, pp.978-989.

[8] Wu H Y, Xue M Q, Cao J N, Karras P, Ng W S, Koo K K. Fuzzy trajectory linking. In Proc. the 32nd Int. Conf. Data Engineering, May 2016, pp.859-870.

[9] Li Q N, Zheng Y, Xie X, Chen Y K, Liu W Y, Ma W Y. Mining user similarity based on location history. In Proc. the 16th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems, November 2008.

[10] Jones K S. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 1972, 28(1):11-21.

[11] Das G, Gunopulos D, Mannila H. Finding similar time series. In Proc. the 1st European Symp. Principles of Data Mining and Knowledge Discovery, June 1997, pp.88-100.

[12] Cortes C, Vapnik V. Support-vector networks. Machine Learning, 1995, 20(3):273-297.

[13] Walker S H, Duncan D B. Estimation of the probability of an event as a function of several independent variables. Biometrika, 1967, 54(1/2):167-179.

[14] Chawla N V. Data mining for imbalanced datasets:An overview. In Data Mining and Knowledge Discovery Handbook, Maimon O, Rokach L (eds.), Springer, 2009, pp.875-886.

[15] Chai X Y, Deng L, Yang Q, Ling C X. Test-cost sensitive naive Bayes classification. In Proc. the 4th IEEE Int. Conf. Data Mining, November 2004, pp.51-58.

[16] Dietterich T G. Ensemble methods in machine learning. In Proc. the 1st Int. Workshop on Multiple Classifier Systems, June 2000.

[17] Chawla N V, Bowyer K W, Hall L O, Kegelmeyer W P. SMOTE:Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 2002, 16(1):321-357.

[18] Raskutti B, Kowalczyk A. Extreme re-balancing for SVMs:A case study. ACM SIGKDD Explorations Newsletter, 2004, 6(1):60-69.

[19] Ho T K. Random decision forests. In Proc. the 3rd Int. Conf. Document Analysis and Recognition, August 1995, pp.278-282.

[20] Munkres J. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 1957, 5(1):32-38.

[21] Kong X N, Zhang J W, Yu P S. Inferring anchor links across multiple heterogeneous social networks. In Proc. the 22nd ACM Int. Conf. Information & Knowledge Management, October 2013, pp.179-188.

[22] Agrawal R, Faloutsos C, Swami A. Efficient similarity search in sequence databases. In Proc. the 4th Int. Conf. Foundations of Data Organization and Algorithms, October 1993, pp.69-84.

[23] Chen L, Ng R. On the marriage of Lp-norms and edit distance. In Proc. the 30th Int. Conf. Very Large Data BasesVolume 30, August 2004, pp.792-803.

[24] Nanni M, Pedreschi D. Time-focused clustering of trajectories of moving objects. Journal of Intelligent Information Systems, 2006, 27(3):267-289.

[25] Chen L, Özsu M T, Oria V. Robust and fast similarity search for moving object trajectories. In Proc. ACM SIGMOD Int. Conf. Management of Data, June 2005, pp.491-502.

[26] Pelekis N, Kopanakis I, Marketos G, Ntoutsi I, Andrienko G, Theodoridis Y. Similarity search in trajectory databases. In Proc. the 14th Int. Symp. Temporal Representation and Reasoning, June 2007, pp.129-140.

[27] Wang X Y, Mueen A, Ding H, Trajcevski G, Trajcevski P, Keogh E. Experimental comparison of representation methods and distance measures for time series data. Data Mining and Knowledge Discovery, 2013, 26(2):275-309.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved