Output details

A memory efficient reachability data structure through bit vector compression

<12>

Compactly representing the transitive closure of a graph, while still allowing fast membership tests, is one of the principle challenges for efficiently answering reachability queries. In this paper we propose a novel form of bit-vector compression, adapting the well-known scheme of word-aligned hybrid compression to work more efficiently by introducing word partitions. We prove that the resulting scheme leads to a more compact data structure than its closest competitor, namely interval lists, confirm this in practice via an extensive and detailed empirical evaluation, and demonstrate that the new technique can handle much larger graphs than alternative algorithms.