主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李鸣鹏,高宏,邹兆年.基于图压缩的k可达查询处理.软件学报,2014,25(4):797-812
基于图压缩的k可达查询处理
K-Reach Query Processing Based on Graph Compression
投稿时间:2013-10-09  修订日期:2013-12-18
DOI:10.13328/j.cnki.jos.004567
中文关键词:  k可达  图压缩  等价类  查询处理  压缩比
英文关键词:k-reach  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  
摘要点击次数: 2897
全文下载次数: 2630
中文摘要:
      研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.
英文摘要:
      This paper focuses on k-reach query processing based on graph compression and proposes a k-reach query preserving graph compression algorithm k-RPC and a query processing algorithm which is able to query on the compressed graph without decompression. k-RPC algorithm is optimal among all the compression algorithms based on equivalent class which supports k-reach query. Considering k-RPC is based on a strict equivalent relation, this study further produces a linear approximate graph compression algorithm k-GRPC. k-GRPC first removes some edges from the input graph, then utilizes k-RPC to acquire better compression ratio. Novel linear query processing algorithms which are able to answer k-reach query on the compressed graph without decompression are introduced. Experiments on real datasets demonstrate that the compression ratios of these two compression algorithms can reach to 45% for sparse graphs and 75%, 67% for dense graphs. Comparing with the query processing on original graphs, the query performance on compressed graphs is better and for sparse graphs, it can be 2.5 times better.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

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