File(s) under permanent embargo
Optimizing streaming graph partitioning via a heuristic greedy method and caching strategy
journal contribution
posted on 2023-05-20, 02:47 authored by Li, Q, Zhong, J, Cao, Z, Li, XGraph 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.
History
Publication title
Optimization Methods and SoftwarePagination
1-16ISSN
1055-6788Department/School
School of Information and Communication TechnologyPublisher
Taylor & Francis LtdPlace of publication
4 Park Square, Milton Park, Abingdon, England, Oxon, Ox14 4RnRights statement
Copyright 2019 Informa UK Limited, trading as Taylor & Francis GroupRepository Status
- Restricted