Paper Info
Title
GRAPHITE: An Extensible Graph Traversal Framework for Relational Database Management Systems.
Abstract
Graph traversals are a basic but fundamental ingredient for a variety of graph algorithms and graph-oriented queries. To achieve the best possible query performance, they need to be implemented at the core of a database management system that aims at storing, manipulating, and querying graph data. Increasingly, modern business applications demand native graph query and processing capabilities for enterprise-critical operations on data stored in relational database management systems. In this paper we propose an extensible graph traversal framework (GRAPHITE) as a central graph processing component on a common storage engine inside a relational database management system. We study the influence of the graph topology on the execution time of graph traversals and derive two traversal algorithm implementations specialized for different graph topologies and traversal queries. We conduct extensive experiments on GRAPHITE for a large variety of real-world graph data sets and input configurations. Our experiments show that the proposed traversal algorithms differ by up to two orders of magnitude for different input configurations and therefore demonstrate the need for a versatile framework to efficiently process graph traversals on a wide range of different graph topologies and types of queries. Finally, we highlight that the query performance of our traversal implementations is competitive with those of two native graph database management systems.
Year
DOI
Venue
2014
10.1145/2791347.2791383
Proceedings of the 27th International Conference on Scientific and Statistical Database Management
Keywords
Field
DocType
graph database
Data mining,Process graph,Computer science,Theoretical computer science,Distributed computing,Graph database,Graph traversal,Wait-for graph,Graph rewriting,Clique-width,Topological graph theory,Graph (abstract data type),Database
Journal
Volume
Citations 
PageRank 
abs/1412.6477
11
0.58
References 
Authors
23
3
Name
Order
Citations
PageRank
Marcus Paradies18210.36
Wolfgang Lehner22243294.69
Christof Bornhövd363042.58