基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理，提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法，k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系，因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边，然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明，对于稀疏的原始图，两种压缩算法的压缩比分别可以达到45%，对于稠密的原始图，两种压缩算法的压缩比分别可以达到75%和67%；与在原始图上直接进行查询处理相比，两种基于压缩图的查询处理算法效率更好，在稀疏图上的查询效率可以提高2.5倍.

K-Reach Query Processing Based on Graph Compression

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.