基于图压缩的最大Steiner连通k核查询处理

摘要

研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明:压缩算法平均可将原始图压缩掉88％,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90％,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1～2个数量级.