TY - GEN
T1 - IOGP
AU - Dai, Dong
AU - Zhang, Wei
AU - Chen, Yong
N1 - Funding Information:
We are thankful to the anonymous reviewers for their valuable feedback and our shepherd, Dr. Jay Lofstead, for his detailed and valuable suggestions that improved this paper significantly. This research is supported in part by the National Science Foundation under CNS-1162488, CNS-1338078, IIP-1362134, and CCF-1409946.
Publisher Copyright:
© 2017 Association for Computing Machinery.
PY - 2017/6/26
Y1 - 2017/6/26
N2 - 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.
AB - 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.
KW - Graph Database
KW - Graph Partitioning
KW - OLTP
UR - http://www.scopus.com/inward/record.url?scp=85025812410&partnerID=8YFLogxK
U2 - 10.1145/3078597.3078606
DO - 10.1145/3078597.3078606
M3 - Conference contribution
AN - SCOPUS:85025812410
T3 - HPDC 2017 - Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing
SP - 219
EP - 229
BT - HPDC 2017 - Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing
PB - Association for Computing Machinery, Inc
Y2 - 26 June 2017 through 30 June 2017
ER -