李鸣鹏,高宏,邹兆年.基于图压缩的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) |
|
摘要点击次数: 4299 |
全文下载次数: 3472 |
中文摘要: |
研究了基于图压缩的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阅读器 |