低冗余计算的可达性查询保持图压缩策略

摘要：

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

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

所属期刊栏目：40

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

资助基金：国家重点研发计划项目2016YFC1401907

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

页数：共8页

页码：510-517