中文摘要：

已有的城市道路网中的最近邻查询算法只考虑离查询者当前位置最近的对象,不能保证相对于即将行驶的路径也是最近的。提出基于最短路径的最近邻查询,给定当前位置和目的地,返回的是到它们之间的最短路径有最小绕道距离的对象。提出基于三阶段的查询算法SFV（Search-filter-verify）,利用双向Dijkstra算法得到最短路径的同时,保留有用的距离信息,再利用最小绕道距离的上下界关系过滤掉不可能成为结果的对象,最后精确计算剩余对象的最小绕道距离,得到结果。基于真实城市路网的实验结果表明,SFV与传统算法相比,有较高的性能和良好的扩展性。

英文摘要：

Existing nearest neighbour query algorithms for urban road networks only consider the objects which are nearest to the current location of the querying person, thus cannot guarantee it is also the nearest relative to the route to drive soon. In this paper we address the shortest path-based nearest neighbour query, by giving the current location and the destination, what will return are the objects whom having the shortest detour distance wrt the shortest paths between them. We propose the three-phase based search-filter-verify （SFV） query algorithm, it uses bidirectional Dijkstra＇s algorithm to find the shortest path, while preserves the useful distance information as well, then it utilises upper and lower boundaries relation of the minimum detour distance to filter out those objects impossible to become the outcomes, finally it precisely calculates the minimum detour distances of the remaining objects and gets the result. The experiments based on real urban road networks show that the SFV has higher performance and good sealability than the traditional algorithm.