Fast and Practical Indexing and Querying of Very Large Graphs

摘要

Many applications work with graph-structured data. As graphs grow in size, indexing becomes essential to ensure sucient query performance. We present the GRIPP index structure (Graph Indexing based on Pre- and Postorder numbering) for answering reachability queries in graphs. GRIPP requires only linear time and space. Using GRIPP, we can answer reachability queries on graphs with 5 million nodes on average in less than 5 milliseconds, which is unrivaled by previous methods. We evaluate the performance and scalability of our approach on real and synthetic random and scale-free graphs and compare our approach to existing indexing schemes. GRIPP is implemented as stored procedure inside a relational database management system and can therefore very easily be integrated into existing graphoriented applications.