AKIN: A streaming graph partitioning algorithm for distributed graph storage systems

Wei Zhang, Yong Chen, Dong Dai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Many graph-related applications face the challenge of managing excessive and ever-growing graph data in a distributed environment. Therefore, it is necessary to consider a graph partitioning algorithm to distribute graph data onto multiple machines as the data comes in. Balancing data distribution and minimizing edge-cut ratio are two basic pursuits of the graph partitioning problem. While achieving balanced partitions for streaming graphs is easy, existing graph partitioning algorithms either fail to work on streaming workloads, or leave edge-cut ratio to be further improved. Our research aims to provide a better solution that fits the need of streaming graph partitioning in a distributed system, which further reduces the edge-cut ratio while maintaining rough balance among all partitions. We exploit the similarity measure on the degree of vertices to gather structuralrelated vertices in the same partition as much as possible, this reduces the edge-cut ratio even further as compared to the state-of-the-art streaming graph partitioning algorithm-FENNEL. Our evaluation shows that our streaming graph partitioning algorithm is able to achieve better partitioning quality in terms of edge-cut ratio (up to 20% reduction as compared to FENNEL) while maintaining decent balance between all partitions, and such improvement applies to various real-life graphs.

Original languageEnglish
Title of host publicationProceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages183-192
Number of pages10
ISBN (Electronic)9781538658154
DOIs
StatePublished - Jul 13 2018
Event18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018 - Washington, United States
Duration: May 1 2018May 4 2018

Publication series

NameProceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018

Conference

Conference18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018
CountryUnited States
CityWashington
Period05/1/1805/4/18

Keywords

  • Distributed system
  • Graph database
  • Graph partitioning
  • Graph storage

Cite this

Zhang, W., Chen, Y., & Dai, D. (2018). AKIN: A streaming graph partitioning algorithm for distributed graph storage systems. In Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018 (pp. 183-192). (Proceedings - 18th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, CCGRID 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CCGRID.2018.00033