TEDI: Efficient Shortest Path Query Answering on Graphs

Our Contributions

To overcome these difficulties, we propose TEDI (Tree Decomposition based Indexing) (Wei, F. (2010)), an indexing and query processing scheme for the shortest path query answering. Briefly stated, we first decompose the graph G into a tree in which each node contains a set of vertices in G. These tree nodes are called bags. Different from other partitioning based methods, there are overlapping among the bags, i.e., for any vertex v in G, there can be more than one bag in the tree which contains v. However, it is required that all these related bags constitute a connected subtree (see Definition 1 for the formal definition).

Based on the decomposed tree, we can execute the shortest path search in a bottom-up manner and the query time is decided by the height and the bag cardinality of the tree, instead of the size of the graph. If both of these two parameters are small enough, the query time can be substantially improved. Of course, in order to compute the shortest paths along the tree, we have to pre-compute the local shortest paths among the vertices in every bag of the tree. This constitutes the major part of the index structure of the TEDI scheme. Our main contributions are the following: