Abstract 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.
The work was supported by the National Key Research and Development Program of China under Grant No. 2016YFB0201402.
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.
Cite this article:
Guo-Wei Wang, Jin-Dou Zhang, Jing Li.Complete Your Mobility: Linking Trajectories Across Heterogeneous Mobility Data Sources[J] Journal of Computer Science and Technology, 2018,V33(4): 792-806
 Zheng Y. Trajectory data mining:An overview. ACM Trans. Intelligent Systems and Technology (TIST), 2015, 6(3):Article No. 29. 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. 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. 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. 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. Esling P, Agon C. Time-series data mining. ACM Computing Surveys (CSUR), 2012, 45(1):Article No. 12. 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. 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. 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. Jones K S. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 1972, 28(1):11-21. 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. Cortes C, Vapnik V. Support-vector networks. Machine Learning, 1995, 20(3):273-297. 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. 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. 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. Dietterich T G. Ensemble methods in machine learning. In Proc. the 1st Int. Workshop on Multiple Classifier Systems, June 2000. 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. Raskutti B, Kowalczyk A. Extreme re-balancing for SVMs:A case study. ACM SIGKDD Explorations Newsletter, 2004, 6(1):60-69. Ho T K. Random decision forests. In Proc. the 3rd Int. Conf. Document Analysis and Recognition, August 1995, pp.278-282. Munkres J. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 1957, 5(1):32-38. 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. 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. 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. Nanni M, Pedreschi D. Time-focused clustering of trajectories of moving objects. Journal of Intelligent Information Systems, 2006, 27(3):267-289. 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. 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. 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.
Copyright 2010 by Journal of Computer Science and Technology