Created from a masterís thesis supervised by Dan Olteanu and submitted to Oxford University Computing Laboratory in September 2010
Author: Robin Steinhaus
Note: These pages describe G-Store version 0.1. The changelog contains a summay of changes.
This thesis develops a storage manager for vertex-labeled graphs, called G-Store. G-Store exploits the structure of the graph to derive a data placement on disk that is optimized for access patterns found in graph queries. The placement strategy is based on a multilevel algorithm that partitions the graph into blocks and arranges these blocks on disk to minimize the distance on disk between adjacent vertices. G-Store has a built-in query engine that supports depth-first traversal, reachability testing, shortest path search, and shortest path tree search. Initial experiments show that G-Store is functional, is fast, and solves queries that traditional database management systems struggle with.
†††† 4.1.1† Edge List
†† 4.2† Queries