グラフ問合せの高速化を可能にする属性分割型グラフストレージエンジンの開発

本研究では，プロパティグラフに対する検索および分析を行うグラフ問合せ性能の向上を目的としている．既存のグラフデータベースシステム(GDB)は，グラフの構成要素に付随しているプロパティを利用した問合せにおいてボトルネックが存在するため，グラフ構成要素の問合せおよび属性問合せがそれぞれ得意なGDBを併用することでその問題を解消する方策を取ることを計画した．一年目はグラフ走査の効率化に着手し，反復的なグラフ走査がよく利用されることに着目し，反復的なグラフ走査のための経路索引を提案した．ただ，データ量の観点からスケールしなかったことから，当初計画に入れていた属性に対する索引に関する提案に着手するよりも先に，二年目からも経路索引の更なる効率化とスケール性の向上を狙うことにした．二年目からは，スケール性を高められるように反復経路の収集を行う対象節点を絞る方法について着手した．反復的にグラフ走査を行う過程でハブを経由すると走査対象が急激に増加することに着目した．ハブはほかの節点よりも外れ値的に次数が多く，次数分布ではグラフ総数のおおよそ2割が該当する．そのハブを対象に反復経路を収集して索引付けする手法について提案を行うことで，収集する反復経路の総数を削減することと効果的な索引付けを行えるように，反復経路索引の再提案を行った．本研究で提案した索引により，反復的なグラフ走査の処理速度は，単一節点からのグラフ走査で10%から18%の向上が見られたため，起点となる節点が増加するとなお効果が得られることが結果として明らかとなった．以上の反復経路索引に関する提案を行い，国内発表3件（内，共著論文1件），国際会議の発表3件を行った．

本研究では，プロパティグラフに対する検索および分析を行うグラフ問合せ性能の向上を目的としている．既存のグラフデータベースシステム(GDB)は，グラフの構成要素に付随しているプロパティを利用した問合せにおいてボトルネックが存在するため，グラフ構成要素の問合せおよび属性問合せがそれぞれ得意なGDBを併用することでその問題を解消する方策を取ることを計画した．一年目はグラフ走査の効率化に着手し，反復的なグラフ走査がよく利用されることに着目し，反復的なグラフ走査のための経路索引を提案した．ただ，データ量の観点からスケールしなかったことから，当初計画に入れていた属性に対する索引に関する提案に着手するよりも先に，二年目からも経路索引の更なる効率化とスケール性の向上を狙うことにした．二年目からは，スケール性を高められるように反復経路の収集を行う対象節点を絞る方法について着手した．反復的にグラフ走査を行う過程でハブを経由すると走査対象が急激に増加することに着目した．ハブはほかの節点よりも外れ値的に次数が多く，次数分布ではグラフ総数のおおよそ2割が該当する．そのハブを対象に反復経路を収集して索引付けする手法について提案を行うことで，収集する反復経路の総数を削減することと効果的な索引付けを行えるように，反復経路索引の再提案を行った．本研究で提案した索引により，反復的なグラフ走査の処理速度は，単一節点からのグラフ走査で10%から18%の向上が見られたため，起点となる節点が増加するとなお効果が得られることが結果として明らかとなった．以上の反復経路索引に関する提案を行い，国内発表3件（内，共著論文1件），国際会議の発表3件を行った．