-
题名基于图压缩的最大Steiner连通k核查询处理
被引量：2
- 1
-
-
作者
李鸣鹏
高宏
邹兆年
-
机构
哈尔滨工业大学计算机科学与技术学院
-
出处
《软件学报》
EI
CSCD
北大核心
2016年第9期2265-2277,共13页
-
基金
国家重点基础研究发展计划(973)(2012CB316200)
国家自然科学基金(61190115
+2 种基金
61033015
61173023)
中央高校基本科研业务费专项(HIT.NSRIF.201180)~~
-
文摘
研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明：压缩算法平均可将原始图压缩掉88%,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90%,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1~2个数量级.
-
关键词
最大steiner连通k核
图压缩
等价类
查询处理
压缩比
-
Keywords
maximum steiner connected k-core
graph compression
equivalent class
query processing
compression ratio
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
