.png){kind=icon}
返回
Revisiting Core Maintenance for Dynamic Hypergraphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2023.3236669.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Core maintenance for dynamic hypergraphs has been receiving an increasing attention. However, existing works mainly focus on the insertion/deletion of hyperedges. This article revisits the problem from the view of vertices change. We study core maintenance when the vertices are inserted/deleted into/from specific hyperedges in the hypergraph, which is a challenging task since the deletion of the vertex may increase the core numbers and the insertion of the vertex may decrease the core numbers. We discuss in detail the possible changes of core numbers in different situations. For the insertion/deletion of vertices contained by a single hyperedge, we design sequential algorithms to discover the vertices whose core numbers have changed. Compared with static recomputation (Leng et al. 2013) and LYCLC (Luo et al. 2021) algorithms, our sequential algorithms can accelerate more than 1,000x and 12x at most in the processing time, respectively. For the insertion/deletion of vertices contained by different hyperedges, we find that core numbers of all vertices change 1 at most if these hyperedges form a matching. We design parallel algorithms that divide a matching into different sets based on their core numbers and allot a thread to each set. Experiments show that our parallel algorithms have good stability, scalability, and parallelism. Compared with the parallel static algorithm (Gabert et al. 2021) and the parallel dynamic algorithm GPC (Gabert et al. 2021), our parallel algorithms with 32 threads can accelerate 33x and 22x at most in the processing time, respectively.
Keyword:
processing time
respectively. Index Terms-Core maintenance
dynamic hypergraphs
parallel algorithm
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
查看更多内容