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

摘要：

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

关键词：最大Steiner连通k核、图压缩、等价类、查询处理、压缩比

所属期刊栏目：27

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

资助基金：国家重点基础研究发展计划9732012CB316200;国家自然科学基金61190115,61033015,61173023;中央高校基本科研业务费专项HIT.NSRIF.201180National Basic Research Program of China 9732012CB316200;National Natural Science Foundation of China61190115,61033015,61173023;Fundamental Research Funds for the Central UniversitiesHIT.NSRIF.201180

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

页数：共13页

页码：2265-2277