hide
Free keywords:
-
Abstract:
In this paper, we propose a scalable and highly efficient index structure for
the reachability problem over graphs. We build on the well-known node interval
labeling scheme where the set of vertices reachable from a particular node is
compactly encoded as a collection of node identifier ranges. We impose an
explicit bound on the size of the index and flexibly assign approximate
reachability ranges to nodes of the graph such that the number of index probes
to answer a query is minimized. The resulting tunable index structure generates
a better range labeling if the space budget is increased, thus providing a
direct control over the trade off between index size and the query processing
performance. By using a fast recursive querying method in conjunction with our
index structure, we show that web-scale graphs comprising hundreds of millions
of nodes and billions of edges can be efficiently processed such that the
resulting size-constrained index allows answering reachability queries in the
order of a few microseconds, using an off-the-shelf computer. Our claims are
supported by an extensive set of experimental results using a multitude of
benchmark and real-world web-scale graph datasets.
