skip to main content
10.1145/1370256.1370293acmotherconferencesArticle/Chapter ViewAbstractPublication PagesuccsConference Proceedingsconference-collections
research-article

A new method for generating compressed representation of transitive closure

Published: 12 May 2008 Publication History

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(n2) 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(n1.5). Our method is suitable for both acyclic and cyclic graphs.

References

[1]
R. Agrawa, A. Borgida and H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, in: Proc. SIGMOD, pp. 253--262, 1989.
[2]
H. Alt, N. Blum, K. Mehlhorn, and M. Paul, Computing a maximum cardinality matching in a bipartite graph in time O(n 1.5 √e/(log n), Information Processing Letters, 37(1991), 237--240.
[3]
A. S. Asratian, T. Denley, and R. Haggkvist, Bipartite Graphs and their Applications, Cambridge University, 1998.
[4]
J. Banerjee, W. Kim, S. Kim and J. F. Garza, "Clustering a DAG for CAD Databases," IEEE Trans. on Knowledge and Data Engineering, Vol. 14, No. 11, Nov. 1988, pp. 1684--1699.
[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]
M. Carey et al., "An Incremental Join Attachment for Starburst," in: Proc. 16th VLDB Conf., Brisbane, Australia, 1990, pp. 662--673.
[7]
Y. Chen, "On the Graph Traversal and Linear Binary-chain Programs," IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 3, May 2003, pp. 573--596.
[8]
N. H. Cohen, "Type-extension tests can be performed in constant time," ACM Transactions on Programming Languages and Systems, 13:626--629, 1991.
[9]
E. Cohen, E. Halperin, H. Kaplan, and U. Zwick, Reachability and distance queries via 2-hop labels, SIAM J. Comput, Vol. 32, No. 5, pp. 1338--1355, 2003.
[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 et al., "A DBMS Prototype to Support Extended NF2 Relations: An Integrated View on Flat Tables and Hierarchies," Proc. ACM SIGMOD Conf., Washington D.C., 1986, pp. 356--367.
[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 Trans. Database Systems, Vol. 15, No. 4, 1990, pp. 558--598.
[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]
T. Keller, G. Graefe and D. Maier, "Efficient Assembly of Complex Objects," Proc. ACM SIGMOD Conf., Denver, Colo., 1991, pp. 148--157.
[17]
W. Kim, "Object-Oriented Database Systems: Promises, Reality, and Future," Proc. 19th VLDB conf., Dublin, Ireland, 1993, pp. 676--687.
[18]
H. A. Kuno and E. A. Rundensteiner, "Incremental Maintenance of Materialized Object-Oriented Views in MultiView: Strategies and Performance Evaluation," IEEE Transactions on Knowledge and Data Engineering, Vol. 10. No. 5, 1998, pp. 768--792.
[19]
E. L. Lawler, Combinatorial Optimization and Matroids, Holt, Rinehart, and Winston, New York (1976).
[20]
M. Stonebraker, L. Rowe and M. Hirohama, "The Implementation of POSTGRES," IEEE Trans. Knowledge and Data Eng., Vol. 2, no. 1, 1990, pp. 125--142.
[21]
R. Schenkel, A. Theobald, and G. Weikum, HOPI: an efficient connection index for complex XML document collections, in Proc. EDBT, 2004.
[22]
R. Schenkel, A. Theobald, and G. Weikum, Efficient creation and incrementation maintenance of HOPI index for complex xml document collection, in Proc. ICDE, 2006.
[23]
L. D. Shapiro, "Join Processing in Database Systems with Large Main Memories," ACM Trans. Database Systems, Vol. 11, no. 3, 1986, pp. 239--264.
[24]
R. Tarjan, Depth-first Search and Linear Graph Algorithms, SIAM J. Compt. Vol. 1. No. 2. June 1972, pp. 146--140.
[25]
J. Teuhola, "Path Signatures: A Way to Speed up Recursion in Relational Databases," IEEE Trans. on Knowledge and Data Engineering, Vol. 8, No. 3, June 1996, pp. 446--454.
[26]
H. S. Warren, "A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations," Commun. ACM 18, 4 (April 1975), 218--220.
[27]
H. Wang, H. He, J. Yang, P. S. Yu, and J. X. Yu, Dual Labeling: Answering Graph Reachability Queries in Constant time, in Proc. of Int. Conf. on Data Engineering, Atlanta, USA, April - 8 2006.
[28]
S. Warshall, "A Theorem on Boolean Matrices," JACM, 9. 1(Jan. 1962), 11--12.
[29]
C. Zhang, J. Naughton, D. DeWitt, Q. Luo and G. Lohman, "On Supporting Containment Queries in Relational Database Management Systems, in Proc. of ACM SIGMOD Intl. Conf. on Management of Data, California, USA, 2001.
[30]
Y. Zibin and J. Gil, "Efficient Subtyping Tests with PQ-Encoding," Proc. of the 2001 ACM SIGPLAN Conf. on Object-Oriented Programming Systems, Languages and Application, Florida, October 14--18, 2001, pp. 96--107.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences
C3S2E '08: Proceedings of the 2008 C3S2E conference
May 2008
240 pages
ISBN:9781605581019
DOI:10.1145/1370256
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

  • BytePress
  • Concordia University: Concordia University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 May 2008

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

C3S2E '08
Sponsor:
  • Concordia University

Acceptance Rates

Overall Acceptance Rate 12 of 42 submissions, 29%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 115
    Total Downloads
  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 12 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media