IOGP: An incremental online graph partitioning algorithm for distributed graph databases

Dong Dai, Wei Zhang, Yong Chen

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

8 Scopus citations

Abstract

Graphs have become increasingly important in many applications and domains such as querying relationships in social networks or managing rich metadata generated in scientific computing. Many of these use cases require high-performance distributed graph databases for serving continuous updates from clients and, at the same time, answering complex queries regarding the current graph. These operations in graph databases, also referred to as online transaction processing (OLTP) operations, have specific design and implementation requirements for graph partitioning algorithms. In this research, we argue it is necessary to consider the connectivity and the vertex degree changes during graph partitioning. Based on this idea, we designed an Incremental Online Graph Partitioning (IOGP) algorithm that responds accordingly to the incremental changes of vertex degree. IOGP helps achieve better locality, generate balanced partitions, and increase the parallelism for accessing high-degree vertices of the graph. Over both real-world and synthetic graphs, IOGP demonstrates as much as 2x better query performance with a less than 10% overhead when compared against state-of-the-art graph partitioning algorithms.

Original languageEnglish
Title of host publicationHPDC 2017 - Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing
PublisherAssociation for Computing Machinery, Inc
Pages219-229
Number of pages11
ISBN (Electronic)9781450346993
DOIs
StatePublished - Jun 26 2017
Event26th ACM International Symposium on High-Performance Parallel and Distributed Computing, HPDC 2017 - Washington, United States
Duration: Jun 26 2017Jun 30 2017

Publication series

NameHPDC 2017 - Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing

Conference

Conference26th ACM International Symposium on High-Performance Parallel and Distributed Computing, HPDC 2017
CountryUnited States
CityWashington
Period06/26/1706/30/17

Keywords

  • Graph Database
  • Graph Partitioning
  • OLTP

Fingerprint Dive into the research topics of 'IOGP: An incremental online graph partitioning algorithm for distributed graph databases'. Together they form a unique fingerprint.

  • Cite this

    Dai, D., Zhang, W., & Chen, Y. (2017). IOGP: An incremental online graph partitioning algorithm for distributed graph databases. In HPDC 2017 - Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing (pp. 219-229). (HPDC 2017 - Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing). Association for Computing Machinery, Inc. https://doi.org/10.1145/3078597.3078606