liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Finding nearest neighbors in road networks: a tree decomposition method
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
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)
Abstract [en]

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 SV, 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.
Keyword [en]
graphs, indexing, k nearest neighbors, shortest path, tree decomposition
National Category
Computer Systems
URN: urn:nbn:se:liu:diva-94575DOI: 10.1145/2457317.2457355ISBN: 978-1-4503-1599-9OAI: diva2:633289
EDBT/ICDT Workshops, March 18-22, 2013, Genoa, Italy
Available from: 2013-06-26 Created: 2013-06-26 Last updated: 2013-08-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Wei-Kleiner, Fang
By organisation
Database and information techniquesThe Institute of Technology
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 26 hits
ReferencesLink to record
Permanent link

Direct link