Decomposing DAGs into spanning trees: A new way to compress transitive closures
Authors:
- 1 April 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 1007-1018
Abstract
Let G(V, E) be a digraph (directed graph) with n nodes and e edges. Digraph G* = (V, E*) is the reflexive, transitive closure if (v, u) ∈ E* iff there is a path from v to u in G. Efficient storage of G* is important for supporting reachability queries which are not only common on graph databases, but also serve as fundamental operations used in many graph algorithms. A lot of strategies have been suggested based on the graph labeling, by which each node is assigned with certain labels such that the reachability of any two nodes through a path can be determined by their labels. Among them are interval labelling, chain decomposition, and 2-hop labeling. However, due to the very large size of many real world graphs, the computational cost and size of labels using existing methods would prove too expensive to be practical. In this paper, we propose a new approach to decompose a graph into a series of spanning trees which may share common edges, to transform a reachability query over a graph into a set of queries over trees. We demonstrate both analytically and empirically the efficiency and effectiveness of our method.Keywords
This publication has 24 references indexed in Scilit:
- On the transitive closure representation and adjustable compression2006
- Compact oracles for reachability and approximate distances in planar digraphsJournal of the ACM, 2004
- A new algorithm for computing transitive closures2004
- On the graph traversal and linear binary-chain programsIEEE Transactions on Knowledge and Data Engineering, 2003
- Efficient subtyping tests with PQ-encoding2001
- Magic sets and stratified databasesInternational Journal of Intelligent Systems, 1997
- On the bottom—up evaluation of recursive queriesInternational Journal of Intelligent Systems, 1996
- Path signatures: a way to speed up recursion in relational databasesIEEE Transactions on Knowledge and Data Engineering, 1996
- Finding optimum branchingsNetworks, 1977
- A modification of Warshall's algorithm for the transitive closure of binary relationsCommunications of the ACM, 1975