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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

TGA: Efficient Trajectory Approximate Top-k Query with High Precision

  • Fengyi Liu,
  • Kai Zhang,
  • Yinan Jing,
  • Zhenying He,
  • X. Sean Wang

摘要

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.