Accelerating Reachability Query Processing Based on DAG Reduction
Publication in refereed journal


Times Cited
Altmetrics Information
.

Other information
AbstractAnswering reachability queries is one of the fundamental graph operations. The existing approaches build indexes and answer reachability queries on a directed acyclic graph (DAG) G, which is constructed by coalescing each strongly connected component of the given directed graph G into a node of G. Considering that G can still be large to be processed efficiently, there are studies to further reduce G to a smaller graph. However, these approaches suffer from either inefficiency in answering reachability queries, or cannot scale to large graphs. In this paper, we study DAG reduction to accelerate reachability query processing, which reduces the size of G by computing transitive reduction (TR) followed by computing equivalence reduction (ER). For TR, we propose a bottom-up algorithm, namely buTR, which removes from G all redundant edges to get the unique smallest DAG G(t) satisfying that Gt has the same transitive closure as that of G. For ER, we propose a divide-and-conquer algorithm, namely linear-ER. Given the result Gt of TR, linear-ER gets a smaller DAG G(epsilon) in linear time based on equivalence relationship between nodes in G. Our DAG reduction approaches (TR and ER) significantly improve the cost of time and space and can be scaled to large graphs. Based on the result of DAG reduction, we further propose a graph decomposition-based algorithm to efficiently answer reachability queries. We confirm the efficiency of our approaches by extensive experimental studies for TR, ER, and reachability query processing using 20 real datasets. The complete source code is available for download at https://pan.baidu.com/s/lskHBXXN.
All Author(s) ListZhou JF, Yu JX, Li N, Wei H, Chen ZY, Tang X
Journal nameVLDB Journal
Year2018
Month4
Volume Number27
Issue Number2
PublisherSPRINGER
Pages271 - 296
ISSN1066-8888
eISSN0949-877X
LanguagesEnglish-United Kingdom
KeywordsReachability query processing,Transitive reduction,Equivalence reduction
Web of Science Subject CategoriesComputer Science, Hardware & Architecture;Computer Science, Information Systems;Computer Science

Last updated on 2020-27-03 at 04:25