大规模图的可达性查询是指在给定的图中判断从初始结点到目标结点间是否有路径相连。可达性查询是图的基本操作之一,它吸引了许多学术上和工业上的研究者来研究这个问题。目前,图可达性查询主要的技术难题是如何在大规模图中快速地构建大小合理的索引的同时能高效准确地回答结点对的可达性。而随着现实生活中图的规模越来越大,图越来越复杂,可达性查询问题仍具有极大的挑战性。基于多维索引的大规模图可达性查询算法是一种新的图可达性查询算法。它通过递归地遍历图来把图划分成若干个互不相交的不共享子图和连接这些子图的跨子图边。这些不共享子图与原始图相比更简单,它们具有类树结构,因此在不共享子图中利用间隔域来回答结点对的可达性将比在整个图中更有效。接着,为了定位图中结点的位置,该算法为每个结点构建了一个四维索引——结点所处的层次值、结点所处的不共享子图标记值、结点的初始间隔域值、结点的目标间隔域值。其中,结点所处的层次值和结点所处的不共享子图标记值可以定位结点所在的不共享子图的拓扑顺序;结点的初始间隔域值和结点的目标间隔域值可以定位结点在不共享子图内的位置,同时间隔域也可以用来回答位于同一不共享子图的结点对的可达性。随后,为了进一步提高查询效率,该算法建立了两个额外的索引——向上等级索引和向下等级索引——来排除一部分不可达的结点对。最后,利用前面构建的索引设计了一个高效的查询算法来快速回答结点对的可达性。通过与现有的可达性查询算法在28个不同的图上的效果相比,基于多维索引的大规模图可达性查询算法可以快速的构建大小合理的图索引,并且能高效准确地回答结点对的可达性,同时它还具有更好的可扩展性。