›› 2013, Vol. 28 ›› Issue (4): 597-604.doi: 10.1007/s11390-013-1360-2

Special Issue: Data Management and Data Mining

• Special Section of EDB2012 • Previous Articles     Next Articles

Online Approach for Spatio-Temporal Trajectory Data Reduction for Portable Devices

Heemin Park1, Member, IEEE, Young-Jun Lee2, Jinseok Chae2,*, Member, IEEE, and Wonik Choi3, Member, IEEE   

  1. 1. Department of Computer Software Engineering, Sangmyung University, Cheonan 330-720, Korea;
    2. Department of Computer Science and Engineering, Incheon National University, Incheon 406-772, Korea;
    3. School of Information and Communication Engineering, Inha University, Incheon 402-751, Korea
  • Received:2012-09-12 Revised:2013-05-07 Online:2013-07-05 Published:2013-07-05
  • Supported by:

    This work was supported by the Incheon National University Research Grant of Korea in 2011. The preliminary version of the paper was published in the Proceedings of EDB2012.

As location data are widely available to portable devices, trajectory tracking of moving objects has become an essential technology for most location-based services. To maintain such streaming data of location updates from mobile clients, conventional approaches such as time-based regular location updating and distance-based location updating have been used. However, these methods suffer from the large amount of data, redundant location updates, and large trajectory estimation errors due to the varying speed of moving objects. In this paper, we propose a simple but efficient online trajectory data reduction method for portable devices. To solve the problems of redundancy and large estimation errors, the proposed algorithm computes trajectory errors and finds a recent location update that should be sent to the server to satisfy the user requirements. We evaluate the proposed algorithm with real GPS trajectory data consisting of 17 201 trajectories. The intensive simulation results prove that the proposed algorithm always meets the given user requirements and exhibits a data reduction ratio of greater than 87% when the acceptable trajectory error is greater than or equal to 10 meters.

[1] Dey A, Hightower J, de Lara E, Davies N. Location-basedservices. IEEE Pervasive Computing, 2010, 9(1): 11-12.

[2] Lee Y J, Kim M S, Chae J, Yoo W, Lee J W. An intelli-gent control scheme of moving objects based on smart phones.Database Research, 2012, 28(2): 19-36.

[3] Lee K J, Yang S B. Three effective top-down clustering algo-rithms for location database systems. Journal of ComputingScience and Engineering, 2010, 4(2): 173-187.

[4] Zheng Y, Zhang L, Xie X et al. Mining interesting locationsand travel sequences from GPS trajectories. In Proc. Int.Conf. World Wild Web, April 2009, pp. 791-800.

[5] Zheng Y, Li Q, Chen Y, Xie X, Ma W Y. Understandingmobility based on GPS data. In Proc. the 10th Int. Conf.Ubiquitous Computing, September 2008, pp. 312-321.

[6] Zheng Y, Xie X, Ma W Y. GeoLife: A collaborative socialnetworking service among user, location and trajectory. IEEEData Engineering Bulletin, 2010, 33(2): 32-39.

[7] Potamias M, Patroumpas K, Sellis T. Sampling trajectorystreams with spatiotemporal criteria. In Proc. the 18th In-ternational Conference on Scientific and Statistical DatabaseManagement, July 2006, pp. 275-284.

[8] Meratnia N, de By R A. Spatiotemporal compression tech-niques for moving point objects. In Proc. Int. Conf. Extend-ing Database Technology, March 2004, pp. 765-782.

[9] Zhou J, Leong H V, Lu Q et al. Optimizing update thresh-old for distance-based location tracking strategies in movingobject environments. In Proc. IEEE Int. Symp. a World ofWireless, Mobile and Multimedia Networks, June 2007.

[10] Lange R, Farrell T, Durr F, Rothermel K. Remote real-timetrajectory simplification. In Proc. IEEE Int. Conf. Perva-sive Computing and Communications, March 2009.

[11] Lange R, Durr F, Rothermel K. Online trajectory data reduc-tion using connection-preserving dead reckoning. In Proc. the5th Int. Conf. Mobile and Ubiquitous Systems: Computing,Networking, and Services, July 2008, Article No.52.

[12] Cao H, Wolfson O, Trajcevski G. Spatio-temporal data reduc-tion with deterministic error bounds. In Proc. Joint Work-shop on Foundations of Mobile Computing, September 2003,pp. 33-42.

[13] Orlando S, Orsini R, Raffaeta A, Roncato A, Silvestri C. Tra-jectory data warehouses: Design and implementation issues.Journal of Computing Science and Engineering, 2007, 1(2):211-232.

[14] Pitoura E, Samaras G. Locating objects in mobile comput-ing. IEEE Transactions on Knowledge and Data Engineer-ing, 2001, 13(4): 571-592.

[15] Douglas D H, Peucker T K. Algorithms for the reduction ofthe number of points required to represent a digitized lineor its caricature. The Canadian Cartographer, 1973, 10(2):112-122.
No related articles found!
Full text



[1] Cai Shijie; Zhang Fuyan;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[2] Shen Yidong;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[3] Yu Shengke;. Reasoning in H-Net: A Unified Approach to Intelligent Hypermedia Systems[J]. , 1996, 11(1): 83 -89 .
[4] Tian Zengping; Wang Yujun; Qu Yunyao; Shi Baile;. On the Expressive Power of F-Logic Language[J]. , 1997, 12(6): 510 -519 .
[5] WU Jinzhao; LIU Zhuojun;. Linear Strategy for Boolean Ring Based Theorem Proving[J]. , 2000, 15(3): 271 -279 .
[6] Jun-Hao Zheng, Lei Deng, Peng Zhang, and Don Xie. An Efficient VLSI Architecture for Motion Compensation of AVS HDTV Decoder[J]. , 2006, 21(3): 370 -377 .
[7] Hao Lang, Bin Wang, Gareth Jones, Jin-Tao Li, Fan Ding, and Yi-Xuan Liu. Query Performance Prediction for Information Retrieval Based on Covering Topic Score[J]. , 2008, 23(4 ): 590 -601 .
[8] David C. Schwartz and Michael S. Waterman. New Generations: Sequencing Machines and Their Computational Challenges[J]. , 2010, 25(1): 3 -9 .
[9] Yan-Hui Ding(丁艳辉), Member, CCF, Qing-Zhong Li(李庆忠), Senior Member, CCF Yong-Quan Dong(董永权), Member, CCF, and Zhao-Hui Peng(彭朝晖), Member, CCF. 2D Correlative-Chain Conditional Random Fields for Semantic Annotation of Web Objects[J]. , 2010, 25(4): 761 -770 .
[10] Javier Tejada-Cárcamo, Hiram Calvo, Alexander Gelbukh, and Kazuo Hara. Unsupervised WSD by Finding the Predominant Sense Using Context as a Dynamic Thesaurus[J]. , 2010, 25(5): 1030 -1039 .

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