欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
研究了基于图压缩的k可达查询处理，提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法，k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的．由于k-RPC算法是基于严格的等价关系，因此进一步又提出了线性时间的近似图压缩算法k-GRPC-k-GRPC算法允许从原始图中删除部分边，然后使用k-RPC获得更好的压缩比．提出了线性时间的无需解压缩的查询处理算法．真实数据上的实验结果表明，对于稀疏的原始图，两种压缩算法的压缩比分别可以达到45％，对于稠密的原始图，两种压缩算法的压缩比分别可以达到75％和67％；与在原始图上直接进行查询处理相比，两种基于压缩图的查询处理算法效率更好，在稀疏图上的查询效率可以提高2．5倍．
英文摘要：
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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：