《表4 查询时间：有向图上k步可达查询处理》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《有向图上k步可达查询处理》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

PLL算法和PLL算法在分别使用了2种优化方法之后的查询时间见表4。其中，查询距离k取10。从表4中可以看出在应用了互逆拓扑序号后的查询效率有了明显的提升，在一些数据集上有2～3倍左右的提升。PLL算法在回答不可达查询时的时间消耗要大于回答可达的查询顶点对所花费的时间，而互逆拓扑序号能在O（1）的时间内回答绝大部分的不可达查询，因此提高了查询的效率。对于PLL+GC方法来说，由于进行了图压缩，因此建立的索引大小更小，从而使得查询时需要遍历的hop顶点数更少，因此也在一定程度上提高了查询效率。