Fast Reachability Queries Answering based on RCN Reduction

Junfeng Zhou, Jeffrey Xu Yu, Yaxian Qiu, Xian Tang, Ziyang Chen, Ming DuIEEE TKDE 2021 · DOI

Abstract

Answering reachability queries is a fundamental graph operation. Considering that the size of the input graph has a great impact on query performance, there are studies focusing on reducing the graph size, such that queries can be answered over a smaller graph. Although the input graph can be compressed significantly by existing approaches, a good compression ratio does not always mean a positive effect on query performance. In this paper, we study graph reduction to accelerate reachability queries answering. We propose a novel graph reduction approach, namely RCN reduction, to compress the input graph into a smaller one. Let a be the compression ratio of the number of nodes in the reduced graph over that of the input graph, we show that based on our approach, the lower bound probability that a query q can be answered in constant time is 1-a^2. We show the difficulties of RCN reduction and propose efficient algorithms to improve the compression ratio. Based on the result of RCN reduction, we further propose a novel labeling scheme to accelerate queries answering. We confirm the efficiency of our approach by extensive experimental results for graph reduction and reachability queries processing using 20 real datasets.
BibTeX
@article{zhou2021fast,
  author = {Junfeng Zhou and Jeffrey Xu Yu and Yaxian Qiu and Xian Tang and Ziyang Chen and Ming Du},
  title = {{Fast Reachability Queries Answering based on RCN Reduction}},
  journal = {IEEE Transactions on Knowledge and Data Engineering},
  year = {2021},
  doi = {10.1109/tkde.2021.3108433},
}

Loading related content...

Figure