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

摘要

Extensive efforts have been made to improve the efficiency of the top-k trajectory similarity search(TkTSS), which retrieves k similarity trajectories for a given trajectory with a similarity function. When a user issues a initial query, s/he may find some desired trajectories are not in the result and may question why these expected trajectories are missing. To address this problem, we develop a so-called why-not spatial temporal TkTSS that is able to minimally modify the original top-k result into a result which contains the expected missing trajectories. In this paper, a novel hybrid SGP index is developed to organize the trajectories. Based on this index, an efficient time-first TkTSS framework is proposed to retrieve TkTSS. In order to refine the initial query to make all missing trajectories appear in the result, an innovative trajectory projection approach is designed to transfer the why-not question on TkTSS into a two-dimensional geometrical problem. Two type boundary areas pruned area (PA) and refined area (RA) are calculated to shrink the searching space. By constructing the compact area of RA, the searching space can be shrunk in a further step. Some pruning methods are proposed to accelerate the query process. Finally, extensive experiments with real-world and synthetic data offer evidence that the proposed solution performs much better than its competitors with respect to both effectiveness and efficiency. (C) 2021 Elsevier B.V. All rights reserved.