论文标题
时空上的TOP-K相似性搜索图中的轨迹
Spatio-Temporal Top-k Similarity Search for Trajectories in Graphs
论文作者
论文摘要
我们研究了找到$ k $的问题，最类似的轨迹与给定查询轨迹。我们的作品灵感来自Grossi等人的工作。 [6]认为轨迹是在图中行走的。每个访问的顶点都有一个时间间隔。 Grossi等。定义捕获时间和空间方面的相似性函数。我们改善了这种相似性函数，以得出一个新的时空距离函数，我们可以证明满足特定类型的三角形不等式。此距离功能是我们的索引结构的基础，可以有效地构造，只需要线性内存，并且可以快速回答最类似轨迹的顶部的查询。我们对现实世界和综合数据集的评估表明，我们的算法在数量级上优于索引时间的基准，同时达到相似或更好的查询时间和结果质量。
We study the problem of finding the $k$ most similar trajectories to a given query trajectory. Our work is inspired by the work of Grossi et al. [6] that considers trajectories as walks in a graph. Each visited vertex is accompanied by a time-interval. Grossi et al. define a similarity function that captures temporal and spatial aspects. We improve this similarity function to derive a new spatio-temporal distance function for which we can show that a specific type of triangle inequality is satisfied. This distance function is the basis for our index structures, which can be constructed efficiently, need only linear memory, and can quickly answer queries for the top-$k$ most similar trajectories. Our evaluation on real-world and synthetic data sets shows that our algorithms outperform the baselines with respect to indexing time by several orders of magnitude while achieving similar or better query time and quality of results.
