Improvement of OPW-TR Algorithm for Compressing GPS Trajectory Data = Improvement of OPW-TR Algorithm for Compressing GPS Trajectory Data

다국어 초록 (Multilingual Abstract)

Massive volumes of GPS trajectory data bring challenges to storage and processing. These issues can be addressed by compression algorithm which can reduce the size of the trajectory data. A key requirement for GPS trajectory compression algorithm is to reduce the size of the trajectory data while minimizing the loss of information. Synchronized Euclidean distance (SED) as an important error measure is adopted by most of the existing algorithms. In order to further reduce the SED error, an improved algorithm for open window time ratio (OPW-TR) called local optimum open window time ratio (LO-OPW-TR) is proposed. In order to make SED error smaller, the anchor points are selected by calculating point`s accumulated synchronized Euclidean distance (ASED). A variety of error metrics are used for the algorithm evaluation. The experimental results show that the errors of our algorithm are smaller than the existing algorithms in terms of SED and speed errors under the same compression ratio.

참고문헌 (Reference)

1 Y. Zheng, "Understanding mobility based on GPS data" 312-321, 2008

2 Y. Chen, "Trajectory simplification method for location-based social networking services" 33-40, 2009

3 F. Giannotti, "Trajectory pattern mining" 330-339, 2007

4 N. Meratnia, "Spatiotemporal compression techniques for moving point objects" 765-782, 2004

5 M. Potamias, "Sampling trajectory streams with spatiotemporal criteria" 275-284, 2006

6 J. Muckell, "SQUISH : an online approach for GPS trajectory compression" 2011

7 A. Kolesnikov, "Reduced-search dynamic programming for approximation of polygonal curves" 24 (24): 2243-2254, 2003

8 J. C. Perez, "Optimum polygonal approximation of digitized curves" 15 (15): 743-750, 1994

9 Y. Zheng, "Mining interesting locations and travel sequences from GPS trajectories" 791-800, 2009

10 M. Morzy, "Mining frequent trajectories of moving objects for location prediction" 667-680, 2007

11 M. Salotti, "Improvement of Perez and Vidal algorithm for the decomposition of digitized curves into line segments" 878-882, 2000

12 Y. Zheng, "GeoLife : a collaborative social networking service among user, location and trajectory" 33 (33): 32-39, 2010

13 Y. Zheng, "GeoLife 2.0: a location-based social networking service" 357-358, 2009

14 Y. Xuan, "GPS location data reducing based on turning point judgment method" 7395-7398, 2011

15 Y. Zheng, "Efficient scheme for GPS data compression" 26 (26): 134-138, 2005

16 J. Muckell, "Compression of trajectory data : a comprehensive evaluation and new approach" 18 (18): 435-460, 2014

17 E. Keogh, "An online algorithm for segmenting time series" 289-296, 2001

18 M. Salotti, "An efficient algorithm for the optimal polygonal approximation of digitized curves" 22 (22): 215-221, 2001

19 D. H. Douglas, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature" 10 (10): 112-122, 1973

20 A. Kolesnikov, "A fast near-optimal min-# polygonal approximation of digitized curves" 418-422, 2002

21 M. Chen, "A fast O(N)multiresolution polygonal approximation algorithm for GPS trajectory simplification" 21 (21): 2770-2785, 2012