講演情報
[5D-01]事前探索を用いた高速な幅優先探索
*新井 淳也1、山村 圭一郎2、藤澤 克樹2 (1. 日本電信電話株式会社、2. 東京科学大学)
発表者区分：一般
論文種別：ロングペーパー
インタラクティブ発表：あり
論文種別：ロングペーパー
インタラクティブ発表：あり
キーワード：
グラフデータ、データ分析アルゴリズム、グラフデータベース
幅優先探索（BFS）はソーシャルグラフやWebグラフのような実世界のグラフの処理で広く用いられる基礎的な操作である．これらのグラフはしばしば大規模であり，さらに異なる根から繰り返しBFSを実行する場合もあることから，1回あたりのBFS処理時間の短縮は重要な課題である．そこで本論文では新しい高速なBFSアルゴリズムを提案する．実世界のグラフにおけるBFSが根の選択によらず同じ探索経路を取りやすいことに着目し，提案手法は事前計算を通じて後続のBFSを高速化するテクニックであるビット並列探索とブロック枝刈りを導入する．評価実験において提案手法は既存手法と比べ大幅に高い性能を示した．