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

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