CAJ | 학술논문

寻找任意点对之间的最短路径是图数据管理中典型的、重要的基本操作之一.随着各种大型网络数据的不断涌现,实现实时的最短路径查询已成为当前图数据管理领域迫切需要解决的问题.为此,通常需要通过预计算最短路径并将其组织成为合适的索引结构,从而实现常量时间内的最短路径查询(SPQ)回答.然而,直接的最短路径索引方案需要消耗O(N2)的空间代价,这对于大型网络而言是无法承受的.针对这一问题,基于最短路径的第1跳划分表示方法提出了一种基于区间树的编码优化方法RED(region tree based encoding)以及相应的索引和查询方案.模拟网络和真实网络上的实验结果表明,所提的算法在索引空间代价以及查询响应时间上都明显优于目前公认的流行算法.此外,该方法具有普适性,可以直接应用现有的流行算法,在不损失影响查询效率的同时进一步降低最短路径索引代价.
심조임의점대지간적최단로경시도수거관리중전형적、중요적기본조작지일.수착각충대형망락수거적불단용현,실현실시적최단로경사순이성위당전도수거관리영역박절수요해결적문제.위차,통상수요통과예계산최단로경병장기조직성위합괄적색인결구,종이실현상량시간내적최단로경사순(SPQ)회답.연이,직접적최단로경색인방안수요소모O(N2)적공간대개,저대우대형망락이언시무법승수적.침대저일문제,기우최단로경적제1도화분표시방법제출료일충기우구간수적편마우화방법RED(region tree based encoding)이급상응적색인화사순방안.모의망락화진실망락상적실험결과표명,소제적산법재색인공간대개이급사순향응시간상도명현우우목전공인적류행산법.차외,해방법구유보괄성,가이직접응용현유적류행산법,재불손실영향사순효솔적동시진일보강저최단로경색인대개.