Utilizing Community Centers to Answer Reachability Queries for Large Graphs
Yifei Zhang, Guoren Wang, Changkuan Zhao, Ende Zhang · 2013
As a fundamental problem, reachability query has been always the research emphasis in many applications in the near 20 years. Especially with the coming of the big data era, its efficiency plays a critical role. Although there are many research results for this issue, they all reach a scalability bottleneck. In this paper, we propose an index structure utilizing community center, i.e. to select a group of vertices from the original graph and construct a subgraph. With this subgraph, we can answer reachability queries rapidly. The experimental result shows that our approach is superior to the-state-of-the-art algorithms including construction time, index size and query time.