特許

J-GLOBAL ID：200903068429385732

データ検索装置及びその方法、及びそのプログラム

発明者： 鷲澤 輝芳
出願人/特許権者： キヤノン株式会社
代理人 (1件)： 西山 恵三 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願2001-122756
公開番号（公開出願番号）：特開2002-318819
出願日： 2001年04月20日
公開日（公表日）： 2002年10月31日
要約：

【要約】【課題】 与えられたベクトルデータに対して重み付きノルムを基にした類似度によるデータ検索が高速に実行できるようにする。【解決手段】 前処理として、ベクトルの各成分に対するソーティング・リストを作成しておき(S101)、プロトタイプをk個取り出し、近傍集合N0の初期値とする(S102)。順次プロトタイプYtを取り出し、類似度ρ(X,Yt)が今までの最小値より大きければ、最小値に対応するプロトタイプとYtを入れ替え、近傍集合及び最小値を更新する(S104〜107)。終了条件を判定し、満足すれば全ての処理を終了して、この時点の近傍集合を解とする(S108)。

請求項（抜粋）：

d次元ベクトルで記述されたプロトタイプ集合から、与えられたテストベクトルに類似する所定個のプロトタイプを検索結果として抽出するデータ検索装置であって、前記d次元ベクトルの各成分につき、前記プロトタイプ集合の各プロトタイプの識別子と成分値とを成分値の2乗の順に並べたd個のリストを作成する前処理手段と、前記リストから順次プロトタイプを取り出す取り出し手段と、前記リストにおいて次に取り出されるべき位置を格納するd個のポインタ手段と、各プロトタイプの成分値の2乗を用いて、前記テストベクトルと各プロトタイプとの重み付きノルムに基づく類似度を計算する類似度計算手段と、前記類似度の値に基づいて検索結果となる近傍集合を更新する更新手段と、前記d個のリストのそれぞれについて、前記d個のポインタで示される位置に格納されている成分値を用いてd次元境界ベクトルを形成し、該d次元境界ベクトルと前記近傍集合に属する要素が持つ類似度のうちの最小値とを比較することによつて、前記取り出し手段によるプロトタイプの取り出しを終了するかどうかを判定する終了判定手段とを有することを特徴とするデータ検索装置。

IPC (3件)：

G06F 17/30 350 ,  G06F 17/30 170 ,  G06F 17/30 210

FI (3件)：

G06F 17/30 350 C ,  G06F 17/30 170 B ,  G06F 17/30 210 A

Fターム (7件)：

5B075ND02 ,  5B075ND06 ,  5B075NK02 ,  5B075NK07 ,  5B075NK08 ,  5B075PR06 ,  5B075QM08