An Efficient Query Algorithm for Trajectory Similarity Based on Frechet Distance Threshold

作者：Guo, Ning; Ma, Mengyu; Xiong, Wei; Chen, Luo^*; Jing, Ning

来源：ISPRS International Journal of Geo-Information, 2017, 6(11): 326.

DOI：10.3390/ijgi6110326

• trajectory similarity
• Frechet distance
• query algorithm
• parallel computing
• Message Passing Interface

The processing and analysis of trajectories are the core of many location-based applications and services, while trajectory similarity is an essential concept regularly used. To address the time-consuming problem of similarity query, an efficient algorithm based on Frechet distance called Ordered Coverage Judge (OCJ) is proposed, which could realize the filtering query with a given Frechet distance threshold on large-scale trajectory datasets. The OCJ algorithm can obtain the result set quickly by a two-step operation containing morphological characteristic filtering and ordered coverage judgment. The algorithm is expedient to be implemented in parallel for further increases of speed. Demonstrated by experiments over real trajectory data in a multi-core hardware environment, the new algorithm shows favorable stability and scalability besides its higher efficiency in comparison with traditional serial algorithms and other Frechet distance algorithms.

• 出版日期2017-11
• 单位中国人民解放军国防科学技术大学