基于图压缩的k可达查询处理

• 作者: 李鸣鹏 邹兆年 高宏
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: k可达 图压缩 等价类 查询处理 压缩比
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 大数据专题
• 页码范围: 797-812
• 页数: 16页
• 分类号: TP311
• 字数: 16602字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004567

摘要

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45％,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75％和67％;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.

作者信息

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