Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs
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
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.
Graphs algorithms; Graph indexing; Shortest path; Tree decomposition; k Nearest Neighbors problems
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-122642DOI: 10.1016/j.jcss.2015.06.008ISI: 000363092400003OAI: oai:DiVA.org:liu-122642DiVA: diva2:871771