导航系统中的K近邻搜索

摘要

汽车导航系统中常见的查询类型是查找k最近的邻居(kNN)的一个给定的查询对象(例如，汽车)使用实际的路网地图。对于道路网络(空间网络)，对象之间的距离取决于它们的网络连通性，计算对象之间的距离(例如最短路径)在计算上是昂贵的。本文提出了一种有效而准确的评估方法k基于空间网络数据库的移动信息系统的神经网络查询。该方法采用一阶Voronoi图和Dijkstra算法。该方法基于将一个大型网络划分到较小的Voronoi区域，然后预计算区域之间的距离。通过只对相邻区域的边界点进行跨网络计算，避免了每个对象对之间的全局预计算。我们对真实数据集的经验实验表明，我们提出的解决方案的性能比基于在线距离计算的方法高出一个数量级。此外，我们的方法比基于预计算的方法有更好的响应时间。

移动信息系统

摘要

版权

更多相关文章