计算机应用

作者：赵丹枫, 林俊辰, 宋巍, 王建, 黄冬梅

单位：1.上海海洋大学 信息学院，上海 201306；2.上海电力大学，上海 200090

关键词：可达性查询,图压缩,查询保持,图数据,拓扑排序,聚合运算

基金：国家重点研发计划项目(2016YFC1401907)

针对可达性查询保持图压缩（QPGC）算法存在冗余计算的问题，提出了一种高性能压缩策略。在求解顶点的祖先后代集阶段，针对普通图数据，提出一种基于拓扑排序的求解算法TSB，首先将图数据顶点拓扑排序，然后沿拓扑序列顺序（逆序）求解顶点的祖先（后代）集，避免了求解顺序不明确导致的冗余计算；针对最长路径较短的图数据，提出一种基于图聚合运算的求解算法AGGB，可在确定次数的聚合运算内完成顶点的祖先和后代集的求解。在求解可达性等价类阶段，提出一种分段统计剪枝算法PSP，先对祖先后代集分段统计，再比较统计值以实现粗匹配，剪除了部分不必要的精细匹配。实验结果表明，与QPGC算法相比：在祖先后代集求解阶段，TSB和AGGB在不同数据集上的性能平均提升94.22%和90.00%；在求解可达性等价类阶段，PSP算法在大部分数据集上性能提升超过70%；随着数据集的增大，TSB和AGGB配合PSP算法，性能提升了近28倍。理论分析和模拟实验表明，该策略与QPGC算法相比冗余计算更少、压缩速度更快。

来源：2020年第2期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第2期