伴随着大数据时代的到来,图处理面临的数据规模越来越大,使得传统的距离算法(Dijkstra,BFS,Floyd)因为内存瓶颈变得不再适用,同时在在线应用中,对响应时间要求高,传统算法会因运算时间过长而无法满足实时响应的需求。为满足现实应用中对距离查询的实时响应要求,基于索引的大规模图最短距离查询算法得以提出。这本质上是一种空间换时间的策略。基于索引的查询算法包含两个阶段,即构建索引阶段和距离查询阶段。构建索引是一个离线计算的过程,通过预处理计算出图中部分顶点间的距离并以文件的形式存于磁盘;距离查询是一个在线过程,给出查询的两个顶点,通过前面预计算的索引组合计算出距离。如何构建索引,使得索引的预处理时间尽量短,占用空间尽量小及相应的查询算法尽量简单是解决这类问题的关键因素。针对动态图的索引增量式更新方法,可以在顶点不变,增加新边的情况下,利用“打补丁”的方式更新现有索引,避免了重新构造索引的复杂计算过程,测试结果表明这种方法可有效节约时间。在无向无权稠密图中,例如社交网络,通信网络中存在大量全连通子图(又被称为团)。针对这样的特性,通过一种聚合在一个团中的顶点的距离信息的方法,达到减小索引大小的目的。经过在各种类型的多个真实稠密图数据集上的测试,这种索引同聚合前索引比较可有效压缩索引大小,同时可加快查询速度。