TGA: Efficient Trajectory Approximate Top-k Query with High Precision
摘要
Top-k queries over trajectory data are essential in numerous applications, including travel recommendation, traffic control, and crowd positioning. Due to the high computational cost of exact search, many approximate approaches have been developed to balance efficiency and accuracy. However, current approximate methods inevitably suffer from significant precision loss when simplifying original trajectories into fixed-length vectors, bit arrays, or other simplified representations; additionally, they insufficiently consider the distance calculation specific to geospatial data, leading to difficulty in achieving high recall for approximate query results. Observing that approximate trajectory top-k queries can be regarded as a special case of Approximate Nearest Neighbor (ANN) search, we leverage this insight to address the aforementioned challenge. To this end, we propose TGA, a novel index structure designed to meet the dual requirements of high efficiency and high recall for trajectory top-k queries. TGA directly applies original trajectories and accurate distances to the ANN graph index, integrating a spatial indexing module, an approximate proximity graph, and probing optimization based on pruning strategies such as triangle inequality pruning. Experimental evaluations demonstrate that TGA achieves a precision exceeding 97% while providing a speedup of more than \(120\times \) compared with the exact approach.