複雑ネットワークにおける効率的な反復走査のための経路索引構築法

概要

グラフ問合せにおいて，部分グラフを抽出することは必要不可欠な処理であり，その処理の高速化 が必須になる．本研究では，グラフ問合せ内のパタン指定によく利用され，グラフデータベースにおける 問合せ計画の1 過程である，反復的な経路導出の効率化を目的とする．現在までに効率的な部分グラフ抽 出手法として，経路索引構築やグラフ走査手法が提案されてきたが，どちらか一方の手法では現実的なグ ラフ管理において，辺の次数が外れ値的に多いハブから受ける影響により非効率な処理が発生する．本研 究では，隣接節点を効率的に走査可能なネイティブグラフ処理とハブを起点とする反復経路の索引を組み 合わせることにより，効率的に反復的なグラフ走査を可能にする経路索引構築法を提案する．

引用情報

楠 和馬, 波多野 賢治, 複雑ネットワークにおける効率的な反復走査のための経路索引構築法, 情報処理学会研究報告, Vol.2020-DBS-172, No.9, 2020-12-22.