arrow
返回

HEPart: A balanced hypergraph partitioning algorithm for big data applications

delete2018-06-01
delete15
PRE
AI
W
Wenyin Yang
G
Guojun Wang *
K
Kim‐Kwang Raymond Choo
S
Shuhong Chen
DOI:10.1016/j.future.2018.01.009delete
delete原文链接
delete分享
delete收藏
摘要

摘要

En 中文
Minimizing the query cost among multi-hosts is important to data processing for big data applications. Hypergraph is good at modeling data and data relationships of complex networks, the typical big data applications, by representing multi-way relationships or interactions as hyperedges. Hypergraph partitioning (HP) helps to partition the query loads on several hosts, enabling the horizontal scaling of large-scale networks. Existing heuristic HP algorithms are generally vertex hypergraph partitioning, designed to minimize the number of cut hyperedges while satisfying the balance requirements of part weights regarding vertices. However, since workloads are mainly produced by group operations, minimizing query costs landing on hyperedges and balancing the workloads should be the objectives in horizontal scaling. We thus propose a heuristic hyperedge partitioning algorithm, HEPart. Specifically, HEPart directly partitions the hypergraph into K sub-hypergraphs with a minimum cutsize for vertices, while satisfying the balance constraint on hyperedge weights, based on the effective move of hyperedges. The I performance of HEPart is evaluated using several complex network datasets modeled by undirected hypergraphs, under different cutsize metrics. The partitioning quality of HEPart is then compared with alternative hyperedge partitioners and vertex hypergraph partitioning algorithms. The experimental findings demonstrate the utility of HEPart (e.g. low cut cost while keeping load balancing as required, especially over scale-free networks). (C) 2018 Elsevier B.V. All rights reserved.
Keyword:
Hypergraph partitioning
Hyperedge partitioning
Load balancing
Big data
AI总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

F
Future Generation Computer Systems-The International Journal of eScience
IF:
6.1
论文数:
6.9K
被引数:
2.8W

机构

U
university of texas system
学者数:
1.1K
论文数: 2.5K
被引数: 11.2W
广州大学 封面图
广州大学
学者数:
1.8K
论文数: 650
被引数: 9.6K
F
Foshan University
学者数:
761
论文数: 240
被引数: 3.5K
学者 查看更多机构
引用论文

引用论文

Activation of Hydrogen Peroxide by Polyoxometalates
err2008-01-01
err0
PREAI
errNoritaka Mizuno; Kazuya Yamaguchi; Keigo Kamata; Yoshinao Nakagawa
err分享
err收藏
err分享
err收藏
The Little Engine(s) That Could: Scaling Online Social Networks
err2012-08-01
err32
errOAAI
errPujol, Josep M.; Erramilli, Vijay; Siganos, Georgos; Yang, Xiaoyuan; Laoutaris, Nikolaos; Chhabra, Parminder; Rodriguez, Pablo
err分享
err收藏
Temporal Workload-Aware Replicated Partitioning for Social Networks
err2014-11-01
err22
errOAAI
errTurk, Ata; Selvitopi, R. Oguz; Ferhatosmanoglu, Hakan; Aykanat, Cevdet
err分享
err收藏
LED: A fast overlapping communities detection algorithm based on structural clustering
err2016-09-01
err87
errOAAI
errMa, Tinghuai; Wang, Yao; Tang, Meili; Cao, Jie; Tian, Yuan; Al-Dhelaan, Abdullah; Al-Rodhaan, Mznah
err分享
err收藏
学者 查看更多内容