›› 2016, Vol. 31 ›› Issue (1): 167-184.doi: 10.1007/s11390-016-1619-5

Special Issue: Data Management and Data Mining

• Data Management and Data Mining • Previous Articles     Next Articles

Context-Based Moving Object Trajectory Uncertainty Reduction and Ranking in Road Network

Jian Dai1,2,3, Zhi-Ming Ding1*, Member, CCF, and Jia-Jie Xu4, Member, CCF   

  1. 1 School of Computer Science, Beijing University of Technology, Beijing 100124, China;
    2 University of Chinese Academy of Sciences, Beijing 100049, China;
    3 Institute of Software, Chinese Academy of Sciences, Beijing 100190, China;
    4 School of Computer Science and Technology, Soochow University, Suzhou 215000, China
  • Received:2014-02-12 Revised:2015-08-19 Online:2016-01-05 Published:2016-01-05
  • Contact: Zhi-Ming Ding E-mail:zmding@bjut.edu.cn
  • About author:Jian Dai received his B.S. degree from University of Science and Technology of China, Hefei, in 2004. He is a Ph.D. candidate in the Institute of Software, Chinese Academy of Sciences, Beijing. His research interests include spatial keyword management and spatio-temporal data management.
  • Supported by:

    This work was supported by the National High Technology Research and Development 863 Program of China under Grant No. 2013AA01A603, the Pilot Project of Chinese Academy of Sciences under Grant No. XDA06010600, and the National Natural Science Foundation of China under Grant No. 61402312.

To support a large amount of GPS data generated from various moving objects, the back-end servers usually store low-sampling-rate trajectories. Therefore, no precise position information can be obtained directly from the back-end servers and uncertainty is an inherent characteristic of the spatio-temporal data. How to deal with the uncertainty thus becomes a basic and challenging problem. A lot of researches have been rigidly conducted on the uncertainty of a moving object itself and isolated from the context where it is derived. However, we discover that the uncertainty of moving objects can be efficiently reduced and effectively ranked using the context-aware information. In this paper, we focus on context-aware information and propose an integrated framework, Context-Based Uncertainty Reduction and Ranking (CURR), to reduce and rank the uncertainty of trajectories. Specifically, given two consecutive samplings, we aim to infer and rank the possible trajectories in accordance with the information extracted from context. Since some context-aware information can be used to reduce the uncertainty while some context-aware information can be used to rank the uncertainty, to leverage them accordingly, CURR naturally consists of two stages:reduction stage and ranking stage which complement each other. We also implement a prototype system to validate the effectiveness of our solution. Extensive experiments are conducted and the evaluation results demonstrate the efficiency and high accuracy of CURR.

[1] Kuijpers B, Othman W. Trajectory databases:Data models, uncertainty and complete query languages. In Proc. the 11th Int. Conf. Database Theory, Jan. 2007, pp.224-238.

[2] Kuijpers B, Othman W. Modeling uncertainty of moving objects on road networks via space-time prisms. International Journal of Geographical Information Science, 2009, 23(9):1095-1117.

[3] Emrich T, Kriegel H P, Mamoulis N, Renz M, Züfle A. Querying uncertain spatio-temporal data. In Proc. the 28th ICDE, April 2012, pp.354-365.

[4] Zheng K, Trajcevski G, Zhou X, Scheuermann P. Probabilistic range queries for uncertain trajectories on road networks. In Proc. the 14th EDBT, March 2011, pp.283-294.

[5] Pfoser D, Jensen C S. Capturing the uncertainty of movingobject representations. In Proc. the 6th SSD, July 1999, pp.111-132.

[6] Jeung H, Yiu M L, Zhou X, Jensen C S. Path prediction and predictive range querying in road network databases. VLDB J., 2010, 19(4):585-602.

[7] Karimi H A, Liu X. A predictive location model for locationbased services. In Proc. the 11th GIS, November 2003, pp.126-133.

[8] Lou Y, Zhang C, Zheng Y, Xie X, Wang W, Huang Y. Mapmatching for low-sampling-rate GPS trajectories. In Proc. the 17th GIS, November 2009, pp.352-361.

[9] Zheng K, Zheng Y, Xie X, Zhou X. Reducing uncertainty of low-sampling-rate trajectories. In Proc. the 28th ICDE, April 2012, pp.1144-1155.

[10] Wu L, Xiao X, Deng D, Cong G, Zhu A D, Zhou S. Shortest path and distance queries on road networks:An experimental evaluation. PVLDB, 2012, 5(5):406-417.

[11] Brakatsoulas S, Pfoser D, Salas R, Wenk C. On mapmatching vehicle tracking data. In Proc. the 31st VLDB, August 30-September 2, 2005, pp.853-864.

[12] Quddus M A, Ochieng W Y, Noland R B. Current mapmatching algorithms for transport applications:State-ofthe-art and future research directions. Transportation Research Part C:Emerging Technologies, 2007, 15(5):312- 328.

[13] Yuan J, Zheng Y, Zhang C, Xie X, Sun G Z. An interactivevoting based map matching algorithm. In Proc. the 11th IEEE MDM, May 2010, pp.43-52.

[14] Lou Y, Zhang C, Zheng Y, Xie X, Wang W, Huang Y. Mapmatching for low-sampling-rate GPS trajectories. In Proc. the 17th ACM GIS, November 2009, pp.352-361.

[15] Trajcevski G, Wolfson O, Zhang F, Chamberlain S. The geometry of uncertainty in moving objects databases. In Proc. the 8th EDBT, March 2002, pp.233-250.

[16] Trajcevski G, Wolfson O, Cao H, Lin H, Zhang F, Rishe N. Managing uncertain trajectories of moving objects with domino. In Proc. the 4th ICEIS, April 2002, pp.218-225.

[17] Ding Z, Güting R H. Uncertainty management for network constrained moving objects. In Proc. the 15th DEXA, August 30-September 3, 2004, pp.411-421.

[18] Gonzalez H, Han J, Li X, Myslinska M, Sondag J P. Adaptive fastest path computation on a road network:A traffic mining approach. In Proc. the 33rd VLDB, Sept. 2007, pp.794-805.

[19] Güting R H, Behr T, Xu J. Efficient k-nearest neighbor search on moving object trajectories. The VLDB Journal, 2010, 19(5):687-714.

[20] Li Z, Ji M, Lee J G, Tang L A, Yu Y, Han J, Kays R. MoveMine:Mining moving object databases. In Proc. SIGMOD, June 2010, pp.1203-1206.

[21] Li Z, Ding B, Han J, Kays R, Nye P. Mining periodic behaviors for moving objects. In Proc. the 16th KDD, July 2010, pp.1099-1108.

[22] Li X, Han J, Lee J G, Gonzalez H. Traffic density-based discovery of hot routes in road networks. In Proc. the 10th SSTD, July 2007, pp.441-459.

[23] Sacharidis D, Patroumpas K, Terrovitis M, Kantere V, Potamias M, Mouratidis K, Sellis T K. On-line discovery of hot motion paths. In Proc. the 11th EDBT, March 2008, pp.392-403.

[24] Chen Z, Shen H T, Zhou X, Zheng Y, Xie X. Searching trajectories by locations:An efficiency study. In Proc. SIGMOD Conference, June 2010, pp.255-266.

[25] Cuppens F, Demolombe R. How to recognize interesting topics to provide cooperative answering. Information Systems, 1989, 14(2):163-173.

[26] Gaasterland T, Godfrey P, Minker J. An overview of cooperative answering. J. Intell. Inf. Syst., 1992, 1(2):123-157.

[27] Andersen O, Jensen C S, Torp K, Yang B. Ecotour:Reducing the environmental footprint of vehicles using Eco-routes. In Proc. the 14th IEEE MDM, June 2013, pp.338-340.

[28] Su H, Zheng K, Wang H, Huang J, Zhou X. Calibrating trajectory data for similarity-based analysis. In Proc. SIGMOD, June 2013, pp.833-844.

[29] Zheng K, Shang S, Yuan N J, Yang Y. Towards efficient search for activity trajectories. In Proc. the 29th IEEE ICDE, April 2013, pp.230-241.
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