eCite Digital Repository

Optimizing streaming graph partitioning via a heuristic greedy method and caching strategy

Citation

Li, Q and Zhong, J and Cao, Z and Li, X, Optimizing streaming graph partitioning via a heuristic greedy method and caching strategy, Optimization Methods and Software pp. 1-16. ISSN 1055-6788 (2019) [Refereed Article]

Copyright Statement

Copyright 2019 Informa UK Limited, trading as Taylor & Francis Group

DOI: doi:10.1080/10556788.2018.1553971

Abstract

Graph partitioning is an important method for accelerating large distributed graph computation. Streaming graph partitioning is more efficient than offline partitioning, and it has been developed continuously in the application of graph partitioning in recent years. In this work, we first introduce a heuristic greedy streaming partitioning method and show that it outperforms the state-of-the-art streaming partitioning methods, leading to exact balance and fewer cut edges. Second, we propose a cache structure for streaming partitioning, called an adjacent edge structure, which can improve the partition efficiency several times on a single commodity type computer without affecting the partition quality. Regardless as to whether the memory capacity is limited (local cache) or not (global cache), our strategy can also improve the partition quality by restreaming partitioning. Taking linear weight greedy streaming algorithm as an example, the experimental results on 19 real-world graphs show that the average partitioning time of the new method is 4.9 times faster than that of the original method, which proves the effectiveness and superiority of the cache structure mentioned in this paper.

Item Details

Item Type:Refereed Article
Keywords:cache structure, streaming graph partitioning, parallel computing, complex networks, community detection, data mining
Research Division:Information and Computing Sciences
Research Group:Artificial Intelligence and Image Processing
Research Field:Pattern Recognition and Data Mining
Objective Division:Information and Communication Services
Objective Group:Computer Software and Services
Objective Field:Information Processing Services (incl. Data Entry and Capture)
UTAS Author:Cao, Z (Mr Zehong Cao)
ID Code:131923
Year Published:2019
Deposited By:Information and Communication Technology
Deposited On:2019-04-11
Last Modified:2019-05-14
Downloads:0

Repository Staff Only: item control page