Answering reachability queries on large directed graphs
Introducing a new data structure using bit vector compression
Sebastiaan J. van Schaik
Utrecht University / University of Oxford
Abstract
Answering reachability queries on graphs has been subject of extensive research for the last couple
of decades. Reachability data structures and algorithms provide an answer to probably one of the
easiest sounding questions in graph theory: can some vertex j be reached from another vertex i
along edges in the graph? Such queries can be answered in many different ways, for example by
using data structures representing the transitive closure of a graph.
Starting in the 1950’s, computer scientists and mathematicians have proposed multiple ways to
process a graph, extract reachability information and represent the transitive closure. Data sources
– and the graphs representing them – are vastly growing, forcing researchers to look for new ways
to efficiently represent a transitive closure, which grows quadratically in the number of vertices of a
graph. Additionally, the amount of time required to process a graph and build a transitive closure
data structure should be limited, as well as the amount of time required to answer reachability
queries using the data structure.
This thesis provides an introduction to transitive closure computation and proposes to use the
concept of bit vector compression to reduce the amount of memory required to represent a transitive
closure. A new data structure (based on bit vector compression) is presented, together with both
a theoretical and experimental analysis to compare its performance – in terms of memory usage,
construction time and query response time – to data structures presented in publications at major
conferences.
Although data structures described in recent publications are supported by a very sound the-
oretical foundation, it turns out that in practice more trivial existing approaches to compression
of transitive closure data structures often provide similar or even better performance. The newly
designed compression scheme often works faster (in terms of both construction time and query time)
and has a smaller memory footprint in virtually all cases.
