3-HOP: a high-compression indexing scheme for reachability query

ABSTRACT

Reachability queries on large directed graphs have attracted much attention recently. The existing work either uses spanning structures, such as chains or trees, to compress the complete transitive closure, or utilizes the 2-hop strategy to describe the reachability. Almost all of these approaches work well for very sparse graphs. However, the challenging problem is that as the ratio of the number of edges to the number of vertices increases, the size of the compressed transitive closure grows very large. In this paper, we propose a new 3-hop indexing scheme for directed graphs with higher density. The basic idea of 3-hop indexing is to use chain structures in combination with hops to minimize the number of structures that must be indexed. Technically, our goal is to find a 3-hop scheme over dense DAGs (directed acyclic graphs) with minimum index size. We develop an efficient algorithm to discover a transitive closure contour, which yields near optimal index size. Empirical studies show that our 3-hop scheme has much smaller index size than state-of-the-art reachability query schemes such as 2-hop and path-tree when DAGs are not very sparse, while our query time is close to path-tree, which is considered to be one of the best reachability query schemes.

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: Renzo Angles , Claudio Gutierrez, Survey of graph database models, ACM Computing Surveys (CSUR), v.40 n.1, p.1-39, February 2008 [doi>10.1145/1322432.1322433]
• 3: M.de Berg, M.van Kreveld, M.Overmars, and O.Schwarzkopf. Computational Geometry. Springer, 2000.
• 4: Li Chen , Amarnath Gupta , M. Erdem Kurul, Stack-based algorithms for pattern matching on DAGs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 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: Jiefeng Cheng, Jeffrey Xu Yu, Xuemin Lin, Haixun Wang, and Philip S. Yu. Fast computation of reachability labeling for large graphs. In EDBT, pages 961--979, 2006.
• 7: Jiefeng Cheng , Jeffrey Xu Yu , Xuemin Lin , Haixun Wang , Philip S. Yu, Fast computing reachability labelings for large graphs with high compression rate, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353370]
• 8: V. Chvál. A greedy heuristic for the set-covering problem. Math. Oper. Res, 4:233--235, 1979.
• 9: Edith Cohen , Eran Halperin , Haim Kaplan , Uri Zwick, Reachability and distance queries via 2-hop labels, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.937-946, January 06-08, 2002, San Francisco, California
• 10: G. Gallo , M. D. Grigoriadis , R. E. Tarjan, A fast parametric maximum flow algorithm and applications, SIAM Journal on Computing, v.18 n.1, p.30-55, Feb. 1989 [doi>10.1137/0218003]
• 11: 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]
• 12: Ruoming Jin , Yang Xiang , Ning Ruan , Haixun Wang, Efficiently answering reachability queries on very large directed graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376677]
• 13: Richard Johnsonbaugh , Martin Kalin, A graph generation software package, Proceedings of the twenty-second SIGCSE technical symposium on Computer science education, p.151-154, March 07-08, 1991, San Antonio, Texas, United States
• 14: Guy Kortsarz , David Peleg, Generating Sparse 2-spanners, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.73-82, July 08-10, 1992
• 15: R. Schenkel, A. Theobald, and G. Weikum. HOPI: An efficient connection index for complex XML document collections. In EDBT, 2004.
• 16: K. Simon, An improved algorithm for transitive closure on acyclic digraphs, Theoretical Computer Science, v.58 n.1-3, p.325-346, June 1988 [doi>10.1016/0304-3975(88)90032-1]
• 17: Yuanyuan Tian , Richard A. Hankins , Jignesh M. Patel, Efficient aggregation for graph summarization, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376675]
• 18: Silke Trißl , Ulf Leser, Fast and practical indexing and querying of very large graphs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247573]
• 19: 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]
• 20: Xifeng Yan , Philip S. Yu , Jiawei Han, Substructure similarity search in graph databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066244]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Performance

Keywords:
2-hop, 3-hop, graph indexing, path-tree, reachability queries, transitive closure