Efficiently Indexing Shortest Paths by Exploiting Symmetry in Graphs
Authors
- Yanghua Xiao (Fudan university, China)
- Wentao Wu (Fudan University, China)
- Jian Pei (Simon Fraser, Canada)
- Wei Wang (Fudan University, China)
- Zhenying He (Fudan University, China)
Abstract
Shortest path queries (SPQ) are essential in many graph analysis and mining tasks. However, answering shortest path queries on-the-fly on large graphs is costly. To online answer shortest path queries, we may materialize and index shortest paths. However, a straightforward index of all shortest paths in a graph of N vertices takes O(N^2) space. In this paper, we tackle the problem of indexing shortest paths and online answering shortest path queries. As many large real graphs are shown richly symmetric, the central idea of our approach is to use graph symmetry to reduce the index size while retaining the correctness and the efficiency of shortest path query answering. Technically, we develop a framework to index a large graph at the orbit level instead of the vertex level so that the number of breadth-first search trees materialized is reduced from O(N) to O(|\Delta|), where |\Delta| <= N is the number of orbits in the graph. We explore orbit adjacency and local symmetry to obtain compact breadth-first-search trees (compact BFS-trees). An extensive empirical study using both synthetic data and real data shows that compact BFS-trees can be built efficiently and the space cost can be reduced substantially. Moreover, online shortest path query answering can be achieved using the novel compact BFS-trees.
Session
EDBT Research Session 14: Graph Techniques (Wednesday, March 25, 16:00—17:30)