Answering reachability queries on large directed graphs
Sebastiaan J. van Schaik · 2010
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 theoretical 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. “Life is all about timing... the unreachable becomes reachable, the unavailable become available, the unattainable... attainable. Have the patience, wait it out. It is all about timing.” — Stacey Charter