Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs

• We propose an indexing scheme for efficient graph query processing.
• We introduce a decomposition algorithm which works for all graphs.
• We design query answering algorithms for shortest path and kNN.

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.