General spanning trees and reachability query evaluation

ABSTRACT

Graph reachability is fundamental to a wide range of applications, including CAD/CAM, CASE, office systems, software management, as well as geographical navigation and internet routing. Many applications involve huge graphs and requires fast answering of reachability queries. Several reachability labeling methods have been proposed for this purpose. They assign labels to the nodes, such that the reachability between any two nodes can be determined using their labels only. In this paper, we propose a new data structure, called a general spanning tree of a directed acyclic graph (DAG) to minimize label space. Different from a traditional spanning tree, an edge in a general spanning tree T of a DAG G may corresponds to a path in G. That is, for each edge u → v in T, we have a path from u to v in G. An algorithm is discussed to find such a tree with the least number of leaf nodes in O(bn √b) time, where n is the number of the nodes of G, and b is the number of the leaf nodes of T. It can be proven that b equals 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. Based on T, we are able to reduce the label space to O(bn) with O(logb) reachability query time. Our method can also be extended for graphs containing cycles.

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: Armen S. Asratian , Tristan M. J. Denley , Roland Häggkvist, Bipartite graphs and their applications, Cambridge University Press, New York, NY, 1998
• 3: 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.
• 4: Y. Chen, Graph Decomposition and Recursive Closures, in Proc. CaiSE 2003 Forum at 15th Conf. on Advanced Information Systems Engineering, June 2003, Klagenfurt/Velden, Austria, pp. 5--8.
• 5: Yangjun Chen , Yibin Chen, An Efficient Algorithm for Answering Graph Reachability Queries, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.893-902, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497498]
• 6: 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.
• 7: Vassilis Christophides , Dimitris Plexousakis , Michel Scholl , Sotirios Tourtounis, On labeling schemes for the semantic web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775230]
• 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: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 11: T. H. Corman, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd. ed., McGraw-Hill Book Company, Boston, 2007.
• 12: R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. 51 (1950), pp. 161--166.
• 13: E. A. Dinic, Algorithm for solution of a problem of maximum flow in a network with power estimation, Soviet Mathematics Doklady, 11(5):1277--1280, 1970.
• 14: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 15: J. E. Hopcroft, and R. M. Karp, An n2.5 algorithm for maximum matching in bipartite graphs, SIAM J. Comput. 2(1973), 225--231.
• 16: 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]
• 17: A. V. Karzanov, Determining the Maximal Flow in a Network by the Method of Preflow, Soviet Math. Dokl., Vol. 15, 1974, pp. 434--437.
• 18: 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
• 19: 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
• 20: 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]
• 21: E. L. Lawler, Combinatorial Optimization and Matroids, Holt, Rinehart, and Winston, New York (1976).
• 22: R. Schenkel, A. Theobald, and G. Weikum, HOPI: an efficient connection index for complex XML document collections, in Proc. EDBT, 2004.
• 23: 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]
• 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: D. West, Parameters of partial orders and graphs: packing, covering and representation, in: I. Rival (ed.), Graphs and Orders, Dordrecht-Reidel, 1985, pp. 267--350.
• 30: 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
• 31: 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

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Design