| 摘要: |
| 研究了基于图压缩的k可达查询处理，提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法，k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系，因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边，然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明，对于稀疏的原始图，两种压缩算法的压缩比分别可以达到45%，对于稠密的原始图，两种压缩算法的压缩比分别可以达到75%和67%；与在原始图上直接进行查询处理相比，两种基于压缩图的查询处理算法效率更好，在稀疏图上的查询效率可以提高2.5倍. |
| 关键词: k可达 图压缩 等价类 查询处理 压缩比 |
| DOI：10.13328/j.cnki.jos.004567 |
| 分类号: |
| 基金项目:国家重点基础研究发展计划（973）（2012CB316200）；国家自然科学基金（61190115，61033015，61173023）；中央高校基本科研业务费专项资金（HIT.NSRIF.201180） |
|
| K-Reach Query Processing Based on Graph Compression |
|
LI Ming-Peng, GAO Hong, ZOU Zhao-Nian
|
|
School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
|
| Abstract: |
| 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. |
| Key words: k-reach graph compression equivalent class query processing compression ratio |
