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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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
Identifiers
URN: urn:nbn:se:liu:diva-94575DOI: 10.1145/2457317.2457355ISBN: 978-1-4503-1599-9 (print)OAI: oai:DiVA.org:liu-94575DiVA: diva2:633289
Conference
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

Authority records BETA

Wei-Kleiner, Fang

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 26 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf