Fast Reachability Queries Answering based on RCN Reduction
Lists
Only you see this
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...