.png){kind=icon}
返回
Reordering and Compression for Hypergraph Processing
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2024.3377915.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Hypergraphs are applicable to various domains such as social contagion, online groups, and protein structures due to their effective modeling of multivariate relationships. However, the increasing size of hypergraphs has led to high computation costs, necessitating efficient acceleration strategies. Existing approaches often require consideration of algorithm-specific issues, making them difficult to directly apply to arbitrary hypergraph processing tasks. In this paper, we propose a compression-array acceleration strategy involving hypergraph reordering to improve memory access efficiency, which can be applied to various hypergraph processing tasks without considering the algorithm itself. We introduce a new metric called closeness to optimize the ordering of vertices and hyperedges in the one-dimensional array representation. Moreover, we present an 1/2w-approximation algorithm to obtain the optimal ordering of vertices and hyperedges. We also develop an efficient update mechanism for dynamic hypergraphs. Our extensive experiments demonstrate significant improvements in hypergraph processing performance, reduced cache misses, and reduced memory footprint. Furthermore, our method can be integrated into existing hypergraph processing frameworks, such as Hygra, to enhance their performance.
Keyword:
Arrays
Measurement
Heuristic algorithms
Proteins
Partitioning algorithms
Optimization
Task analysis
Graph analytics
hypergraph
locality
reordering
optimization
期刊
IF:
3.8
论文数:
5.4K
被引数:
1.0W
机构
引用论文
Enhanced immunogenicity of a contraceptive vaccine using diverse synthetic carriers with permissible adjuvant.png)
Vaccine
VaccineIF0
PREAI
分享收藏
查看更多内容