講演情報
[5D-02]集約隣接リストを用いたWorst-Case Optimal Joinの高速化
*伊藤 寿浩1、塩川 浩昭2 (1. 筑波大学理工情報生命学術院、2. 筑波大学計算科学研究センター)
発表者区分：学生
論文種別：ロングペーパー
インタラクティブ発表：あり
論文種別：ロングペーパー
インタラクティブ発表：あり
キーワード：
Worst-Case Optimal Join、部分グラフ問合せ、データ構造、アルゴリズム
Worst-Case Optimal Join (WCOJ) は部分グラフ問合せを処理する主要な手法であり，問合せ処理の中間結果が爆発的に増加することを抑制することで効率的な処理を実現する．しかし，WCOJでは隣接リストの積集合を得る操作が頻出することから，大規模なグラフデータに対してWCOJを実行する場合に多くの処理時間を要する．そこで本稿ではWCOJに対して，集約隣接リストを用いた高速な部分グラフ問合せ処理アルゴリズムを提案する．集約隣接リストは隣接頂点の隣接リストを併合した索引であり，複数の積集合の取得処理を一度に処理することで操作回数を劇的に削減する．加えて，集約隣接リストは指定されたメモリサイズに応じて構築可能であり，資源が制限された状況においても効率的な処理を提供できる．実験では，規模やスケールフリー性が異なる多様なグラフデータ上で性能評価を行い，提案手法が最先端手法と比較して最大50倍高速に処理可能であることを示す．