特許
J-GLOBAL ID：201603017411728243
検索装置、検索方法および検索プログラム
発明者：
出願人/特許権者：
代理人 (1件)：
特許業務法人酒井国際特許事務所
公報種別：特許公報
出願番号（国際出願番号）：特願2013-108843
公開番号（公開出願番号）：特開2014-229110
特許番号：特許第6005583号
出願日： 2013年05月23日
公開日（公表日）： 2014年12月08日
請求項（抜粋）：
【請求項1】 コンピュータネットワークを形成する機器をノードとし、前記機器間の接続をエッジとする前記コンピュータネットワークのグラフを、解ノードの個数を示すk(kは前記ノードの数を超えない正整数)の入力を受け付けて検索し、前記k個の解ノードを出力する検索装置であって、
0を初期値とし、+1ずつインクリメントされるiについて、i=0の場合には前記グラフを部分グラフとし、i>0の場合にはi回目の繰り返し計算における候補ノードに基づく(i-1)回目の繰り返し計算における前記グラフの部分グラフへ到達可能なノードの集合からi回目の繰り返し計算における前記グラフの部分グラフを構築する部分グラフ構築処理を実行する部分グラフ構築部と、
前記部分グラフ構築部が構築した部分グラフに対応するランダムウォークの確率を計算するランダムウォーク確率計算部と、
前記ランダムウォーク確率計算部が計算したランダムウォークの確率およびi回目の繰り返し計算における前記候補ノードの全てのノードに対するPageRankのスコアの下限値の推定値および上限値の推定値を計算する推定値計算部と、
i回目の繰り返し計算における前記候補ノードから(i+1)回目の繰り返し計算における前記候補ノードを計算し、当該(i+1)回目の繰り返し計算における前記候補ノードの集合の要素数が前記kに等しい場合には当該(i+1)回目の繰り返し計算における前記候補ノードの集合を解ノードとして出力し、当該(i+1)回目の繰り返し計算における前記候補ノードの集合の要素数が前記kと異なる場合には、前記部分グラフ構築部に当該iをさらに+1インクリメントさせたあらたなiについて前記部分グラフ構築処理を実行させる候補ノード計算部と
を有し、
前記候補ノード計算部が前記部分グラフ構築部に前記あらたなiについて前記部分グラフ構築処理を実行させる場合は、当該あらたなiについて、前記部分グラフ構築部、前記ランダムウォーク確率計算部、前記推定値計算部、前記候補ノード計算部が各処理を再度、順次実行する
ことを特徴とする検索装置。
IPC (1件)：
FI (2件)：
G06F 17/30 419 B
, G06F 17/30 340 B
