Abstract: Reachability query is one of the fundamental problems of management of massive directed graphs. This paper considered reachabihty query under the context of dense graphs. We proposed a storage schema, called X-Hop, which compresses the storage of 2-Hop via a multipl}hop schema. By organizing center vertexes in a tree structure, X-Hop storage delivers efficient query process in addition to high compression ratio. Extensive experiments demonstrate the efficiency of our proposal.

Key words: X-Hop,Reachability query,2-Hop labeling,Transitive closure compression