Personalized PageRankに対するアドホックな検索手法

藤原 靖宏  中辻 真  塩川 浩昭  三島 健  鬼塚 真  

誌名
電子情報通信学会論文誌 D   Vol.J98-D   No.5   pp.774-787
発行日: 2015/05/01
Online ISSN: 1881-0225
論文種別: 特集論文 (データ工学と情報マネジメント論文特集)
専門分野: グラフ検索
キーワード: 
Personalized PageRank,  アドホック,  高速,  アルゴリズム,  

本文: FreePDF(692.1KB)


あらまし: 
Personalized PageRank (PPR) はグラフにおけるノード間の代表的な類似度であり,PPRに対するノードの検索は多くのアプリケーションにおいて用いられている.多くのアプリケーションにおいてグラフは動的に変化する性質があるなどの理由から,PPRに対してアドホックな検索が行えることが望ましい.アドホックな検索とは,検索を行うごとに検索対象のグラフやパラメータを変えながら検索を行うことである.しかしグラフのサイズが大きくなるとアドホックに検索を行う計算コストが高くなるという問題がある.過去にもPPRの計算コストを低減するためにさまざまな手法が提案されてきた.しかしそれらの手法は事前計算が必要であったり,近似的な検索結果になるなどの理由から有効にアドホックな検索を行えないという問題があった.本論文ではPPRに対してアドホックな検索を行う高速化手法 Castanet を提案する.提案手法は(1)再帰的にPPRのスコアの下限値と上限値を推定し,(2)繰り返し計算の中で動的に検索結果を得るのに不必要なノードを枝狩りすることを特徴とする.実験から提案手法は既存手法より高速にPPRに対してアドホックな検索が可能であること確認した.