Files and links (1)
CC BY V4.0, Open Access
Journal article
Modular Decomposition-Based Graph Compression for Fast Reachability Detection
Data science and engineering, Vol.4(3), pp.193-207
2019
Abstract
Fast reachability detection is one of the key problems in graph applications. Most of the existing works focus on creating an index and answering reachability based on that index. For these approaches, the index construction time and index size can become a concern for large graphs. More recently query-preserving graph compression has been proposed, and searching reachability over the compressed graph has been shown to be able to significantly improve query performance as well as reducing the index size. In this paper, we introduce a multilevel compression scheme for DAGs, which builds on existing compression schemes, but can further reduce the graph size for many real-world graphs. We propose an algorithm to answer reachability queries using the compressed graph. Extensive experiments with four existing state-of-the-art reachability algorithms and 12 real-world datasets demonstrate that our approach outperforms the existing methods. Experiments with synthetic datasets ensure the scalability of this approach. We also provide a discussion on possible compression for k-reachability.
Details
- Title
- Modular Decomposition-Based Graph Compression for Fast Reachability Detection
- Authors/Creators
- Shikha AnirbanJunhu Wang - Griffith Univ, Sch Informat & Commun Technol, Gold Coast, AustraliaMd. Saiful Islam - Griffith Univ, Sch Informat & Commun Technol, Gold Coast, Australia
- Publication Details
- Data science and engineering, Vol.4(3), pp.193-207
- Publisher
- Springer Nature
- Identifiers
- 991005638766607891
- Copyright
- © The Author(s) 2019
- Murdoch Affiliation
- School of Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
34 Record Views