典型文献
基于顶点度数的图数据分区域重排序
文献摘要：
图计算在机器学习、数据挖掘、网络安全等领域都有着重要应用.而图数据结构不规则且规模巨大,导致访存成为图应用运行时的瓶颈.由于图数据的顶点度数服从幂律分布,许多研究通过重排序图数据使高度数顶点连续储存在相邻位置,从而提升图数据被访问时的时间与空间局部性.然而重排序会破坏原始图数据中存在的群落结构,导致目前基于顶点度数信息的重排序算法在高结构性图数据集上无法产生性能提升.本文针对上述问题提出了一种新的保护图数据结构性的重排序算法,通过对自然图数据集中存在的群落结构进行研究,结合处理器访存结构特性,将图数据集合理划分成不同区域后进行重排序,保护其群落存储顺序以提高重排序后访存时的局部性.本文在通用处理器平台上,对6个不同结构性图数据集和3种图计算应用共18个测试点进行了验证,实验结果表明,该重排序方法相对于原始图数据集实现了平均18.86％的性能提升,相对于目前最优的基于顶点度数信息的轻量级重排序算法实现了平均11.3％的性能提升.
文献关键词：
图数据重排序;顶点度数;访存局部性;幂律分布;群落结构
中图分类号：
作者姓名：
李策;章隆兵
作者机构：
计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190;中国科学院大学计算机学院 北京100190
文献出处：
引用格式：
[1]李策;章隆兵-.基于顶点度数的图数据分区域重排序)[J].高技术通讯,2022(09):903-913
A类：
顶点度数,图数据重排序,访存局部性
B类：
数据分区,图计算,重要应用,数据结构,结构不规则,服从,幂律分布,时间与空间,群落结构,排序算法,性能提升,结合处,结构特性,数据集合,通用处理器,测试点,排序方法,轻量级,算法实现
AB值：
0.156675
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
