Finding nearest neighbors in road networks: a tree decomposition method
2013 (English)In: EDBT '13 Proceedings of the Joint EDBT/ICDT 2013 Workshops, New York: Association for Computing Machinery (ACM), 2013, 233-240 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
New York: Association for Computing Machinery (ACM), 2013. 233-240 p.
graphs, indexing, k nearest neighbors, shortest path, tree decomposition
IdentifiersURN: urn:nbn:se:liu:diva-94575DOI: 10.1145/2457317.2457355ISBN: 978-1-4503-1599-9OAI: oai:DiVA.org:liu-94575DiVA: diva2:633289
EDBT/ICDT Workshops, March 18-22, 2013, Genoa, Italy