一种基于四维索引的大规模图的可达查询方法和系统

摘要

本发明公开了一种基于四维索引的大规模图的可达查询方法和系统，本发明方法通过递归遍历图的方式把图划分为若干个彼此互不相交的不共享子图以及连接这些不共享子图的跨子图边；根据图划分过程、图划分结果和结点所在的不共享子图为每个结点构建一个四维索引：包括结点所处的层次索引、结点所处的不共享子图编号、结点的初始间隔域和目标间隔域。同时，为了加速查询过程，本发明为每个结点构建了两个等级索引。对于给定的图中的任意结点对，根据四维索引和等级索引的相互关系确定结点对的可达性；本发明还实现了一种基于四维索引的大规模图的可达查询系统。总体而言，本发明技术方案相较现有技术方案在确保高效的查询时间的同时保证了索引构建时间比较快，索引大小不大。