DAG Reduction: Fast Answering Reachability Queries
Refereed conference paper presented and published in conference proceedings


Times Cited
Web of Science12WOS source URL (as at 16/01/2021) Click here for the latest count
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 ER, we propose a divide-and-conquer algorithm, namely linear-ER. Given the result Gt of TR, linear-ER gets a smaller DAG Gε 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. We confirm the efficiency of our approaches by extensive experimental studies for TR, ER, and reachability query processing using 20 real datasets.
All Author(s) ListJunfeng Zhou, Shijie Zhou, Jeffrey Xu Yu, Hao Wei, Ziyang Chen, Xian Tang
Name of ConferenceThe Annual ACM SIGMOD/ PODS Conference 2017
Start Date of Conference14/05/2017
End Date of Conference19/05/2017
Place of ConferenceChicago
Country/Region of ConferenceUnited States of America
Proceedings TitleProceedings of the 2017 ACM International Conference on Management of Data
Year2017
Pages375 - 390
ISBN978-1-4503-4197-4
LanguagesEnglish-United States

Last updated on 2021-17-01 at 00:13