Data Management

3-HOP: A High-Compression Indexing Scheme for Reachability Query

Download Now Free registration required

Executive Summary

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, the authors propose a new 3-hop indexing scheme for directed graphs with higher density.

  • Format: PDF
  • Size: 602.8 KB