Adaptive simplification of GPS trajectories with geographic context – a quadtree-based approach

ABSTRACT

Big GPS trajectory datasets can have redundant spatio-temporal information for applications, which requires simplification as a key preprocessing for modeling. Many existing simplification methods focus on the geometric information from a trajectory per se. Conversely, methods considering geographic context often fail to provide spatially adaptive simplification, or require complex parameter settings to achieve this task. This study proposes a novel two-stage adaptive trajectory simplification method embedding spatial indexing, enrichment, and aggregation in an integrated process. The first stage employs a quadtree for the subdivision depending on the density of geographic context features (i.e. POIs), leading to a variable-resolution representation of the area. The second stage aggregates trajectory waypoints locating in the same quadtree leaf node into a representative point, making the aggregation adapting to the spatial layout of the geographic feature in the first stage. Evaluation with a real-world vehicle trajectory dataset shows that the proposed approach can automatically simplify trajectory segments at variable compression ratios with greater simplification in areas with sparse context features (e.g. rural) and less simplification in areas with dense context features (e.g. urban). More importantly, the method can still preserve inter-trajectory distances between original trajectories and simplified ones, while significantly reducing the computing time.

KEYWORDS:

• Trajectory simplification
• adaptive simplification
• quadtree
• geographic context
• points of interest (POIs)

Acknowledgments

The authors would like to thank Vodafone Innovus for providing the trajectory data. The authors also appreciate the comments of three anonymous reviewers which helped improve the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Data and code availability statement

The data and codes that support the findings of this study are available with a DOI at https://doi.org/10.6084/m9.figshare.11708994. The vehicle trajectory data cannot be made publicly available to protect the privacy of research participants. Simulated vehicle trajectories are provided via the link for demonstration purposes.

Additional information

Funding

This work has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 780754, project Track & Know.

Notes on contributors

Cheng Fu

Cheng Fu is a postdoctoral researcher of the Geographical Information Systems unit in the Department of Geography, University of Zurich, Switzerland. His research interests include trajectory modeling, place and big data, and social media.

Haosheng Huang

Haosheng Huang starts a tenure track professorship in Cartography and GIScience at Ghent University, Belgium in February 2020. His research interests include location based services (LBS), spatial cognition, computational mobility and activity analytics, and urban informatics. Please refer to https://users.ugent.be/~haohuang/ for more details.

Robert Weibel

Robert Weibel is a Professor of Geographic Information Science at the University of Zurich, Switzerland. He is interested in mobility analytics with applications in transportation and health, spatial analysis for linguistic applications, and computational cartography.