[5D]グラフ問合せ

14:45 〜 15:10

[5D-04] 経路分割とサンプリングを活用した正規経路問合せのカーディナリティ推定

*三木 隆哉¹、佐々木 勇和¹ (1. 大阪大学)

発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：あり

キーワード：

正規経路問合せ、カーディナリティ推定、グラフデータベース

正規経路問合せは，ラベル列が正規表現の言語である経路によって接続されている節点の対を返す問合せである．カーディナリティ推定は，問合せ最適化やスケジューリングのためにカーディナリティを事前に見積もる技術である．本研究では，高速化のために経路を分割し，分割する箇所の節点集合をサンプリングする手法を提案する．経路を分割することで，グラフの探索範囲を狭めることができる．加えて，節点集合をサンプリングすることで，すべての節点に対して問合せを処理することなくカーディナリティを推定することが可能となる．実験では，サンプリングする割合を小さくした場合であっても，サンプリング割合が大きい場合と比較して精度を落とさずに推定できることを示す．