论文部分内容阅读
图顶点相似度计算问题,即在图上计算出所有相似度系数大于等于给定阈值的顶点对,该问题作为图分析领域的基础性算法问题,广泛应用于用户推荐、关系链预测等领域。然而,图顶点相似度计算是一个计算复杂度较高的问题,尤其是在大数据时代。因此,大规模分布式图顶点相似度计算方法和算法研究成为一个重要的研究课题,具有很高的理论研究和实际应用价值。目前已有一些分布式图顶点相似度计算算法研究工作,主要分为基于过滤的计算和全量计算两大类方法。然而,目前已有的工作和方法还存在诸多问题,例如全量计算算法存在冗余、shuffle阶段的冗余数据造成网络通信量的增加等等。同时,现有算法不能在0-1的全阈值范围内都取得良好的效果,基于过滤的算法适合高阈值情况,而全量计算算法适合低阈值情况。此外,现有的数据并行平台上的分布式算法shuffle效率较低,Hadoop和Spark平台上数据shuffle处理时都是基于磁盘交换的,对于大规模图上顶点的相似度计算来说,算法执行过程中shuffle处理时会出现频繁的数据交换和读写磁盘文件操作,这大大降低了程序的运行效率。为解决以上问题,本文提出了两个算法FinNOR-MR和FinNOR-Adaptive,主要研究工作和贡献包括以下几点:(1)为解决全量计算算法中存在冗余的问题,本文提出了一种新的分布式图顶点相似度全量计算算法FinNOR-MR,该算法利用一种新的基于分区的交换策略,而不采用传统算法中基于顶点进行数据交换的策略,有效减少了冗余数据传输,网络通信量明显降低。(2)为解决现有算法不能在0-1全阈值范围内都取得良好效果的问题,本文提出了一种高效的自适应算法FinNOR-Adaptive,可高效解决图顶点相似度计算问题,并能在0-1全阈值范围内都取得良好的效果。FinNOR-Adaptive算法具有自适应的能力,在低阈值情况下选择使用全量计算模式,高阈值情况下选择使用基于过滤的计算模式,并利用计算开销的估计模型在计算过程中动态切换计算模式,实现全阈值范围内的高性能顶点相似度计算。(3)为解决现有数据并行计算平台上数据shuffle效率较低的问题,本文利用MapReduce框架和分布式数据库,实现了一种分布式FinNOR-Adaptive算法。该算法用数据库查询代替MapReduce中的数据交换,省去大量的基于磁盘的数据shuffle的IO开销,同时采用高速缓存机制,它可以起到类似于FinNOR-MR中基于分区的交换策略的效果,从而大幅降低网络通信开销。这两种优化措施使得FinNOR-Adaptive在全阈值范围内成为目前计算性能最好的顶点相似度计算算法。(4)实验评估表明,FinNOR-MR算法性能优于目前所有的全量计算算法,与理论分析一致。与目前最快的基于MapReduce的全量计算算法相比,FinNOR-MR算法计算效率可达到3.5倍的加速比,网络通信量下降到现有最快算法的5.7%。同时,实验也证明FinNOR-Adaptive算法在全阈值范围内均能高效解决τ-PVSC问题,自适应策略效果良好,在低阈值部分性能优于最高效的全量计算算法,在高阈值部分性能与最快的基于过滤的算法性能相当。且两个算法算法均有近似线性的数据扩展性和节点扩展性。