Partitioning Graph Databases Via Access Patterns

Summary:

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 dis- tributed 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.

Özet:

Twitter, Facebook, Linkedin gibi büyük ölçekli sosyal ağların ortaya çıkmasıyla büyük verinin artan büyüme eğilimi daha da belirgin hale geldi. Bu durum, yoğun şekilde bağlı bu büyük verinin saklanmasına ek olarak etkili bir mekanizmayla işlen- mesi gereksinimini doğurdu. İlişkisel veri tabanı yönetimi sistemleri gibi geleneksel çözümlerin yetersiz kalması insanların graf veritabanlarına yönelmesine sebep oldu. Graf veritabanları, veri yapısı modellerinin grafları temel alması nedeniyle bağlı ver- iler için doğal bir çözüm olmaktadır. Milyarlarca düğüm ve ilişkiyi tek bir makinede işleyebilmelerine rağmen sosyal verinin artan büyüme hızı limitlerini zorlamaktadır. Bu çalışmada bir graf veri tabanı sisteminin işlem hacmini arttırabilmek için graf veri tabanlarının bölümlenmesini değerlendirmeyi amaçladık. Bu doğrultuda hem graf veri tabanını bölümlendiren hem de dağıtık bir graf veri tabanı sistemi sunan bir yapıyı tasarladık ve gerçekledik. Önceki çalışmalardan farklı olarak erişim örün- tülerine dayanan bir bölümlendirme üzerinde yoğunlaştık. Denemelerimiz esnasında erişim örüntülü bölümlendirme, sadece grafın yapısına dayanarak bölümlendirme ya- pan yöntemi geride bıraktı. Değerlendirmelerimiz için Erdös Projesi ve Pokec sosyal ağ verilerini kullandık.