Random walk with restartに対する高速な検索手法

• Item type: Trans(1)
• 公開日: 2011-07-01
• タイトル: Random walk with restartに対する高速な検索手法
• タイトル / 言語: en
• タイトル: Efficient Search Method for Random Walk with Restart
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文（優秀論文賞受賞）
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 日本電信電話株式会社NTTサイバースペース研究所／東京大学生産技術研究所
• 著者所属: 日本電信電話株式会社NTTサイバーソリューション研究所
• 著者所属: 日本電信電話株式会社NTTサイバースペース研究所
• 著者所属: 東京大学生産技術研究所
• 著者所属(英): en
• 著者所属(英): NTT Cyber Space Laboratories, NTT Corporation / Institute of Industrial Science, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): NTT Cyber Solution Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Cyber Space Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, The University of Tokyo
• 著者名: 藤原, 靖宏; 中辻, 真; 鬼塚, 真; 喜連川, 優
• 著者名(英): Yasuhiro, Fujiwara; Makoto, Nakatsuji; Makoto, Onizuka; Masaru, Kitsuregawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフは基本的なデータ構造であり，世の中の様々なシステムで用いられている．グラフのノード間の類似度として近年Random walk with restart（RWR）が提案され，様々なアプリケーションに応用されている．本論文ではグラフの中からRWRに基づいて問合せノードに対する類似ノードをK個高速かつ正確に検索する問題を対象とする．提案手法では(1)特定のノードの類似度を疎行列を用いて計算する方法と，(2)不必要な類似度の計算を探索において省略する方法を用いる．実データを用いて比較実験を行い，提案手法は従来手法より高速に類似ノードを検索できることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Graphs are a fundamental data structure and have been recently employed to model real-world systems and phenomena. Random walk with restart (RWR) provides a good similarity score between two nodes in a graph, and it has been successfully used in many applications. The goal of this work is to find nodes that have high similarities for a given node based on RWR. Our solution is based on two ideas: (1) We computes the similarity of a selected node by matrices, and (2) we skips similarity computations when searching nodes. We perform comprehensive experiments to verify the efficiency of our approach. The results show that our approach can find high similarity nodes with significantly better speed than the previous approaches.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 4, 号 2, p. 25-34, 発行日 2011-07-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会