English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

FERRARI: Flexible and Efficient Reachability Range Assignment for Graph Indexing

MPS-Authors
/persons/resource/persons45462

Seufert,  Stephan
Databases and Information Systems, MPI for Informatics, Max Planck Society;

/persons/resource/persons44012

Anand,  Avishek
Databases and Information Systems, MPI for Informatics, Max Planck Society;

/persons/resource/persons45720

Weikum,  Gerhard
Databases and Information Systems, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Seufert, S., Anand, A., Bedathur, S., & Weikum, G. (2013). FERRARI: Flexible and Efficient Reachability Range Assignment for Graph Indexing. In 29th IEEE International Conference on Data Engineering (pp. 1009-1020). Piscataway, NJ: IEEE. doi:10.1109/ICDE.2013.6544893.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0015-36CC-1
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 in practice, reachability queries can be answered in the order of microseconds on an off-the-shelf computer -- even for the case of massive-scale real world graphs. Our claims are supported by an extensive set of experimental results using a multitude of benchmark and real-world web-scale graph datasets.