主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李鸣鹏,高宏,邹兆年.基于图压缩的最大Steiner连通k核查询处理.软件学报,2016,27(9):2265-2277
基于图压缩的最大Steiner连通k核查询处理
Maximum Steiner Connected k-Core Query Processing Based on Graph Compression
投稿时间:2015-09-24  修订日期:2016-01-12
DOI:10.13328/j.cnki.jos.005044
中文关键词:  最大Steiner连通k  图压缩  等价类  查询处理  压缩比
英文关键词:maximum Steiner connected k-core  graph compression  equivalent class  query processing  compression ratio
基金项目:国家重点基础研究发展计划(973)(2012CB316200);国家自然科学基金(61190115,61033015,61173023);中央高校基本科研业务费专项(HIT.NSRIF.201180)
作者单位E-mail
李鸣鹏 哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001 lmp@hit.edu.cn 
高宏 哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001  
邹兆年 哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150001  
摘要点击次数: 1021
全文下载次数: 1349
中文摘要:
      研究了基于图压缩的最大Steiner连通k核查询处理,提出了一种支持最大Steiner连通k核查询的图压缩算法SC,证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域,提出了图压缩算法TC,进一步将压缩图压缩为树.证明了基于压缩树的查询正确性,并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明:压缩算法平均可将原始图压缩掉88%,且对于稠密的原始图,压缩算法的压缩效果更好,可将原始图压缩掉90%,与在原始图上直接进行查询处理相比,基于压缩图的查询处理算法效率更好,平均提升了1~2个数量级.
英文摘要:
      This paper focuses on maximum Steiner connected k-core query processing based on graph compression, and proposes a maximum Steiner connected k-core query preserving graph compression algorithm, SC. The correctness of querying based on SC algorithm is proved. Since maximum Steiner connected k-core query only requires a connected component which satisfies certain properties, graph compression algorithm TC is proposed to further compact the compressed graph into a tree. It is proved that querying based on the compacted tree is correct. A novel linear query processing algorithm which is able to query on the compacted tree without decompression is also introduced. Experiments on both real and synthetic datasets demonstrate that the compression algorithm could compress the original graph by 88% in average, and for denser graphs, the compression algorithm achieves better compression ratio, reducing the original graph by nearly 90%. Comparing with the query processing on original graphs, the query performance on compressed graphs is better, and in average, it could be 1 to 2 orders of magnitude times better.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利