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

Strategy with low redundant computation for reachability query preserving graph compression

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

Since some computation in reachability Query Preserving Graph Compression(QPGC)algorithm are redundant,a high-performance compression strategy was proposed.In the stage of solving the vertex sets of ancestors and descendants,an algorithm named TSB(Topological Sorting Based algorithm for solving ancestor and descendant sets)was proposed for common graph data.Firstly,the vertices of the graph data were topological sorted.Then,the vertex sets were solved in the order or backward order of the topological sequence,avoiding the redundant computation caused by the ambiguous solution order.And an algorithm based on graph aggregation operation was proposed for graph data with short longest path,namely AGGB(AGGregation Based algorithm for solving ancestor and descendant sets),so the vertex sets were able to be solved in a certain number of aggregation operations.In the stage of solving reachability equivalence class,a Piecewise Statistical Pruning(PSP)algorithm was proposed.Firstly,piecewise statistics of ancestors and descendants sets were obtained and then the statistics were compared to achieve the coarse matching,and some unnecessary fine matches were pruned off.Experimental results show that compared with QPGC algorithm:in the stage of solving the vertex sets of ancestors and descendants,TSB and AGGB algorithm have the performance averagely increased by 94.22%and 90.00%respectively on different datasets;and in the stage of solving the reachability equivalence class,PSP algorithm has the performance increased by more than 70%on most datasets.With the increasing of the dataset,using TSB and AGGB cooperated with PSP has the performance improved by nearly 28 times.Theoretical analysis and simulation results show that the proposed strategy has less redundant computation and faster compression speed compared to QPGC.