特許
J-GLOBAL ID：201203098635391937

類似ノード検索装置及び方法及びプログラム

発明者：
藤原 靖宏

藤原 靖宏 について


出願人/特許権者：
日本電信電話株式会社

日本電信電話株式会社 について


代理人 (2件)： 伊東 忠彦 ,  石原 隆治
公報種別：公開公報
出願番号（国際出願番号）：特願2011-019174
公開番号（公開出願番号）：特開2012-160015
出願日： 2011年01月31日
公開日（公表日）： 2012年08月23日
要約：
【課題】 高速かつ正確に類似ノードを検索する。【解決手段】 本発明は、RWRを用いて類似度を計算し、類似度が高い順にK個のノードを検索する際に、外部から入力されたグラフデータから上三角行列と下三角行列の逆行列を生成し、外部から入力された問い合わせノードと検索個数Kと、逆行列に基づいて、検索対象ノードについて、入力された問い合わせノードを始点とする幅優先木を構築し、幅優先探索の順番に推定された類似度(推定値)を計算し、記憶手段に格納し、該推定値が解候補ノードの最も小さい類似度より小さい場合には類似度の計算(検索)を打ち切り、そうでない場合には、問い合わせノードと逆行列から類似度を計算する。【選択図】 図1
請求項（抜粋）：
グラフの構造的な特徴に基づいて類似度を計算するRandom walk with restart(RWR)を用いて類似度を計算する類似度計算手段を有し、類似度が高い順にK個のノードを検索する類似ノード検索装置であって、 外部から入力されたグラフデータから上三角行列と下三角行列の逆行列を生成する事前計算手段と、 外部から入力された問い合わせノードと検索個数Kと、前記事前計算手段で生成された前記逆行列に基づいて、該問い合わせノードを始点とする幅優先木を用いて類似度を推定することにより類似ノードを検索して出力する検索手段と、 K個の検索結果を出力する出力手段と、 を有することを特徴とする類似ノード検索装置。
IPC (1件)：
G06F 17/30
FI (2件)：
G06F17/30 419A ,  G06F17/30 350C
Fターム (4件)：
5B075ND20 ,  5B075ND35 ,  5B075QM08 ,  5B075UU40
引用文献：
出願人引用 (4件)
全件表示
審査官引用 (4件)
全件表示

前のページに戻る

TOP

BOTTOM