中文摘要：

寻找任意点对之间的最短路径是图数据管理中典型的、重要的基本操作之一.随着各种大型网络数据的不断涌现,实现实时的最短路径查询已成为当前图数据管理领域迫切需要解决的问题.为此,通常需要通过预计算最短路径并将其组织成为合适的索引结构,从而实现常量时间内的最短路径查询(SPQ)回答.然而,直接的最短路径索引方案需要消耗O(N2)的空间代价,这对于大型网络而言是无法承受的.针对这一问题,基于最短路径的第1跳划分表示方法提出了一种基于区间树的编码优化方法RED(region tree based encoding)以及相应的索引和查询方案.模拟网络和真实网络上的实验结果表明,所提的算法在索引空间代价以及查询响应时间上都明显优于目前公认的流行算法.此外,该方法具有普适性,可以直接应用现有的流行算法,在不损失影响查询效率的同时进一步降低最短路径索引代价.

英文摘要：

寻找任意点对之间的最短路径是图数据管理中典型的、重要的基本操作之一.随着各种大型网络数据的不断涌现,实现实时的最短路径查询已成为当前图数据管理领域迫切需要解决的问题.为此,通常需要通过预计算最短路径并将其组织成为合适的索引结构,从而实现常量时间内的最短路径查询(SPQ)回答.然而,直接的最短路径索引方案需要消耗O(N2)的空间代价,这对于大型网络而言是无法承受的.针对这一问题,基于最短路径的第1跳划分表示方法提出了一种基于区间树的编码优化方法RED(region tree based encoding)以及相应的索引和查询方案.模拟网络和真实网络上的实验结果表明,所提的算法在索引空间代价以及查询响应时间上都明显优于目前公认的流行算法.此外,该方法具有普适性,可以直接应用现有的流行算法,在不损失影响查询效率的同时进一步降低最短路径索引代价.