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