一种存储介质优化的大规模图遍历方法研究

摘要：

大图数据的BFS算法作为一种基础算法,受到工业界和学术界的广泛重视.不同平台涌现出众多大图BFS算法的研究工作,其中多使用固态硬盘来提高算法效率.在BFS算法遍历过程中,存储设备需要连续重复装载会数据以满足遍历需求,而数据重复装载造成大量数据擦写操作,严重影响了固态硬盘的使用寿命.由此可见,减少BFS算法数据擦写操作可以有效延长固态硬盘的使用寿命.结合图结构的特点,提出数据重用模型,用于描述图遍历过程中的数据重用程度;提出了基于图顶点度的启发式优先访问方法,该方法判断图顶点之间的独立性,并根据判断结果选择优先访问的图顶点,增加数据重用的可能性,提高缓存的命中率,减少闪存颗粒磨损.所提优化方法不修改BFS算法和大图数据,适用于各种BFS算法和数据集.最后,实验验证了所提数据重用模型的正确性,以及启发式优先访问方法的有效性.该优化方法应用于BFS-4K,B40C和Gun-rock这3种常见的BFS算法上,能有效减少图遍历过程中的数据写入操作,固态硬盘的使用寿命可分别提高12％,15％,22％.

关键词：图遍历、固态硬盘、缓存命中率、启发式、使用寿命

所属期刊栏目：50

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61672143

在线出版日期：2023-02-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：34-40