eCite Digital Repository

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


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


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:Computer vision and multimedia computation
Research Field:Pattern recognition
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Cao, Z (Dr Zehong Cao)
ID Code:131923
Year Published:2019
Web of Science® Times Cited:3
Deposited By:Information and Communication Technology
Deposited On:2019-04-11
Last Modified:2020-05-18

Repository Staff Only: item control page