%0 Journal Article
%T 基于图压缩的k可达查询处理
%A 李鸣鹏？
%A 高宏？
%A 邹兆年？
%J 软件学报
%P 797-812
%D 2014
%R 10.13328/j.cnki.jos.004567
%X 研究了基于图压缩的k可达查询处理，提出了一种支持k可达查询的图压缩算法k-rpc及无需解压缩的查询处理算法，k-rpc算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-rpc算法是基于严格的等价关系，因此进一步又提出了线性时间的近似图压缩算法k-grpc.k-grpc算法允许从原始图中删除部分边，然后使用k-rpc获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明，对于稀疏的原始图，两种压缩算法的压缩比分别可以达到45%，对于稠密的原始图，两种压缩算法的压缩比分别可以达到75%和67%；与在原始图上直接进行查询处理相比，两种基于压缩图的查询处理算法效率更好，在稀疏图上的查询效率可以提高2.5倍.
%K k可达
%K 图压缩
%K 等价类
%K 查询处理
%K 压缩比
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=4567&flag=1