Archive for the ‘G-Store (graphs)’ Category

G-Store: A Storage Manager for Graph Data

Friday, November 2nd, 2012

G-Store: A Storage Manager for Graph Data by Dan Olteanu, Robin Steinhaus, Tim Furche and Emanuel Ferm.

From the webpage:

Many modern applications are based on graph data. Social networks, for instance, are based on graphs that describe relationships among people. Paths of disease outbreaks form a graph, as do airline routes, and citations among academic papers. These graphs often contain a massive amount of data.

Relational databases are today’s system of choice for storing and querying large amounts of data. Their use has been backed up by decades of research and commercially successful database management systems such as Oracle, IBM DB2, and PostgreSQL. Relational databases are extremely fast in finding, filtering, inserting, deleting, and updating information in a database table. Joining information from several tables, on the other hand, often takes orders of magnitude longer.

From a theoretical point of view, the relational database model is not a good fit for representing highly interconnected data. Regardless, as businesses and processes around the world get more interconnected, relational databases are increasingly used for storing such data. Perhaps one reason is the lack of a suitable, stable, and well-supported alternative.

G-Store is a prototype of a storage manager for large vertex-labeled graphs. 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 pages and arranges these pages 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.

Reported to be approximately 12,000 lines of C/C++ code and runs on Windows.

I have not installed Windows on my Ubuntu box so I haven’t tried the software.

Interested if you do, what comments you have. (Particularly on the query language.) Thanks!