Finding nearest neighbors in road networks: a tree decomposition method

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. To address these problems, we propose TIkNN (stands for Tree decomposition-based Indexing for kNN), an indexing and query processing scheme for kNN query answering. TIkNN is based on the tree decomposition methodology. The graph is first decomposed into a tree in which each node (a.k.a. bag) contains more than one vertex from graph. The shortest paths are stored in such bags and these local paths together with the tree are the components of the index of the graph. Based on this index, step-wise query processing over the tree can be executed to find the nearest neighbors. Our experimental results show that TIkNN offers orders-of-magnitude performance improvement over Dijkstra's algorithm on query answering, while the storage requirement for the index structure is relatively small.