• PDF / 2,286,765 Bytes
• 24 Pages / 439.642 x 666.49 pts Page_size
• 79 Downloads / 204 Views

DOWNLOAD

REPORT

---

SST: synchronized spatial-temporal trajectory similarity search Peng Zhao1 · Weixiong Rao1 · Chengxi Zhang1 · Gong Su2 · Qi Zhang2 Received: 2 June 2019 / Revised: 19 November 2019 / Accepted: 1 April 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract The volume of trajectory data has become tremendously large in recent years. How to effectively and efficiently search similar trajectories has become an important task. Firstly, to measure the similarity between a trajectory and a query, literature works compute spatial similarity and temporal similarity independently, and next sum the two weighted similarities. Thus, two trajectories with high spatial similarity and low temporal similarity will have the same overall similarity with another two trajectories with low spatial similarity and high temporal similarity. To overcome this issue, we propose to measure the similarity by synchronously matching the spatial distance against temporal distance. Secondly, given this new similarity measurement, to overcome the challenge of searching top-k similar trajectories over a huge trajectory database with non-trivial number of query points, we propose to efficiently answer the top-k similarity search by following two techniques: trajectory database grid indexing and query partitioning. The performance of our proposed algorithms is studied in extensive experiments based on two real data sets. Keywords Trajectory · Spatial-Temporal Similarity · Top-k Search

 Weixiong Rao

[email protected] Peng Zhao [email protected] Chengxi Zhang [email protected] Gong Su [email protected] Qi Zhang [email protected] 1

School of Software Engineering, Tongji University, Shanghai, China

2

IBM Watson Research Lab, Ossining, NY, USA

Geoinformatica

1 Introduction Recent years have witnessed unprecedented amounts of GPS trajectories generated by location-based services (LBS). Analysis of the trajectories is an important task for many applications such as carpooling, route planning, traffic analysis and mobility pattern analysis [1]. Among such applications, trajectory search is a fundamental task to find the top-k most similar trajectories to an input query. For example, to find potential carpooling partners, we would like to search the most similar routes in terms of matching spatial distance and time schedule. In literature, many trajectory similarity measurements have been propose. Some works (e.g., [2–6]) measure spatial similarity only. Such similarity measurements obviously suffer from ineffectiveness issue. For example, in the carpooling recommendation system, spatial similarity is insufficient to evaluate the similarity between two trajectories: the carpooling partners should match the required time schedule. Others (e.g., [7–10]) take into account both spatial similarity and temporal similarity. Among these works, some separately measure spatial similarity from temporal similarity. For example, a very recent work [9] separately computes spatial and temporal similarities and then linearly co