インデックスを用いた任意の終了確率に対するランダムウォーク

情報処理学会

説明

ユーザの興味に応じたグラフ探索技術として，ユーザが指定した起点ノードから多数のランダムウォークを実行することが注目を集めており，高速なランダムウォークのためには事前実行した経路群であるインデックスをクエリ時に参照することが有効である．ここで，ランダムウォークの探索範囲を制御するパラメータとして終了確率αが存在するが，インデックスを用いた演算では，入力可能なαが限定されることが課題である．そこで本稿では，インデックス生成時の終了確率 αindex 以下の終了確率しか受け付けない既存手法を拡張し，任意の終了確率αに対する経路を生成する手法を提案する．具体的には，終了確率の変更によりランダムウォークの経路長が確率的に変わることに注目し，αとαindex の値に応じてインデックス内の経路群を連結・切断することによって終了確率がαの経路を生成する．加えて，生成する経路群について長さが 1 の経路と 2 以上の経路を分けて生成することにより，連結する経路数の減少を実現する．そして，実世界の 6 種類のデータセットを用いて提案手法の実行時間を，インデックスを用いない既存手法と用いる既存手法とで比較した．その結果，提案手法は 2 つの既存手法に対してそれぞれ最大 5.23, 2.27 倍高速であることが明らかになった．

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ