「Random walk with restartに対する高速な検索手法」
2012年度論文賞受賞者の紹介
Random walk with restartに対する高速な検索手法
［情報処理学会論文誌 データベース Vol.4 No.2 pp.25-34］
［論文概要］
グラフは基本的なデータ構造であり，世の中の様々なシステムで用いられている．グラフのノード間の類似度として近年 Random walk with restart (RWR) が提案され，様々なアプリケーションに応用されている．本論文ではグラフの中から RWR に基づいて問い合わせノードに対する類似ノードを K 個を高速かつ正確に検索する問題を対象とする．提案手法では（１）特定のノードの類似度を疎行列を用いて計算する方法と，（２）不必要な類似度の計算を探索において省略する方法を用いる．実データを用いて比較実験を行い，提案手法は従来手法より高速に類似ノードを検索できることを確認した．
［推薦理由］
本論文は，グラフ上のノード間類似度を高速に求める手法を提案したものである．従来手法が精度を犠牲にした上での高速化手法であったのに対し，提案手法は，不必要な計算の省略と逆行列の計算を疎行列で行うことで，ノード間類似度計算の精度を低下させずに O(10^3) の高速化に成功している点が興味深い．問題設定とその解法が非常にシンプルに纏められていること，ならびに，単なる提案にとどまらず証明が行われ議論が深いことから学術論文としての洗練度が高いだけでなく，グラフ構造に基づく研究分野やシステムへの幅広い応用が期待でき，波及効果は大きい．よって，本論文は，論文賞受賞にふさわしいと判断した．
藤原靖宏 君
2003 年早稲田大学大学院理工学研究科電気工学専攻修士課程修了．2003 年日本電信電話株式会社入社．2011 年東京大学大学院情報理工学系研究科電子情報学専攻博士課程修了，現在，NTT ソフトウェアイノベーションセンタ研究員．博士（情報理工学）．時系列データ処理およびグラフマイニングの研究開発に従事．情報処理学会，電子情報通信学会，日本データベース学会各会員．
中辻真 君
2001年京大工学部数理工学科卒業．2003年京大大学院情報学研究科システム科学専攻修士課程修了．2003年日本電信電話株式会社入社．2010年京大大学院情報学研究科社会情報学専攻博士課程修了（情報学）．2013年から米国レンセラー工科大客員研究員．日本電信電話株式会社サービスエボリューション研究所所属．Semantic Web，情報推薦の研究に従事．電子情報通信学会，人工知能学会会員．
鬼塚真 君
1991年東京工業大学工学部情報工学科卒．同年，NTT入社．2000～2001年ワシントン州立大学客員研究員．現在，日本電信電話（株）ソフトウェアイノベーションセンタ 特別研究員，電気通信大学 客員教授，博士(工学)．大規模グラフデータのデータ処理に関する研究開発に取り組んでいる．本会正会員，ACM, 電子情報通信学会，日本データベース学会各会員．
喜連川優 君
東京大学工学系研究科情報工学博士課程修了(83年)工博 現在 国立情報学研究所長 東大生産技術研究所教授 東大地球観測データ統融合連携研究機構長、文科省「情報爆発」特定研究領域代表、経済産業省「情報大航海」戦略会議委員長、 データベース工学が専門 ACM SIGMOD Edgar F Codd Innovation Award受賞、ACM/IEEEフェロー、情報処理学会/電子情報通信学会フェロー、内閣府最先端研究開発支援プログラムを推進