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.
2.1 Graphs: Notation and Definitions
3 Working with Graphs in Main Memory
3.1.2 Compressed Storage Format
4 Working with Graphs in a Relational Database
4.1.2 Relational Adjacency Matrix
4.2.1 Breadth-First with Joins
4.2.2 Breadth-First with Recursive CTEs
4.2.3 Depth-First with PL/pgSQL
4.2.4 Depth-First with CONNECT BY
5 A Storage Manager for Graph Data
5.2 Storing Vertices and Edges
6.2 Memory and Graph Representation
8 First Experiments with G-Store