Ferrari Reachability Index

The Ferrari Reachability Index is a main-memory index structure for rapid processing of reachability queries over massive graphs.

Introduction

A reachability query for a pair of vertices (u,v) returns a positive answer if the graph under consideration contains a directed path starting at vertex u and ending at vertex v, and a negative answer otherwise.

References

1. Stephan Seufert, Avishek Anand, Srikanta J. Bedathur, and Gerhard Weikum. FERRARI: Flexible and Efficient Reachability Range Assignment for Graph Indexing. Proceedings of the 29th IEEE International Conference on Data Engineering (ICDE'13), Brisbane, Australia. IEEE, 2013.
2. Stephan Seufert, Avishek Anand, Srikanta J. Bedathur, and Gerhard Weikum. High-Performance Reachability Query Processing under Index Size Restrictions. Computing Research Repository (CoRR), 2012 (arXiv:1211.3375 [cs.DB]). 2012.

License

Ferrari Reachability Index by Stephan Seufert is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.