%0 Journal Article
%T 基于图压缩的最大Steiner连通k核查询处理
%A 李鸣鹏
%A 邹兆年
%A 高宏
%J -
%D 2016
%R 10.13328/j.cnki.jos.005044
%X 研究了基于图压缩的最大Steiner连通k核查询处理，提出了一种支持最大Steiner连通k核查询的图压缩算法SC，证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域，提出了图压缩算法TC，进一步将压缩图压缩为树.证明了基于压缩树的查询正确性，并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明：压缩算法平均可将原始图压缩掉88%，且对于稠密的原始图，压缩算法的压缩效果更好，可将原始图压缩掉90%，与在原始图上直接进行查询处理相比，基于压缩图的查询处理算法效率更好，平均提升了1～2个数量级
%K 最大Steiner连通k核 图压缩 等价类 查询处理 压缩比
%U http://www.jos.org.cn/jos/ch/reader/view_abstract.aspx?file_no=5044&flag=1