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

Direct link
Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
Linköping University, Department of Computer and Information Science, Database and information techniques. Linköping University, The Institute of Technology.
2016 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 82, no 1, 23-44 p.Article in journal (Refereed) Published
Abstract [en]

We propose TEDI, an indexing for solving shortest path, and k Nearest Neighbors (kNN) problems. TEDI is based on the tree decomposition methodology. The graph is first decomposed into a tree in which the node contains vertices. The shortest paths are stored in such nodes. These local shortest paths together with the tree structure constitute the index of the graph. Based on this index, algorithms can be executed to solve the shortest path, as well as the kNN problem more efficiently. Our experimental results show that TEDI offers orders-of-magnitude performance improvement over existing approaches on the index construction time, the index size and the query answering. (C) 2015 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
ACADEMIC PRESS INC ELSEVIER SCIENCE , 2016. Vol. 82, no 1, 23-44 p.
Keyword [en]
Graphs algorithms; Graph indexing; Shortest path; Tree decomposition; k Nearest Neighbors problems
National Category
Computer and Information Science
URN: urn:nbn:se:liu:diva-122642DOI: 10.1016/j.jcss.2015.06.008ISI: 000363092400003OAI: diva2:871771
Available from: 2015-11-16 Created: 2015-11-13 Last updated: 2015-11-16

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
In the same journal
Journal of computer and system sciences (Print)
Computer and Information Science

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: 114 hits
ReferencesLink to record
Permanent link

Direct link