部分グラフ検索高速化のためのハブ節点を考慮した関係辺の再帰走査法

概要

柔軟な表現力の高さからさまざまな分野において，データがグラフ構造で表現されている．グラフデータベースには，膨大で複雑なグラフを一定コストでグラフ走査を行えるインデックスフリー隣接性という特性がある．しかし，同一関係性を再帰的に辿るような問合せでは，グラフ全体を走査することになり同一の節点に到達することが多くなる．また，辺の次数が多いハブ節点の影響を受けることで，辺の走査を必要とする節点候補が増加し，問合せ結果の導出コストが高くなる非効率性がある．そこで本研究では，次数が外れ値的に多いようなハブ節点の存在を考慮し，ハブ節点へのパスおよびハブ節点からの再帰的な同一関係性の経路情報をインデックスフリー隣接性に拡張することで効率的なグラフ走査方法を提案する．

引用情報

楠 和馬, 波多野 賢治, 部分グラフ検索高速化のためのハブ節点を考慮した関係辺の再帰走査法, 第12回データ工学と情報マネジメントに関するフォーラム予稿集, 2020-03-04.