Finding nearest neighbors in road networks
Fang Wei-Kleiner · 2013
Finding k Nearest Neighbors in one category of POIs (point of interests) belongs to the most frequently issued queries in the navigating systems or online maps. This problem can be formulated as given a graph G(V, E), a vertex u and S ⊆ V, finding k nearest neighbors of u in S. Classic Dijkstra's algorithm offers an optimal solution if S = V holds, but the performance deteriorates as S is of smaller size. Other approaches such as pre-computing and storing all the shortest distances require too much storage, thus suffer from drawbacks of scalability.