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

• 作者: 李鸣鹏 邹兆年 高宏
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 最大Steiner连通k核 图压缩 等价类 查询处理 压缩比
• 年，卷（期）: 2016,（9）
• 所属期刊栏目: 数据库技术
• 页码范围: 2265-2277
• 页数: 13页
• 分类号: TP311
• 字数: 13036字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005044

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高宏	哈尔滨工业大学计算机科学与技术学院	109	1574	18.0	36.0
2	邹兆年	哈尔滨工业大学计算机科学与技术学院	17	244	9.0	15.0
3	李鸣鹏	哈尔滨工业大学计算机科学与技术学院	3	19	2.0	3.0