特許

J-GLOBAL ID：200903047089050105

多次元ベクトル空間内の近傍検索方法とそのプログラムの記録媒体

発明者： キャサリン カーティス ,  山室 雅司 ,  谷口 展郎
出願人/特許権者： 日本電信電話株式会社
代理人 (1件)： 若林 忠
公報種別：公開公報
出願番号（国際出願番号）：特願平9-106240
公開番号（公開出願番号）：特開平10-301937
出願日： 1997年04月23日
公開日（公表日）： 1998年11月13日
要約：

【要約】【課題】 木構造インデクスのノード間の重なり部分を検索する無駄を省いて検索を高速化する。【解決手段】 各階層の要素をいくつかのクラスタといずれのクラスタにも属しない余りの要素とに分類する処理を各階層ごとに繰り返して非均衡木の木構造インデクスを予め構築する手順702と、参照点が入力されたとき、その木構造インデクスのノードへのポインタとそのノードに対応する多次元ベクトル空間内の点と参照点との距離評価値との組を作成して検索管理情報リストに格納する手順702と、検索管理情報リストを参照して木構造インデクスをルートノードから順に辿る手順703と、検索管理情報リストを更新する手順705,706と、検索の処理停止を判断する手順704とを含む方法ならびにそのプログラムを記録した記録媒体。

請求項（抜粋）：

木構造インデクスと呼ばれる補助データ構造を構築し、多次元ベクトル空間内の多数の点の中から、その空間内で指定された点、以下参照点という、との間の距離評価値が近い点を前記木構造インデクスを利用して特定の数だけ取り出す多次元ベクトル空間内の近傍検索方法において、各階層の要素をいくつかのクラスタと、いずれのクラスタにも属さない余りの要素とに分類する処理を各階層ごとに繰返して木構造インデクスを構築する手順と、前記木構造インデクスのノードへのポインタと、そのノードに対応する多次元ベクトル空間内の点と前記参照点との距離評価値との組を情報として作成し検索管理情報リストに格納する手順と、前記検索管理情報リストを参照して、その木構造インデクスをルートノードから順に辿る手順と、前記検索管理情報リストを更新する手順と、検索の処理停止を判断する手順と、を有することを特徴とする多次元ベクトル空間内の近傍検索方法。