Edge Cluster Based Large Graph Partitioning and Iterative Processing in BSP
-
摘要: 近年来随着互联网的普及和相关技术的日益成熟,大规模图数据处理成为新的研究热点.由于传统的如Hadoop等通用云平台不适合迭代式地处理图数据,研究人员基于BSP模型提出了新的处理方案,如Pregel,Hama,Giraph等.然而,图处理算法需要按照图的拓扑结构频繁交换中间计算结果而导致巨大的通信开销,这严重地影响了基于BSP模型的系统的处理性能.首先从降低消息通信的角度分析当前主流BSP系统的处理方案,然后提出了一种基于边聚簇的垂直混合划分策略(EC-VHP),并建立代价收益模型分析其消息通信优化的效果.在EC-VHP的基础上,提出了一个点-边计算模型,并设计了简单Hash索引和多队列并行顺序索引机制,进一步提高消息通信的处理效率.最后,在真实数据集和模拟数据集上的大量实验,验证了EC-VHP策略和索引机制的正确性和有效性.Abstract: With the development of Internet and the gradual maturity of related techniques in recent years, the processing of large graphs has become a new hot research topic. Since it is not appropriate for traditional cloud computing platforms to process graph data iteratively, such as Hadoop, researchers have proposed some solutions based on the BSP model, such as Pregel, Hama and Giraph. However, since graph algorithms need to frequently exchange intermediate results in accordance with the graph’s topological structure, the tremendous communication overhead impacts the processing performance of systems based on the BSP model greatly. In this paper, we first analyze the solutions proposed by the well-known BSP-based systems in reducing communication overhead, and then propose a graph partition strategy named edge cluster based vertically hybrid partitioning (EC-VHP), building a cost benefit model to study its effectiveness to the communication overhead. Then based on EC-VHP, we propose a vertex-edge computation model, and design both a plain hash index structure and a multi-queue parallel sequential index structure to further improve the processing efficiency of message communication. Finally, our experiments on real and synthetic data sets demonstrate the efficiency and accuracy of the EC-VHP and the index mechanism.
-
Keywords:
- large graph /
- BSP model /
- graph partition /
- vertex-edge computation model /
- index structure
-
-
期刊类型引用(6)
1. 徐嘉振,何文雪,李浩然. 基于注意力时间卷积的运动想象脑电分类方法. 现代电子技术. 2024(18): 70-76 . 百度学术
2. 仝航,杨燕,江永全. 检测脑电癫痫的多头自注意力机制神经网络. 计算机科学与探索. 2023(02): 442-452 . 百度学术
3. 王昊 ,周建涛 ,郝昕毓 ,王飞宇 . 基于特征再抽象(FRA)的多元时序预测方法. 计算机科学. 2023(S2): 662-669 . 百度学术
4. 蔡霄仙,陈顺芝,王江辉,丁洋,费克玲. 基于多时窗共空间模式的HMM运动想象脑电识别. 计算机测量与控制. 2023(12): 277-283 . 百度学术
5. 许萌,王丹,李致远,陈远方. IncepA-EEGNet:融合Inception网络和注意力机制的P300信号检测方法. 浙江大学学报(工学版). 2022(04): 745-753+782 . 百度学术
6. 张远鹏,蔡可夫,姚敏,姚登福,王理. 基于深度堆叠式稀疏回归的癫痫患者脑电信号特征选择. 南通大学学报(医学版). 2021(03): 212-216 . 百度学术
其他类型引用(15)
计量
- 文章访问数: 1371
- HTML全文浏览量: 0
- PDF下载量: 817
- 被引次数: 21