Graph Partitioning

The amount and connectivity of stored data increases every year.

Graph databases excel at storing and processing such connected data - such as that used by social networks - but they need to be partitioned for large datasets.

Partitioning leads to interdependencies between servers, increasing latency and network traffic. Moreover, with the ever increasing volume of social data, scalability of conventional methods such as full replication and disjoint partitioning of databases becomes challenging.

To address this problem, we investigate different methods of efficiently partitioning graph databases and distributing them on multiple machines, including various combinations of: incremental partitioning at runtime on dynamic graphs, partial replication techniques, and distributed diffusive clustering algorithms.