Partitioning graph databases via access patterns

Abstract

With the emergence of large scale social networks such as Twitter, Facebook, Linkedin and Google+ the growing trend of big data become much clear. In addition to storing this highly connected big data, an efficient mechanism for processing this data is also needed. The inadequacy of traditional solutions such as relational database management systems for processing highly connected data caused the people head toward graph databases. Graph databases are the natural fit for connected data with their underlying data structure model depending on graphs. They are able to handle up to billions of nodes and relationships on a single machine but the high growing rate of social data pushes their limits. In this study, we evaluate partitioning graph databases in order to increase throughput of a graph database system. For this purpose we designed and implemented a framework that both partitions a graph database and provides a fully functional distributed graph database system. Comparing to previous studies we have concentrated on access pattern based partitioning. Within our experiments access pattern based partitioning outperformed unbiased partitioning that only depends on static structure of the graph. We have evaluated our results on real world datasets of Erdös Webgraph Project and Pokec social network.