A new method for generating compressed representation of transitive closure

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 of G if (v, u) ∈ E* iff there is a path from v to u in G. If we store it as a matrix, O(n²) space is required, not suitable for large graphs. In this paper, we present a new method to reduce the space overhead to O(bn), where b is the G's width, defined to be the size of a largest node subset U of G such that for every pair of nodes u, v ∈ U, there does not exist a path from u to v or from v to u. With such a compressed data structure of transitive closure, the time for checking reachability (whether a node is reachable from another node through a path) is bounded by O(logb). In addition, this data structure can be generated in O(be') time, where e' is the size of a subset of E, which contains only those edges (u, v) such that there is no path of length ≥2 connecting u and v. We are able to show that the average value of e' is on the order of O(n^1.5). Our method is suitable for both acyclic and cyclic graphs.

REFERENCES

• 1: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 2: H. Alt , N. Blum , K. Mehlhorn , M. Paul, Computing a maximum cardinality matching in a bipartite graph in time On^1.5m/logn , Information Processing Letters, v.37 n.4, p.237-240, Feb. 28, 1991 [doi>10.1016/0020-0190(91)90195-N ]
• 3: Armen S. Asratian , Tristan M. J. Denley , Roland Häggkvist, Bipartite graphs and their applications, Cambridge University Press, New York, NY, 1998
• 4: J. Banerjee , W. Kim , S.-J. Kim , J. F. Garza, Clustering a DAG for CAD Databases, IEEE Transactions on Software Engineering, v.14 n.11, p.1684-1699, November 1988 [doi>10.1109/32.9055 ]
• 5: K. S. Booth and G. S. Leuker, "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms," J. Comput. Sys. Sci., 13(3):335--379, Dec. 1976.
• 6: Michael Carey , George Lapis , Eugene Shekita , Bruce Lindsay , John McPherson, An incremental join attachment for Starburst, Proceedings of the sixteenth international conference on Very large databases, p.662-673, September 1990, Brisbane, Australia
• 7: Yangjun Chen, On the Graph Traversal and Linear Binary-Chain Programs, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.573-596, March 2003 [doi>10.1109/TKDE.2003.1198392]
• 8: Norman H. Cohen, Type-extension type test can be performed in constant time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.626-629, Oct. 1991 [doi>10.1145/115372.115297]
• 9: Edith Cohen , Eran Halperin , Haim Kaplan , Uri Zwick, Reachability and Distance Queries via 2-Hop Labels, SIAM Journal on Computing, v.32 n.5, p.1338-1355, 2003 [doi>10.1137/S0097539702403098]
• 10: J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu, Fast computation of reachability labeling for large graphs, in Proc. EDBT, Munich, Germany, May 26--31, 2006.
• 11: P. Dadam , K. Kuespert , F. Andersen , H. Blanken , R. Erbe, A DBMS prototype to support extended NF2 relations: an integrated view on flat tables and hierarchies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.356-367, May 28-30, 1986, Washington, D.C., United States
• 12: R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. 51 (1950), pp. 161--166.
• 13: J. E. Hopcroft, and R. M. Karp, An n2.5 algorithm for maximum matching in bipartite graphs, SIAM J. Comput. 2(1973), 225--231.
• 14: H. V. Jagadish, A compression technique to materialize transitive closure, ACM Transactions on Database Systems (TODS), v.15 n.4, p.558-598, Dec. 1990 [doi>10.1145/99935.99944]
• 15: A. V. Karzanov, Determining the Maximal Flow in a Network by the Method of Preflow, Soviet Math. Dokl., Vol. 15, 1974, pp. 434--437.
• 16: Tom Keller , Goetz Graefe , David Maier, Efficient assembly for complex objects, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.148-157, May 29-31, 1991, Denver, Colorado, United States
• 17: Won Kim, Object-Oriented Database Systems: Promises, Reality, and Future, Proceedings of the 19th International Conference on Very Large Data Bases, p.676-687, August 24-27, 1993
• 18: Harumi A. Kuno , Elke A. Rundensteiner, Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.768-792, September 1998 [doi>10.1109/69.729731 ]
• 19: E. L. Lawler, Combinatorial Optimization and Matroids, Holt, Rinehart, and Winston, New York (1976).
• 20: M. Stonebraker , L. A. Rowe , M. Hirohama, The Implementation of POSTGRES, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.125-142, March 1990 [doi>10.1109/69.50912 ]
• 21: R. Schenkel, A. Theobald, and G. Weikum, HOPI: an efficient connection index for complex XML document collections, in Proc. EDBT, 2004.
• 22: Ralf Schenkel , Anja Theobald , Gerhard Weikum, Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections, Proceedings of the 21st International Conference on Data Engineering, p.360-371, April 05-08, 2005 [doi>10.1109/ICDE.2005.57]
• 23: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• 24: R. Tarjan, Depth-first Search and Linear Graph Algorithms, SIAM J. Compt. Vol. 1. No. 2. June 1972, pp. 146--140.
• 25: Jukka Teuhola, Path Signatures: A Way to Speed Up Recursion in Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.446-454, June 1996 [doi>10.1109/69.506711 ]
• 26: Henry S. Warren, Jr., A modification of Warshall's algorithm for the transitive closure of binary relations, Communications of the ACM, v.18 n.4, p.218-220, April 1975 [doi>10.1145/360715.360746]
• 27: Haixun Wang , Hao He2 , Jun Yang , Philip S. Yu , Jeffrey Xu Yu, Dual Labeling: Answering Graph Reachability Queries in Constant Time, Proceedings of the 22nd International Conference on Data Engineering, p.75, April 03-07, 2006 [doi>10.1109/ICDE.2006.53]
• 28: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
• 29: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States
• 30: Yoav Zibin , Joseph Yossi Gil, Efficient subtyping tests with PQ-encoding, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.96-107, October 14-18, 2001, Tampa Bay, FL, USA