图常用的查询算法有可达性、最短路径距离和最宽路径查询等,传统查询算法有两种:一种是求解完整传递闭包,即预计算出所有的结果,那么查询效率为(1);另一种则是使用修改的Dijkstra算法或其他算法直接在原图上进行搜索,空间开销为(1)。而近年来图规模快速增长,其节点和边的总数可以达到亿级规模。针对如此大规模的图,前者查询效率虽高,但是空间开销使其难以扩展;后者虽然空间开销(1)很低,但直接在原图搜索的算法往往因其过高的时间复杂度,无法满足一些实时性要求很高的应用。因此在大规模图中,如何进行快速高效地查询是极具挑战意义的。面向亿级图的高效索引和查询系统是为了解决传统算法在大规模图处理中,查询效率低或者空间复杂度过高的问题。该系统基于2-hop label索引结构,采用空间换时间的思想,在查询效率和空间复杂度之间获得平衡。并提出了一个基于剪枝思想的最宽路径索引算法,该算法在处理大规模图时,能使索引规模显著降低。算法为每个节点依次执行剪枝的Dijkstra算法,并产生索引标签。其能减少索引时间和索引大小的核心关键是引入一个剪枝的操作。除此之外,本系统还集成了能支持亿级规模图的最短路径、可达性查询的索引算法,并提供索引的分布式存储和查询。实验结果表明,本系统基于剪枝的最宽路径索引方法,可以处理至亿级规模图,且查询时间在微秒级别。与传统算法相比,查询速度提高了6个数量级,并且在索引时间、索引大小和查询效率之间取得一个较好平衡,扩展性良好。同时本系统集成的最短路径、可达性查询的索引算法,都能够支持至亿级规模图,查询时间也都在微秒级别。