Fast Reachability Queries Answering Based on RCN Reduction
Publication in refereed journal

Altmetrics Information

Other information
AbstractAnswering 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 RCN reduction, to reduce the input graph G with |V| nodes into a smaller one Gr with |Vr| 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−(|Vr||V|)2 , denoting that the probability that q needs to be answered over the reduced graph is (|Vr||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 RCN reduction and propose efficient algorithms to improve the reduction 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.
All Author(s) ListJunfeng Zhou, Jeffrey Xu Yu, Yaxian Qiu, Xian Tang, Ziyang Chen, Ming Du
Journal nameIEEE Transactions on Knowledge and Data Engineering
Volume Number35
Issue Number3
Pages2590 - 2609
LanguagesEnglish-United States
KeywordsIndexes, Erbium, Testing, Time complexity, Query processing, Optimization, Buildings, Reachability Queries, Time Constant, Result Of Reduction, Reduction Ratio, Graph Size, Input Graph, Small Graphs, Query Performance, Time Complexity, Root Node, Linear Time, Leaf Node, Directed Acyclic Graph, Rank Value, Polynomial-time Algorithm, Original Graph, Large Graphs, Query Results, Processing Nodes, Spanning Tree, Query Time, Large Nodes, Cost Line, Sparse Graph, Efficient Expansion, Graph Traversal, Citation Network, Exact Intervals, Directed Graph, Space Complexity, Graph data management, reachability queries processing, graph reduction

Last updated on 2024-24-01 at 12:30