  Electronic data is growing at increasing rates, in both size and
connectivity: the increasing presence of, and interest in, relationships
between data. An example is the Twitter social network graph. Due to this
growth demand is increasing for technologies that can process such data.
Currently relational databases are the predominant technology, but they are
poorly suited to processing connected data as they are optimized for
index-intensive operations. Conversely, graph databases are optimized for graph
computation. They link records by direct references, avoiding index lookups,
and enabling retrieval of adjacent elements in constant time, regardless of
graph size. However, as data volume increases these databases outgrow the
resources of one computer and data partitioning becomes necessary. We evaluate
the viability of using graph partitioning algorithms to partition graph
databases. A prototype partitioned database was developed. Three partitioning
algorithms explored and one implemented. Three graph datasets were used: two
real and one synthetically generated. These were partitioned in various ways
and the impact on database performance measured. We defined one synthetic
access pattern per dataset and executed each on the partitioned datasets.
Evaluation took place in a simulation environment, ensuring repeatability and
allowing measurement of metrics like network traffic and load balance. Results
show that compared to random partitioning the partitioning algorithm reduced
traffic by 40-90%. Executing the algorithm intermittently during usage
maintained partition quality, while requiring only 1% the computation of
initial partitioning. Strong correlations were found between theoretic quality
metrics and generated network traffic under non-uniform access patterns.
