Why-not questions about spatial temporal top-k trajectory similarity search

Highlights：

• We are the first to model the why-not questions on trajectory similarity search problem.

• An efficient hybrid space grid partition index (SGP) is designed to organize the trajectory segments. A time-first search framework is proposed to obtain an initial top-k similarity trajectories.

• We deduce the ranking update for the missing trajectories to a geometric problem, and transform the search space to a finite set of candidate vectors. Two type boundary areas PA and RA are calculated to reduce the searching space. By constructing the compact area of RA, the searching space can be further shrunk. Some pruning methods and the search algorithms are proposed to find the refined query with minimal penalty.

• Extensive experimental results on real-world datasets show that the proposed method performs much better than its competitors, and can obtain the best refined query with the lowest modification cost.

摘要

•We are the first to model the why-not questions on trajectory similarity search problem.•An efficient hybrid space grid partition index (SGP) is designed to organize the trajectory segments. A time-first search framework is proposed to obtain an initial top-k similarity trajectories.•We deduce the ranking update for the missing trajectories to a geometric problem, and transform the search space to a finite set of candidate vectors. Two type boundary areas PA and RA are calculated to reduce the searching space. By constructing the compact area of RA, the searching space can be further shrunk. Some pruning methods and the search algorithms are proposed to find the refined query with minimal penalty.•Extensive experimental results on real-world datasets show that the proposed method performs much better than its competitors, and can obtain the best refined query with the lowest modification cost.