Fast Reachability Queries Answering Based on $\mathsf{RCN}$RCN Reduction

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

Abstract

Answering reachability queries is one of the fundamental graph operations. One way to make acceleration is directly building index on the input graph. Considering that the size of the input graph has a great impact on the query performance, the other way is reducing the size of the input graph, such that the given queries can be answered over a smaller graph. Although the input graph can be reduced significantly in some cases by existing approaches, a smaller reduced graph does not always mean a positive effect on the query performance. In this paper, we study graph reduction to accelerate reachability queries answering. We propose a novel graph reduction approach, namely $\mathsf{RCN}$ reduction, to reduce the input graph $G$ with $|V|$ nodes into a smaller one $G^{r}$ with $|V^r|$ nodes. Assume that the probability of a node of $G$ to be a query node is $1/|V|$, we show that based on our approach, the lower bound probability that a query $q$ can be answered in constant time is $1-(\frac{|V^r|}{|V|})^2$, denoting that the probability that $q$ needs to be answered over the reduced graph is $(\frac{|V^r|}{|V|})^2$, which means the smaller the reduced graph, the larger the probability that $q$ can be answered in constant time. We show the difficulties of $\mathsf{RCN}$ reduction and propose efficient algorithms to improve the reduction ratio. Based on the result of $\mathsf{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{zhou2023fast,
  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 $\textbackslash\{\}mathsf\{RCN\}$RCN Reduction}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  url = {https://openreview.net/forum?id=pI5Tm8jYNC},
}

Loading related content...

Figure