WO2013051619A1 - 類似性検出装置及び指向性近傍検出方法 - Google Patents

Abstract

　大量のデータから類似のデータを高速に検出するために、パラメータリストに基づいて乱数情報を算出する乱数発生装置３と、その乱数情報に基づいて複数のキー計算関数を算出し、入力データに基づいて複数のテーブルを算出し、検索条件が示すクエリに基づいて候補データリストを算出するテーブル管理装置５と、その候補データリストから検索条件が示す条件を満足する検索結果データを算出するデータ処理装置６とを備えている。その各テーブルは、あるキーに対応するバリューが、あるキー計算関数に代入した値がそのキーに等しくなるデータのデータリストを示すように算出される。その候補データリストは、複数の検索データリストを含み、そのテーブルに対応する検索データリストは、そのクエリをそのキー計算関数に代入したクエリ値に対応するバリューを示している。

Description

類似性検出装置及び指向性近傍検出方法

　本発明は、特徴検出装置及び指向性近傍検出方法に関し、特に、多次元連続データ集合から所望のデータを検索する特徴検出装置及び指向性近傍検出方法に関する。

　近傍検索技術は、様々な応用範囲で用いられる重要な技術であり、例えば、画像やＷｅｂページ等のデータの類似性を考慮し、膨大なデータベースの中から特徴が似たデータを検出する等のアプリケーションに用いられる。非常に単純な方法として、それぞれのデータの特徴を距離の定義された空間の一点（例えばユークリッド空間の一点）で表現し、クエリ点からの全てのデータへの距離を計算することで、クエリに近いデータを検出することができる。しかし、このような距離を直接計算する方法は、非常にコストがかかり、データ数の増大とともに計算負荷が非線形に増加してしまうため、様々な方法が提案されている。

　特許文献１（特開２００４－０２１４３０号公報）には、ユーザの操作を煩雑にすることなく、特定の被写体を含む画像を類似画像として的確に検索し得る画像検索装置が開示されている。その画像検索装置は、検索の対象となる画像を複数含む検索対象画像群の中から、検索キーである基準画像に類似する画像を抽出する画像検索装置であって、基準画像及び検索対象画像群に含まれる各画像をそれぞれ複数の領域に分割する手段と、基準画像及び検索対象画像群に含まれる各画像の各領域から少なくとも１つの特徴量を抽出する手段と、検索対象画像群に含まれる各画像について領域の一部を選択する手段であって、検索対象画像群から画像を順次選択し、基準画像の各領域から抽出された特徴量と、当該選択した画像の各領域から抽出された特徴量と、の類似性に基づいて、所定数の当該選択された画像の領域を選択する手段と、前記検索対象画像群に含まれる各画像について選択された一部の領域の特徴量に基づいて、検索対象画像群から基準画像に類似する画像を抽出する手段と、を含むことを特徴としている。

　特許文献２（特開２００５－０７０９２７号公報）には、画像自体の一致度に拘泥されず、描画形状が類似している画像を検出することができるような画像特徴を取得する画像特徴取得方法が開示されている。その画像特徴取得方法は、二次元画像の画像特徴を取得する画像特徴取得方法であって、上記二次元画像を所定の大きさにサイズ変更し、該画像がカラー画像であれば一色の濃淡の階調で形成するスケール画像に変換し、各スケール画像に対して、二次元画像の左右のいずれか一方に設定した起点から水平方向へ連なる画素列を、該画素列の終点と次の画素列の起点とを鉛直方向へ順番に連結して水平成分の一次元ラスタ画像を作成し、二次元画像の上下のいずれか一方に設定した起点から鉛直方向へ連なる画素列を、該画素列の終点と次の画素列の起点とを水平方向へ順番に連結して鉛直成分の一次元ラスタ画像を作成し、これらの一次元ラスタ画像に対して適宜の変換処理を実行する。

　特許文献３（特開平１０－３２６２８６号公報）には、類似検索の精度が向上でき、また重要な類似データが検索結果からぬけおちる可能性が低い類似検索装置が開示されている。その類似検索装置は、複数の対象に対して各々作成され、対象を特徴づける複数の属性をベクトル構成要素とするベクトルデータを複数蓄積するベクトルデータベースと、指定された類似検索対象に対するベクトルデータを作成する対象ベクトルデータ作成部と、複数の検索条件を生成する検索条件集合生成部と、この検索条件集合生成部で生成された個々の検索条件ごとに、上記ベクトルデータベースに蓄積された複数のベクトルデータの中から、上記検索条件を満足し、かつ上記対象ベクトルデータに類似するベクトルデータを検索する類似検索エンジンと、上記類似検索エンジンにより検索された結果を個々の検索条件ごとに表示する検索結果表示部とを備えたことを特徴としている。

　一般に、高次元の空間における近傍検索は、低次元の場合に比べ、更に問題が困難になる。そのため、大量な高次元データに対して、厳密に距離を計算して近傍データを求めるのではなく、近似的に、もしくは確率的に近距離のデータを求める近似的近傍検索方法が提案されている。その一つの代表例は、ＬＳＨ（Ｌｏｃａｌｉｔｙ　Ｓｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ）（非特許文献１参照）である。ＬＳＨは、任意の２点に対して、その２点の距離が近いほど高い確率で衝突する（同じ値をもつ）ハッシュ関数を利用する方法であり、クエリ入力に対する近傍検出演算にかかる時間を削減することができる。ここで、ＬＳＨを用いると、あるクエリｑに対してデータｐが衝突する確率は、その距離ｄ（ｐ、ｑ）にのみ依存するため、クエリｑを中心とする１つの円の円周上にある複数のデータは、全て等確率でクエリｑに衝突することになる。

特開２００４－０２１４３０号公報 特開２００５－０７０９２７号公報 特開平１０－３２６２８６号公報

Ｄａｔａｒ，　Ｍ．，　Ｉｍｍｏｒｌｉｃａ，　Ｎ．，　Ｉｎｄｙｋ，　Ｐ．，　ａｎｄ　Ｍｉｒｒｏｋｎｉ，　Ｖ．　２００４．　Ｌｏｃａｌｉｔｙ　ｓｅｎｓｉｔｉｖｅ　ｈａｓｈｉｎｇ　ｓｃｈｅｍｅ　ｂａｓｅｄ　ｏｎ　ｐ－ｓｔａｂｌｅ　ｄｉｓｔｒｉｂｕｔｉｏｎｓ．　Ｉｎ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＡＣＭ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｇｅｏｍｅｔｒｙ

　第１の問題点は、２つのデータの特徴の近さの指標として、方向に代表される詳細な位置関係が考えられていないことである。具体的には、ある方向に関する距離を他の方向に関する距離より重要視する場合等、方向の違いを区別して近傍検索を行うことができない。その理由は、従来の近傍検索はその距離のみに依存する手法が用いられているからである。

　第２の問題点は、ある観点に対する類似度のみに関心がある場合、従来手法では、余計な計算時間がかかってしまうことである。その理由は、従来手法では、方向の考慮がないため、全方向での近傍検出によって候補を抽出した後に、関心がある方向に沿ったデータのみを取り出すという２段階の処理が必要であるからである。方向によって関心の高さの違いが大きい（ある方向に沿った距離の重みと、他の方向の距離の重みの差が非常に大きい時）ほど、近傍検出した候補の数が膨大になるため、計算時間の削減効果はあまり期待できなくなってしまう。

　本発明の目的は、特徴の違いが、距離として定義された空間内での近傍検出において、任意の類似度判定基準（任意の方向と、任意の距離の重要度）を指定して、近傍データを高速に検出する類似性検出装置及び指向性近傍検出方法を提供することにある。

　本発明による類似性検出装置は、乱数発生部と初期化部とデータ登録部と検索部とデータ処理部とを備えている。その乱数発生部は、入力装置を介して入力された複数の方向パラメータと複数の強度パラメータとに基づいて複数の乱数情報を算出する。その複数の方向パラメータは、ユークリッド空間上の方向を示している。その初期化部は、その複数の乱数情報に基づいて複数のキー計算関数を算出する。そのデータ登録部は、入力装置を介して入力された複数の検索対象データに基づいて、その複数のキー計算関数に対応する複数のテーブルを算出し、その複数のテーブルをテーブル保持装置に記録する。その複数の検索対象データは、それぞれ、そのユークリッド空間上の点を示している。その複数の検索対象データのうちの任意の２つの検索対象データがそれぞれ示している２つの点の距離は、その２つの検索対象データの類似度を示している。その複数のテーブルのうちの任意のキー計算関数に対応するテーブルは、複数のキーを複数のデータリストに対応付け、その複数のデータリストのうちの任意のキーに対応するデータリストに属するデータがその任意のキー計算関数に代入されることにより算出される値がその任意のキーに等しくなるように算出される。その検索部は、その複数のテーブルを参照して、入力装置を介して入力された検索条件が示しているクエリに基づいて候補データリストを算出する。その候補データリストは、その複数のキー計算関数に対応する複数の検索データリストを含んでいる。その複数の検索データリストのうちのその任意のキー計算関数に対応する検索データリストは、その複数のデータリストのうちの、そのクエリがそのキー計算関数に代入されることにより算出されるクエリ値に対応するデータリストを示している。そのデータ処理部は、その候補データリストに属する複数の検索データからその検索条件が示している条件を満足する検索結果データを算出し、その検索結果データを出力装置に出力する。

　本発明による指向性近傍検出方法では、入力装置を介して入力された複数の方向パラメータと複数の強度パラメータとに基づいて複数の乱数情報を算出する。また、その複数の乱数情報に基づいて複数のキー計算関数を算出する。また、入力装置を介して入力された複数の検索対象データに基づいて、その複数のキー計算関数に対応する複数のテーブルを算出する。また、その複数のテーブルをテーブル保持装置に記録する。また、その複数のテーブルを参照して、入力装置を介して入力された検索条件が示しているクエリに基づいて候補データリストを算出する。また、その候補データリストに属する複数の検索データからその検索条件が示している条件を満足する検索結果データを算出する。また、その検索結果データを出力装置に出力する。その複数の方向パラメータは、ユークリッド空間上の方向を示している。その複数の検索対象データは、それぞれ、そのユークリッド空間上の点を示している。その複数の検索対象データのうちの任意の２つの検索対象データがそれぞれ示している２つの点の距離は、その２つの検索対象データの類似度を示している。その複数のテーブルのうちの任意のキー計算関数に対応するテーブルは、複数のキーを複数のデータリストに対応付け、その複数のデータリストのうちの任意のキーに対応するデータリストに属するデータがその任意のキー計算関数に代入されることにより算出される値がその任意のキーに等しくなるように算出される。その候補データリストは、その複数のキー計算関数に対応する複数の検索データリストを含んでいる。その複数の検索データリストのうちのその任意のキー計算関数に対応する検索データリストは、その複数のデータリストのうちの、そのクエリがそのキー計算関数に代入されることにより算出されるクエリ値に対応するデータリストを示している。

　第１の効果は、膨大なデータの中で、あるクエリ点からある興味方向に沿った自由度の高い近傍点の検出が行えることである。その理由は、任意の２点が、任意の興味の方向に沿った任意の距離重み（重要度）で測った距離が短いほど高い確率で同じエントリに登録されるテーブルを具備するデータ管理機能を提供することで、指向性近傍検出機能を実現するからである。

　第２の効果は、指向性近傍検索処理の高速化である。その理由は、事前に所望の指向性を登録した複数のテーブルにデータを登録しておくことで、クエリ点からの指向性近傍検索に当たって、クエリ点と同じエントリに登録されたデータのみを扱えば良く、全てのデータとの距離を計算する必要がないためオンライン処理時間が大幅に短縮化されるからである。

図１は、本発明による類似性検出装置を示すブロック図である。 図２は、テーブル管理装置を示すブロック図である。 図３は、初期化動作を示す流れ図である。 図４は、検索動作を示す流れ図である。 図５は、指向パラメータの例を示す表である。 図６は、指向パラメータに対応する衝突確率等値線を示すグラフである。 図７は、指向パラメータの例を示す表である。 図８は、複数のテーブルセットの例を示す表である。 図９は、複数の指向パラメータに対応する複数の衝突確率等値線を示すグラフである。 図１０は、画像を示す図である。 図１１は、複数の検索対象データ示すグラフである。 図１２は、複数のテーブルセットの例を示す表である。 図１３は、検索条件のクエリの例を示すグラフである。 図１４は、検索結果データの例を示すグラフである。 図１５は、複数の時系列データを示すグラフである。 図１６は、複数の時系列データのうちの複数の検索対象データを示すグラフである。 図１７は、複数の衝突確率等値線を示すグラフである。 図１８は、他の複数の衝突確率等値線を示すグラフである。 図１９は、衝突確率分布を示すグラフである。 図２０は、他の衝突確率分布を示すグラフである。 図２１は、特徴分布を示すグラフである。 図２２は、移動体管理システムを示すブロック図である。 図２３は、複数のテーブルセットを示す表である。

　図面を参照して、本発明による類似性検出装置の実施の形態を説明する。その類似性検出装置１は、図１に示されているように、複数のコンピュータが互いに双方向に情報を伝送することができるように接続されている。

　その複数のコンピュータの各コンピュータは、図示されていないが、ＣＰＵと、記憶装置と、インターフェースとを備えている。

　そのＣＰＵは、そのコンピュータにインストールされているコンピュータプログラムを実行することにより、その記憶装置とそのインターフェースとを制御する。

　その記憶装置は、そのコンピュータプログラムを記録し、そのＣＰＵにより作成される情報を一時的に記録する。

　そのインターフェースは、そのコンピュータに接続されている外部機器により生成される情報をそのＣＰＵに出力したり、そのＣＰＵにより生成された情報をその外部機器に出力したりする。

　その外部機器としては、入力装置、出力装置、通信装置、リムーバルメモリドライブが例示される。

　その入力装置は、ユーザに操作されることにより情報を作成し、その情報をそのＣＰＵに出力する。その入力装置としては、キーボード、ポインティングデバイス、タッチパネルが例示される。

　その出力装置は、そのＣＰＵにより生成される情報をユーザに認識可能に出力する。その出力装置としては、ディスプレイ、音響装置、タッチパネルが例示される。

　その通信装置は、通信ネットワークを介してそのＣＰＵにより作成された情報を他のコンピュータに送信し、その通信ネットワークを介して他のコンピュータから受信された情報をそのＣＰＵに出力する。その通信装置は、更に、そのコンピュータにインストールされるコンピュータプログラムを他のコンピュータからダウンロードすることに利用される。

　そのリムーバルメモリドライブは、記録媒体が挿入されたときに、その記録媒体に記録されているデータを読み出すことに利用される。そのリムーバルメモリドライブは、更に、コンピュータプログラムが記録されている記録媒体が挿入されたときに、そのコンピュータプログラムをそのコンピュータにインストールするときに利用される。その記録媒体としては、磁気ディスク（フレキシブルディスク、ハードディスク）、光ディスク（ＣＤ、ＤＶＤ）、光磁気ディスク、フラッシュメモリが例示される。

　その複数のコンピュータは、パラメータ管理装置２と、乱数発生装置３と、テーブル管理装置５と、データ処理装置６とを含んでいる。

　パラメータ管理装置２は、入力装置７を備えている。パラメータ管理装置２は、入力装置７を介してパラメータリスト８がパラメータ管理装置２に入力されるように、入力装置７を制御する。

　乱数発生装置３は、テーブル管理装置５から乱数情報を要求されたときに、テーブル管理装置５から出力された情報に基づいて乱数情報を算出する。

　テーブル管理装置５は、テーブル保持装置１０と、入力装置１１とを備えている。テーブル管理装置５は、入力装置１１を介して入力データ１２がテーブル管理装置５に入力されるように、入力装置１１を制御する。テーブル管理装置５は、入力データ１２と乱数発生装置３により算出された乱数情報とに基づいて複数のテーブルを算出する。テーブル管理装置５は、その複数のテーブルがテーブル保持装置１０に記録されるように、テーブル保持装置１０を制御する。テーブル管理装置５は、更に、データ処理装置６からデータリストを要求されたときに、その複数のテーブルを参照して、データ処理装置６から出力された情報に基づいてデータリストを算出し、そのデータリストをデータ処理装置６に出力する。

　データ処理装置６は、入力装置１４と、出力装置１５とを備えている。データ処理装置６は、入力装置１４を介して検索条件１６がデータ処理装置６に入力されるように、入力装置１４を制御する。検索条件１６は、クエリと条件とを示している。データ処理装置６は、更に、そのクエリをテーブル管理装置５に出力することにより、テーブル管理装置５にデータリストを要求する。データ処理装置６は、その条件とテーブル管理装置５により算出されたデータリストとに基づいて検索結果データを算出する。その検索結果データは、そのデータリストが示すデータのうちのその条件を満足するデータを示している。データ処理装置６は、更に、テーブル管理装置５により算出された検索結果データがユーザに認識可能に表現されるように、出力装置１５を制御する。

　図２は、テーブル管理装置５を示している。テーブル管理装置５にインストールされるコンピュータプログラムは、テーブル管理装置５に複数の機能をそれぞれ実現させる複数のコンピュータプログラムから形成されている。

　テーブル管理装置５にその複数の機能をそれぞれ実現させた場合、テーブル管理装置５は、乱数情報取得部２１と、初期化部２２と、データ登録部２３と、検索部２４とを含んでいる。

　乱数情報取得部２１は、パラメータ管理装置２に入力されたパラメータリスト８をパラメータ管理装置２から収集する。パラメータリスト８は、テーブルパラメータと管理パラメータと指向パラメータとを示している。そのテーブルパラメータは、テーブルの面数Ｐとウィンドウ幅Ｗと基数Ｃとビット長Ｂとを示している。面数Ｐは、正の整数を示している。ウィンドウ幅Ｗは、正の実数を示している。基数Ｃは、２以上の整数を示している。ビット長Ｂは、正の整数を示している。その管理パラメータは、次元数Ｄを示している。その指向パラメータは、集合Ｕを示している。

　集合Ｕは、指向パラメータｕ_ｊから形成され、以下の式により表現される。
　Ｕ＝｛ｕ_ｊ｜ｕ_ｊ∈Ｒ^Ｄ×Ｒ_＋｝（ｊ＝１，・・・，Ｄ）
　ここで、集合Ｒ^Ｄは、Ｄ次元数ベクトル空間を示している。例えば、集合Ｒ^２は、２次元数ベクトル空間を示している。

　集合Ｒ_＋は、正の実数の集合を示している。すなわち、指向パラメータｕ_ｊは、以下の式により表現される。
　ｕ_ｊ＝＜ｖ_ｊ，σ_ｊ＞
　ここで、方向パラメータｖ_ｊは、Ｄ次元のベクトルを示している。強度パラメータσ_ｊは、正の実数であり、方向パラメータｖ_ｊを重視する程度を示している。

　乱数情報取得部２１は、パラメータリスト８のうちのウィンドウ幅Ｗとビット長Ｂと次元数Ｄと集合Ｕとを乱数発生装置３に出力することにより、乱数発生装置３に乱数情報を要求する。乱数情報取得部２１は、乱数発生装置３により算出された乱数情報を乱数発生装置３から収集する。乱数情報取得部２１は、その要求をＰ回繰り返すことにより、複数（Ｐ個）の乱数情報を乱数発生装置３から収集し、乱数情報集合Ｚを作成する。

　乱数情報集合Ｚは、以下の式により表現される。
　Ｚ＝｛Ｚ_ｐ｝（ｐ＝１，・・・，Ｐ）
　ここで、集合Ｚ_ｐは、乱数発生装置３により算出された１つの乱数情報を示している。

　集合Ｚ_ｐは、以下の式により表現される。
　Ｚ_ｐ＝｛Ｚ_ｂ｜Ｚ_ｂ＝＜Φ^（ｐ） _ｂ，Ｒ^（ｐ） _ｂ＞｝（ｂ＝１，・・・，Ｂ）
　ここで、乱数Ｒ^（ｐ） _ｂは、一様分布Ｕ［０，Ｗ］に従う乱数を示している。ランダムベクトルΦ^（ｐ） _ｂは、Ｄ次元のベクトルを示している。

　ランダムベクトルΦ^（ｐ） _ｂは、以下の式により表現される。
　Φ^（ｐ） _ｂ＝ＶΛ^－１／２Ａ_ｂ

　行列Ｖは、以下の式により表現される。
　Ｖ＝（ｖ_１，・・・，ｖ_Ｄ）

　対角行列Λ^－１／２は、以下の式により表現される。
　Λ^－１／２＝ｄｉａｇ｛１／σ_１，・・・，１／σ_Ｄ｝

　ベクトルＡ_ｂは、Ｄ次元ベクトルであり、ベクトルＡ_ｂのｄ成分Ａ_ｂ，ｄ（ｄ＝１，・・・，Ｄ）は、正規分布Ｎ（０，１）に従う乱数を示している。

　初期化部２２は、更に、パラメータ管理装置２により収集されたパラメータリスト８と乱数情報取得部２１により収集された乱数情報とに基づいて複数（Ｐ個）のキー計算関数を算出する。その複数のキー計算関数のうちの任意の自然数ｐ（ｐ≦Ｐ）に対応するキー計算関数Ｌ^（ｐ）（ｘ）は、Ｄ次元数ベクトルｘの関数である。

　キー計算関数Ｌ^（ｐ）（ｘ）は、Ｄ次元数ベクトルｘを用いて、以下の式により表現される。
　Ｌ^（ｐ）（ｘ）＝（ｆ^（ｐ） _１（ｘ），・・・，ｆ^（ｐ） _Ｂ（ｘ））

　基本関数ｆ^（ｐ） _ｂ（ｘ）は、以下の式により表現される。

　データ登録部２３は、入力装置１１を介してテーブル管理装置５に入力データ１２が入力されるように、入力装置１１を制御する。入力データ１２は、データ集合Ｘを示している。

　データ集合Ｘは、データｘ_ｉから形成され、以下の式により表現される。
　Ｘ＝｛ｘ_ｉ｜ｘ_ｉ∈Ｒ^Ｄ｝（ｉ＝１，・・・，Ｎ）
　ここで、集合Ｒ^Ｄは、Ｄ次元数ベクトル空間を示している。自然数Ｎは、データ集合Ｘのデータｘ_ｉの要素の総数を示し、１より大きい自然数を示している。データｘ_ｉは、Ｄ次元数ベクトルを示している。

　データ登録部２３は、更に、入力データ１２と初期化部２２により算出された複数のキー計算関数とに基づいて、複数（Ｐ個）のテーブルを作成する。その複数のテーブルのうちの任意の自然数ｐに対応するテーブルは、複数のエントリから形成されている。そのテーブルは、その複数のエントリの各エントリが１つのキーと１つのバリューとのペア（組）を示すことにより、複数のキーを複数のバリューに対応付けている。すなわち、その複数のキーのうちの任意のキーは、その複数のバリューのうちの１つのバリューに対応している。

　その複数のキーのうちの任意のキーは、初期化部２２により算出された複数のキー計算関数のうちの任意の自然数ｐに対応するキー計算関数Ｌ^（ｐ）（ｘ）に、データ集合Ｘのうちのいずれかのデータｘが代入されることにより算出された値を示している。更に、その複数のキーは、互いに異なり、データ集合Ｘに属する全てのデータｘがキー計算関数Ｌ^（ｐ）（ｘ）に代入されることによりそれぞれ算出される複数の値を含んでいる。

　その複数のバリューのうちの任意のキーＬに対応するバリューＴａｂｌｅ^（ｐ）［Ｌ］は、所定のデータの集合であるデータリストを示している。このとき、バリューＴａｂｌｅ^（ｐ）［Ｌ］は、そのデータリストに属するデータのうちの任意のデータｘがキー計算関数Ｌ^（ｐ）（ｘ）に代入されることにより算出された値がキーＬに一致するように、算出される。

　データ登録部２３は、更に、その複数のテーブルがテーブル保持装置１０に記録されるように、テーブル保持装置１０を制御する。

　検索部２４は、データ処理装置６からクエリが出力されたときに、データ登録部２３により作成された複数のテーブルを参照して、そのクエリに基づいてデータリストを算出する。すなわち、検索部２４は、そのクエリｑに基づいてその複数のテーブルに対応する複数の検索キーを算出する。その複数の検索キーのうちの自然数ｐに対応する検索キーＬ^（ｐ）（ｑ）は、初期化部２２により算出された複数のキー計算関数のうちの自然数ｐに対応するキー計算関数Ｌ^（ｐ）（ｘ）にクエリｑが代入されることにより算出された値を示している。

　検索部２４は、データ登録部２３により作成された複数のテーブルを参照して、その複数の検索キーに基づいてデータリストＬｉｓｔ＜ｘ＞を算出する。データリストＬｉｓｔ＜ｘ＞は、データ集合Ｘに属するデータのうちの所定のデータの集合を示している。データリストＬｉｓｔ＜ｘ＞は、その複数のテーブルのうちの自然数ｐに対応するテーブルがキーＬ^（ｐ）（ｑ）に対応するエントリを含むときに、そのエントリが示すバリューＴａｂｌｅ^（ｐ）［Ｌ］が示すデータリストに属するデータを含むように、算出される。

　このとき、データ処理装置６は、検索条件１６と検索部２４により算出されたデータリストＬｉｓｔ＜ｘ＞とに基づいて検索結果データｘ_＊を算出する。検索結果データｘ_＊は、データリストＬｉｓｔ＜ｘ＞に属するデータのうちの検索条件１６が示す条件が満足するデータの集合を示している。データ処理装置６は、更に、検索結果データｘ_＊が表示されるように、出力装置１５を制御する。

　本発明による指向性近傍検出方法の実施の形態は、類似性検出装置１により実行され、初期化動作とデータ登録動作と検索動作とを備えている。

　図３は、その初期化動作を示している。ユーザは、まず、パラメータリスト８を用意し、入力装置７を操作することにより、パラメータリスト８をパラメータ管理装置２に入力する。パラメータ管理装置２は、入力装置７を介してパラメータリスト８が入力されると、パラメータリスト８を記憶装置に記録する。テーブル管理装置５は、パラメータ管理装置２に入力されたパラメータリスト８をパラメータ管理装置２から取得する（ステップＳ１）。

　パラメータリスト８は、テーブルパラメータと管理パラメータと指向パラメータとを示している。そのテーブルパラメータは、テーブルの作成に必要である情報を示し、すなわち、テーブルの面数Ｐとウィンドウ幅Ｗと基数Ｃとビット長Ｂとを示している。面数Ｐは、正の整数を示している。ウィンドウ幅Ｗは、正の実数を示している。基数Ｃは、２以上の整数を示している。ビット長Ｂは、正の整数を示している。その管理パラメータは、その他管理運用に必要である情報を示し、すなわち、次元数Ｄを示している。その指向パラメータは、特徴検出の方向や距離の重み情報を含み、近傍検出における指向性を表現し、集合Ｕを示している。

　集合Ｕは、指向パラメータｕ_ｊから形成され、以下の式により表現される。
　Ｕ＝｛ｕ_ｊ｜ｕ_ｊ＝＜ｖ_ｊ，σ_ｊ＞｝（ｊ＝１，・・・，Ｄ）
　ここで、方向パラメータｖ_ｊは、Ｄ次元のベクトルを示している。強度パラメータσ_ｊは、正の実数であり、方向パラメータｖ_ｊを重視する程度を示している。

　テーブル管理装置５は、テーブル面番号ｐに１を代入する（ステップＳ２）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐの大小関係を算出する（ステップＳ３）。

　テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きくないときに（ステップＳ３、ｐ≦Ｐ）、パラメータリスト８のうちのウィンドウ幅Ｗとビット長Ｂと次元数Ｄと集合Ｕとを乱数発生装置３に出力することにより、乱数発生装置３に乱数情報を要求する。乱数発生装置３は、テーブル管理装置５から乱数情報を要求されたときに、ウィンドウ幅Ｗとビット長Ｂと次元数Ｄと集合Ｕとに基づいて、集合Ｚ_ｐを示す乱数情報を算出する。

　集合Ｚ_ｐは、要素Ｚ_ｂから形成され、以下の式により表現される。
　Ｚ_ｐ＝｛Ｚ_ｂ｜Ｚ_ｂ＝＜Φ^（ｐ） _ｂ，Ｒ^（ｐ） _ｂ＞｝（ｂ＝１，・・・，Ｂ）
　ここで、乱数Ｒ^（ｐ） _ｂは、一様分布Ｕ［０，Ｗ）に従う乱数を示し、Ｂ回の独立な試行により生成される。ランダムベクトルΦ^（ｐ） _ｂは、Ｄ次元のベクトルを示している。

　ランダムベクトルΦ^（ｐ） _ｂは、以下の式により表現される。
　Φ^（ｐ） _ｂ＝ＶΛ^－１／２Ａ_ｂ

　行列Ｖは、以下の式により表現される。
　Ｖ＝（ｖ_１，・・・，ｖ_Ｄ）

　対角行列Λ^－１／２は、以下の式により表現される。
　Λ^－１／２＝ｄｉａｇ｛１／σ_１，・・・，１／σ_Ｄ｝

　ベクトルＡ_ｂは、Ｄ次元ベクトルであり、ベクトルＡ_ｂのｄ成分Ａ_ｂ，ｄ（ｄ＝１，・・・，Ｄ）は、正規分布Ｎ（０，１）に従う乱数を示している。ベクトルＡ_ｂの全ての成分は、それぞれ、独立な試行により生成される。テーブル管理装置５は、乱数発生装置３により算出された乱数情報を乱数発生装置３から収集する（ステップＳ４）。

　テーブル管理装置５は、その乱数情報が収集された後に、テーブル面番号ｐを１だけインクリメントし、すなわち、テーブル面番号ｐが示す値に１を加算することにより算出された和をテーブル面番号ｐに代入する（ステップＳ５）。

　テーブル管理装置５は、テーブル面番号ｐをインクリメントした後に、テーブル面番号ｐが示す値と面数Ｐとの大小関係を算出する（ステップＳ３）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きくないときに（ステップＳ３、ｐ≦Ｐ）、ステップＳ４～Ｓ５を繰り返して実行する。

　テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きいときに（ステップＳ３、ｐ＞Ｐ）、乱数情報集合Ｚとパラメータリスト８と基づいて、複数（Ｐ個）のキー計算関数を算出する（ステップＳ６）。

　ここで、乱数情報集合Ｚは、ステップＳ４が繰り返し実行されることにより収集された複数（Ｐ個）の乱数情報を示している。その複数のキー計算関数のうちのテーブル面番号ｐに対応するキー計算関数Ｌ^（ｐ）（ｘ）は、Ｄ次元数ベクトルｘの関数である。

　乱数情報集合Ｚは、以下の式により表現される。
　Ｚ＝｛Ｚ_ｐ｝（ｐ＝１，・・・，Ｐ）

　キー計算関数Ｌ^（ｐ）（ｘ）は、Ｄ次元数ベクトルｘを用いて、以下の式により表現される。
　Ｌ^（ｐ）（ｘ）＝（ｆ^（ｐ） _１（ｘ），・・・，ｆ^（ｐ） _Ｂ（ｘ））
　ここで、基本関数ｆ^（ｐ） _ｂ（ｘ）は、前述の式により表現される（数１参照）。

　テーブル管理装置５は、その複数（Ｐ個）のキー計算関数が算出された後に、エントリが空の複数（Ｐ個）のテーブルを作成する（ステップＳ７）。その複数のテーブルは、その複数のキー計算関数に対応している。テーブル管理装置５は、テーブル保持装置１０を制御することにより、その複数（Ｐ個）のテーブルをテーブル保持装置１０に記録する。

　そのデータ登録動作は、その初期化動作が実行された後に実行される。ユーザは、まず、入力データ１２を用意し、入力装置１１を操作することにより、入力データ１２をテーブル管理装置５に入力する。入力データ１２は、データ集合Ｘを示している。

　データ集合Ｘは、データｘ_ｉから形成され、以下の式により表現される。
　Ｘ＝｛ｘ_ｉ｜ｘ_ｉ∈Ｒ^Ｄ｝（ｉ＝１，・・・，Ｎ）
　ここで、集合Ｒ^Ｄは、Ｄ次元数ベクトル空間を示している。自然数Ｎは、データ集合Ｘの要素であるデータｘ_ｉの総数を示し、１より大きい自然数を示している。データｘ_ｉは、Ｄ次元数ベクトルを示している。

　テーブル管理装置５は、入力装置１１を介して入力データ１２が入力されると、記憶装置を制御することにより、入力データ１２をその記憶装置に記録する。

　テーブル管理装置５は、入力装置１１を介して入力データ１２が入力されると、その初期化動作により作成された複数（Ｐ個）のテーブルに対応する複数（Ｐ個）のテーブル作成動作を実行する。その複数のテーブル作成動作のうちのテーブル面番号ｐに対応するテーブル作成動作は、データ集合Ｘに属する全てのデータに対応する複数（Ｎ個）のエントリ作成動作から形成されている。

　その複数（Ｎ個）のエントリ作成動作のうちのあるデータｘ_ｉに対応するエントリ作成動作では、テーブル管理装置５は、その初期化動作により作成された複数（Ｐ個）のキー計算関数のうちのテーブル面番号ｐに対応するキー計算関数Ｌ^（ｐ）（ｘ）にデータｘ_ｉを代入することによりキーＬ^（ｐ）（ｘ_ｉ）を算出する。テーブル管理装置５は、その初期化動作により作成された複数（Ｐ個）のテーブルのうちのテーブル面番号ｐに対応するテーブルに、キーＬ^（ｐ）（ｘ_ｉ）に対応するエントリが存在しているかどうかを判別する。

　テーブル管理装置５は、そのテーブルにキーＬ^（ｐ）（ｘ_ｉ）に対応するエントリが存在するときに、そのエントリのバリューＴａｂｌｅ^（ｐ）［Ｌ^（ｐ）（ｘ_ｉ）］が示すデータリストにデータｘ_ｉを追加する。テーブル管理装置５は、そのテーブルにキーＬ^（ｐ）（ｘ_ｉ）に対応するエントリが存在しないときに、キーＬ^（ｐ）（ｘ_ｉ）に対応するエントリをそのテーブルに追加する。このとき、そのエントリのバリューＴａｂｌｅ^（ｐ）［Ｌ^（ｐ）（ｘ_ｉ）］は、データｘ_ｉのみを要素とするデータリストを示している。

　テーブル管理装置５は、その複数（Ｎ個）のエントリ作成動作の全てを実行することにより、その複数（Ｐ個）のテーブルのうちのテーブル面番号ｐに対応するテーブルを作成する。テーブル管理装置５は、その複数（Ｐ個）のテーブル作成動作の全てを実行することにより、その複数（Ｐ個）のテーブルの全てを作成する。テーブル管理装置５は、テーブル保持装置１０を制御することにより、その複数のテーブルをテーブル保持装置１０に記録する。

　このように作成されたテーブルでは、任意の２つのデータに対応する２つのキーがそれぞれ示す任意の２点が、指向パラメータｕ_ｊが示す方向に沿った任意の距離重み（重要度）で測った距離が短いほど高い確率で同じエントリに登録される。

　図４は、その検索動作を示している。ユーザは、まず、検索条件１６を用意し、入力装置１４を操作することにより、検索条件１６をデータ処理装置６に入力する。検索条件１６は、クエリｑと条件とを示している。その条件としては、「クエリｑの最近傍のデータを１つ取得する」「クエリｑに近いものからＫ個のデータを取得する」が例示される。データ処理装置６は、入力装置１４を介して検索条件１６が入力されると、記憶装置を制御することにより、検索条件１６をその記憶装置に記録する（ステップＳ１１）。データ処理装置６は、検索条件１６が入力されると、更に、クエリｑをテーブル管理装置５に出力することにより、テーブル管理装置５にデータリストを要求する（ステップＳ１２）。

　テーブル管理装置５は、データ処理装置６からクエリｑが出力されると、テーブル面番号ｐに１を代入し、空のデータリストＬｉｓｔ＜ｘ＞＝φを用意する（ステップＳ１３）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐの大小関係を算出する（ステップＳ１４）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きくないときに（ステップＳ１４、ｐ≦Ｐ）、クエリｑに基づいて検索キーＬ^（ｐ）（ｑ）を算出する（ステップＳ１５）。

　検索キーＬ^（ｐ）（ｑ）は、その初期化動作により算出された複数のキー計算関数のうちのテーブル面番号ｐに対応するキー計算関数Ｌ^（ｐ）（ｘ）にクエリｑが代入されることにより算出される値を示している。

　テーブル管理装置５は、そのデータ登録動作により作成された複数のテーブルのうちのテーブル面番号ｐに対応するテーブルを参照して、検索キーＬ^（ｐ）（ｑ）に対応するバリューＴａｂｌｅ^（ｐ）［Ｌ^（ｐ）（ｑ）］を取得する（ステップＳ１６）。テーブル管理装置５は、バリューＴａｂｌｅ^（ｐ）［Ｌ^（ｐ）（ｑ）］が示すデータリストに属するデータをデータリストＬｉｓｔ＜ｘ＞に追加する（ステップＳ１７）。

　ここで、テーブル管理装置５は、データリストＬｉｓｔ＜ｘ＞とバリューＴａｂｌｅ^（ｐ）［Ｌ^（ｐ）（ｑ）］とに重複して属するデータがあった場合に、バリューＴａｂｌｅ^（ｐ）［Ｌ^（ｐ）（ｑ）］が示すデータのうちのデータリストＬｉｓｔ＜ｘ＞に登録されていないデータのみをデータリストＬｉｓｔ＜ｘ＞に追加する。

　テーブル管理装置５は、ステップＳ１７が実行された後に、テーブル面番号ｐを１だけインクリメントし、すなわち、テーブル面番号ｐが示す値に１を加算することにより算出された和をテーブル面番号ｐに代入する（ステップＳ１８）。テーブル管理装置５は、テーブル面番号ｐをインクリメントした後に、テーブル面番号ｐが示す値と面数Ｐとの大小関係を算出する（ステップＳ１４）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きくないときに（ステップＳ１４、ｐ≦Ｐ）、ステップＳ１５～Ｓ１８を繰り返して実行する。

　テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きいときに（ステップＳ１４、ｐ＞Ｐ）、データリストＬｉｓｔ＜ｘ＞をデータ処理装置６に出力する。こうして出来上がったデータリストＬｉｓｔ＜ｘ＞は、クエリｑの特定方向を適当な重みで重要視して距離計算した時に近距離となるデータの候補となっている。

　データ処理装置６は、テーブル管理装置５によりデータリストＬｉｓｔ＜ｘ＞が出力されると、検索条件１６が示す条件とデータリストＬｉｓｔ＜ｘ＞とに基づいて検索結果データｘ_＊を算出する（ステップＳ１９）。

　検索結果データｘ_＊は、データリストＬｉｓｔ＜ｘ＞に属するデータのうちのその条件が満足するデータの集合を示している。もし、その条件が「クエリｑに近いものからＫ個のデータを取得する」を示し、データリストＬｉｓｔ＜ｘ＞がＫ個以下のデータしか含まない場合には、検索結果データｘ_＊は、データリストＬｉｓｔ＜ｘ＞の全てのデータを示している。なお、データリストＬｉｓｔ＜ｘ＞からクエリｑに近いデータを選択する計算としては、普通のユークリッド距離を用いても良いし、指向パラメータで指定した重要度を考慮して距離を計算しても良い。

　データ処理装置６は、検索結果データｘ_＊が算出された後に、出力装置１５を制御することにより、検索結果データｘ_＊を出力装置１５に表示させる（ステップＳ２０）。

　このような指向性近傍検出方法によれば、ユーザが興味の方向やその度合い等を示す関心情報を考慮して指向パラメータを設定しておくことで、類似性検出装置１は、高次元データにおいても、その関心に沿った中で、関心中心から近いデータを高速に優先的選択する指向性近傍検出が可能である。

　既存手法では、同じ距離（類似度）にあるデータは同じ確率で選択するため、ある検索中心から同心球上の点は、全て同じ確率で検出される。そのため、ある興味方向にある距離ｒのデータだけを取り出すには、一度半径ｒの球内にあるデータを全て選択し、そこからある方向のみのものを優先的に取り出す必要がある。このような手法では、指向性が強くなるほど（ある方向の重要度の重みが他の方向の重要度の重みに比べて大きくなるほど）、不必要なデータを大量に取得しなければならず、その分計算時間が増大する。

　それに対して、本発明による技術では、衝突確率等値線が等方的な球ではなく、衝突確率等値線が興味方向に長軸をもつ楕円体として制御できるため、任意の方向に任意の重みで指向性近傍検出を行うことが可能となり大幅な時間削減が望める。

　なお、類似性検出装置１は、データ処理装置６が、乱数情報取得部２１と初期化部２２とデータ登録部２３と検索部２４とがそれぞれ実現される複数のコンピュータに置換されることができる。更に、類似性検出装置１は、パラメータ管理装置２と乱数発生装置３とテーブル管理装置５とデータ処理装置６とが実現される１つのコンピュータに置換されることもできる。更に、パラメータ管理装置２と乱数発生装置３とデータ処理装置６と乱数情報取得部２１と初期化部２２とデータ登録部２３と検索部２４とのいずれかが実現される複数のコンピュータから形成されることもできる。このように置換された類似性検出装置も、類似性検出装置１と同様にして、任意の方向に任意の重みで指向性近傍検出を行うことが可能となる。

　次に、本発明による指向性近傍検出方法が二次元（Ｄ＝２）ユークリッド空間に適用される例を考える。例えば、図５に示されているように、集合Ｕが複数の指向パラメータ３６を複数の方向パラメータ３７と複数の強度パラメータ３８とに対応付けている例を考える。

　複数の指向パラメータ３６は、２つの指向パラメータｕ_１，_ｕ２から形成されている。複数の方向パラメータ３７は、（１／ｓｑｒｔ（２）、１／ｓｑｒｔ（２））を示す方向パラメータｖ_１と（－１／ｓｑｒｔ（２）、１／ｓｑｒｔ（２））を示す方向パラメータｖ_２とから形成されている。複数の強度パラメータ３８は、２を示す強度パラメータσ_１と１を示す強度パラメータσ_１とから形成されている。指向パラメータｕ_１は、方向パラメータｖ_１を強度パラメータσ_１に対応付けている。指向パラメータｕ_２は、方向パラメータｖ_２を強度パラメータσ_２に対応付けている。

　すなわち、集合Ｕは、以下の式により表現される。
　Ｕ＝｛＜（１／ｓｑｒｔ（２）、１／ｓｑｒｔ（２））、２＞、＜（－１／ｓｑｒｔ（２）、１／ｓｑｒｔ（２））、１＞｝

　このとき、方向パラメータｖ_１は、図６に示されているように、ｘ軸から反時計回りに４５度傾いた方向を示している。方向パラメータｖ_２は、方向パラメータｖ_１が示す方向と直交する方向を示している。集合Ｕは、強度パラメータσ_２が示す値の２倍の値を強度パラメータσ_１が示すことから、方向パラメータｖ_１の方向を方向パラメータｖ_２の方向に比べて２倍重視することを意味する。

　入力データ１２は、集合Ｘに属するデータの分布が任意とする。検索条件１６の条件としては、「クエリｑの入力に対して、クエリｑとの距離が最も近いデータである」ことを示す。

　このとき、衝突確率等値線３１は、方向パラメータｖ_１の方向に長軸をもつ楕円に形成される。すなわち、衝突確率等値線３１の上のデータは、全て同じ確率で検出される。類似性検出装置１は、方向パラメータｖ_２の方向に比べ、方向パラメータｖ_１の方向に２倍遠い場所を同一視して、集合Ｘに属するデータから検索結果データを検索することができる。すなわち、類似性検出装置１は、検出確率を制御することができるため、方向パラメータｖ_１の方向に強度パラメータσ_１の重みで指向性近傍検出を行うことが可能となる。

　本発明による類似性検出装置の第２の実施の形態は、既述の実施の形態に記載されたパラメータリスト８が示す指向パラメータが他の指向パラメータに置換されている。

　その指向パラメータは、集合Ｕ_ｋから形成される集合を示し、その集合は、以下の式により表現される。
　｛Ｕ_ｋ｝（ｋ＝１，・・・，Ｋ）

　集合Ｕ_ｋは、以下の式により表現される。
　Ｕ_ｋ＝｛ｕ_ｊ｜ｕ_ｊ∈Ｒ^Ｄ×Ｒ_＋｝（ｊ＝１，・・・，Ｄ）
　このとき、集合Ｕ_ｋは、互いに異なる。すなわち、方向パラメータｖ又は強度パラメータσのどれかが異なっている。

　例えば、簡単のためＤ＝２の２次元の場合を考えると、集合Ｕ_ｋは、以下の式により表現される。
　Ｕ_ｋ＝｛＜ｖ_ｘ，σ_ｘ２^ｐ＞、＜ｖ_ｙ，σ_ｙ２^ｐ＞｝
　ここで、方向パラメータｖ_ｘは、ｘ軸方向の単位ベクトルを示している。方向パラメータｖ_ｙは、ｙ軸方向の単位ベクトルを示している。変数ｐは、０以上の整数を示している。強度パラメータσ_ｘは、ｘ軸方向の基本重みを示している。強度パラメータσ_ｙは、ｙ軸方向の基本重みを示している。

　例えば、指向パラメータＵとしては、図７に示されているように、ｐ＝０，１，２，３の４通りとし、（σ_ｘ，σ_ｙ）＝（１，３）、（３，１）の２通りとすると、Ｋ＝２×４＝８通りの指向パラメータ集合Ｕ_ｋが指定される。

　このとき、その類似性検出装置は、その指向パラメータに基づいて、その指向パラメータが示す集合Ｕに属する複数の集合に対応する複数のキー計算関数集合を作成する。その複数のキー計算関数集合のうちの集合Ｕ_ｋに対応するキー計算関数集合は、複数のキー計算関数を示している。その複数のキー計算関数は、既述の実施の形態における類似性検出装置１により集合Ｕに基づいて算出される複数のキー計算関数と同様にして、集合Ｕ_ｋに基づいて算出される。

　その類似性検出装置は、入力データ１２とその複数のキー計算関数集合とに基づいて、図８に示されているように、その複数のキー計算関数集合５２に対応する複数のテーブルセット５１を作成する。複数のテーブルセット５１の任意のテーブルセットは、複数のテーブルから形成されている集合を示している。

　その複数のテーブルは、既述の実施の形態における複数のテーブルと同様にして、作成されている。すなわち、その複数のテーブルのうちの任意のテーブル面番号ｐに対応するテーブルは、複数のキーを複数のバリューに対応付けている。

　その複数のキーのうちの任意のキーは、その複数のキー計算関数のうちのテーブル面番号ｐに対応するキー計算関数Ｌ^（ｐ）（ｘ）に、データ集合Ｘのうちのいずれかのデータｘが代入されることにより算出された値を示している。

　その複数のバリューのうちの任意のキーＬに対応するバリューＴａｂｌｅ^（ｐ）［Ｌ］は、所定のデータの集合であるデータリストを示している。このとき、バリューＴａｂｌｅ^（ｐ）［Ｌ］は、そのデータリストに属するデータのうちの任意のデータｘがキー計算関数Ｌ^（ｐ）（ｘ）に代入されることにより算出された値がキーＬに一致するように、算出される。

　図９は、集合Ｕ_ｋが指定する指向性をそれぞれ示す複数の衝突確率等値線を示している。その複数の衝突確率等値線は、それぞれ、方向パラメータの方向に長軸をもつ楕円に形成され、互いに異なっている。

　その複数の衝突確率等値線のうちの集合Ｕ_ｋに対応する衝突確率等値線の上のデータは、図６に示される衝突確率等値線３１と同様にして、複数のテーブルセット５１のうちの集合Ｕ_ｋに対応するテーブルセットが示す複数のテーブルを用いて、全て同じ確率で検出される。その類似性検出装置は、既述の最良の実施の形態で述べた方法と同様に、それぞれの指向パラメータに対応するテーブルを指定された面数だけ作成したテーブルを作成・管理する。

　ユーザは、その検索動作の際に、検索条件１６と異なる他の検索条件をその類似性検出装置に入力する。

　その検索条件は、指向性パラメータと検索条件１６が示すクエリと条件とを示している。その指向性パラメータは、方向と強度のペアの集合を示している。その類似性検出装置は、複数のテーブルセット５１からその指向性パラメータに一番近い指向パラメータを示す集合Ｕ_ｋに対応するテーブルセットを選択する。その類似性検出装置は、そのテーブルセットに属する複数のテーブルを用いて複数の検索データリストを算出し、データリストＬｉｓｔ＜ｘ＞を算出する。

　その複数の検索データリストのうちのあるテーブルセットに対応する検索データリストは、そのテーブルセットの複数のバリューのうちのクエリのキーに対応するバリューが示すデータリストに一致している。データリストＬｉｓｔ＜ｘ＞は、その複数のテーブルセットに対応する複数の検索データリストを含んでいる。

　このような第２の実施の形態における類似性検出装置は、予め複数のテーブルセットを作成し、検索に合わせて利用するテーブルを選択する機能が設けられていることにより、事前に指向性パラメータが不明な場合でも、検索動作時に「この点のこちらの方向にこれくらいの強さで」という指向性パラメータを合わせて入力することで、指向性近傍検索が可能となる。

　なお、ここでは、８通りのみの指向性パラメータを持つテーブルを用意する例を示したが、一般には、もっと多くても良く、様々な方向や強度の組み合わせを用意しておくほど様々な検索要求に対して精度良い出力を返すことができる。そのテーブルセットの個数は、計算資源等とのトレードオフで決めれば良い。

　また、検索の指向性パラメータの指定として、この例では、検索者が指向性パラメータＵの書式（方向と強度のペアの集合）で入力するとしたが、これは、より直感的な入力を定義しデータ処理装置において指向性パラメータの書式に変換しても良い。

　より直感的な入力の例として、関心のない軸方向の単位長さと同一視する関心がある方向にそった長さを指定することで、検索の指向性を指定することも可能である（例えばｘ軸から４５°傾いた方向に沿った長さ１は、ｘ軸から－４５°傾いた方向に沿った長さ３に相当する場合は、ｘ軸から－４５°傾いた方向は４５°傾いた方向より実距離で３倍遠くても同じ確率で検出することになる）。

　更に、本例では、検索における指向性情報に対して、最適なテーブルを一つ選択して結果を出力する例を記載したが、複数のテーブルを組み合わせた指向性近傍検索結果を出力しても良い。具体的には、例えば、検索に指定された指向性情報と、テーブルの持つ指向性情報との距離を用いて、その重みで、各テーブルで行った近傍検索結果を表示しても良い。

　本発明による指向性近傍検出方法における第２の実施例について詳細に説明する。本実施例では、ある特徴に関して類似する画像を高速検出する手法について説明する。

　画像を示す画像データは、一般に、Ｄ次元特徴ベクトルで表現することが可能である。様々な手法が考えられるが、ここでは、一例として、図１０に示されているように、画像６１が適当なメッシュで複数の画素６２－１～６２－１６に切られており、各画素６２－ｉで画素値を定義することによって表現される画像データを考える。

　ここで、それぞれの画素における画素値をラスタ・スキャン（Ｒａｓｔｅｒ　ｓｃａｎ）して、画素値を並べることで特徴ベクトルを作成するとする。なお、ラスタ・スキャンでは、左上からはじめて、左から右に順に値を読んでいき、右端までいったら一段おりて同じことを繰り返す。

　例えば、４ｘ_４の画素に区切られた任意の画像の特徴ベクトルｕは、１６次元ベクトルで表現される。例えば、１６個の単位ベクトルｅ_１～ｅ_１６と１６個の画素値とを用いて、以下の式により表現される。

　ここで、単位ベクトルｅ_ｉは、ｉ番目の成分のみが１を示し、あとの成分が０を示すベクトルである。

　ここで、ユーザは、ある特徴方向に関してのみ興味があるとする。一番簡単には、ユーザは、画像６１のうちのある一部分である興味領域６３のみに関心があり、それ以外の類似性を無視するような場合が考えられる。その場合、ユーザは、特徴ベクトルｕの第１成分と第２成分と第５成分と第６成分とのみを重視し、他の画素を重視しないことになる。

　ここで、重視する重みを１０倍とすると（非興味方向に沿った距離の１に対して興味方向に沿った距離の１０を同一視すると）、指向性パラメータＵ＝｛ｕ_ｉ＝＜ｖ_ｉ、σ_ｉ＞｝ｉ＝１，・・・，１６をｖ_ｉ＝ｅ_ｉ、σ_ｉ＝１０（ｉ＝１，２，５，６），１（その他）と設定する。この指向性パラメータＵを用いて、既述の最良の実施の形態に示した指向性近傍検出を行うことで、あるクエリ画像ｑの入力に対して、第１、２、５，６番目の画素の類似性を重視した類似画像検索が可能である。

　更に、本発明による指向性近傍検出方法は、一般に、画素を適当な割合で組み合わせを特徴方向として類似画像の検出を行うことも可能である。例えば、第１，２，５，６番目の画素値の比率の類似性を重視する場合を考える。

　興味方向として、第１，２，５，６番目の画素を同じ重みで足し合わせた方向パラメータｖ_１を、以下の式により定義する。
　ｖ_１＝（ｅ_１＋ｅ_２＋ｅ_５＋ｅ_６）／２

　方向パラメータｖ_１は、グラム・シュミットの直交化法等を用いれば、方向パラメータｖ_１と｛ｅ_ｉ｝ｉ＝２，・・・，１６とから、互いに直交する正規直交座標系｛ｖ_１，ｖ_２，・・・，ｖ_１６｝を構成することができる。

　先の例と同様に方向パラメータｖ_１の方向を他の方向に比べて１０倍重視する場合、指向性パラメータＵをＵ＝｛ｕ_ｉ＝＜ｖ_ｉ、σ_ｉ＞｝（ｉ＝１，・・・，１６）をσ_ｉ＝１０（ｉ＝１），１（その他）と設定することにより、第１，２，５，６番目の画素値の比率が同じ画像を類似画像として検出することができる。これは、例えば画素値として色の濃さを０～１の実数値で表したときに、対象部分の濃さの比率が近ければ、対象部分以外の画素値の違いが多少大きくても類似画像として検出されることになる。

　次いで、本発明による指向性近傍検出方法における第２の実施例について詳細に説明する。本実施例では、多次元関数の局所的特徴に着目した類似関数検索を行う。典型的な例として、多次元ベクトルの集合で表現される時系列データ｛ｖ（ｔｉ）｝ｉ＝１，２，・・・を考える。

　ここで、ｖ（ｔｉ）は、時刻ｔｉにおける多次元ベクトルを示している。その時系列データとしては、ある地点で、時刻ｔｉに測定された加速度センサーのそれぞれｘ軸方向，ｙ軸方向，ｚ軸方向の加速度の値を３次元ベクトルとして表現したものが例示される。その場合、３次元ベクトル空間上における時刻をパラメータにした点の集合が時系列データとなる。

　本実施例は、大量な時系列データ（例えば、大量の地点での加速度データの時系列データ）の中で、あるクエリとなる時系列データに対して、その部分的な領域のみで類似する時系列データを高速検索する。

　図１１は、本実施例で検索対象となる複数の時系列データ７１－１～７１－Ｔを示している。ユーザは、まず、複数の時系列データ７１－１～７１－Ｔを本実施例における類似性検出装置に入力する。その類似性検出装置は、第２の実施の形態における類似性検出装置と同様にして、複数の指向パラメータに対応する複数のテーブルに時系列データの各点を順次登録する。

　ここで、その複数の指向パラメータは、簡単に、ｘ軸方向に長軸をもちｙ軸方向に短軸をもつ指向パラメータと、その長軸から９０度回転した方向に指向性をもつ他の指向パラメータとの２種類とする。指向パラメータの強度は、一般に、複数指定可能だが、ここでは、例えば３：１の比率で設定するものとする。

　その類似性検出装置は、図１２に示されているように、その複数の指向パラメータ７４に対応する複数のテーブルセット７５を作成する。ここで、複数のテーブルセット７５の各テーブルセットに属するテーブルの数は、Ｋ個とする。その類似性検出装置は、既述の実施の形態における類似性検出装置と同様にして、全てのテーブルに、時系列データの各点に対するキーを計算してバリューに登録する。

　検索のときは、ユーザは、図１３に示されているように、時系列データ７６を入力し、時系列データ７６のうちの興味領域（検索対象領域）を示す検索範囲パラメータ７７をクエリとして指定する。ここで、検索範囲パラメータ７７は、時系列データ７６の興味領域が指定できれば良い。例えば、座標値の範囲を示すデータでも良いし、各データのパラメータ（例えば、時刻ｔ等）の範囲を示すデータでも良い。また、検索範囲パラメータ７７は、時系列データ７６のなかから興味領域の範囲内のデータのみ抜き出した部分時系列データそのものでも良い。

　その類似性検出装置は、既述の実施の形態における類似性検出装置と同様にして、複数のテーブルセット７５のうちのユーザにより選択されたテーブルセットに属する複数のテーブルを参照して、図１４に示されているような時系列データ７８を抽出し、時系列データ７８がユーザ認識可能に表現されるように出力装置１５を制御する。時系列データ７８は、その複数のテーブルに対応する複数の検索データリストに含まれるデータから形成されている。その複数の検索データリストのうちのあるテーブルに対応する検索データリストは、そのテーブルに対応するキー計算関数にそのクエリが代入されることにより算出されるクエリ値に対応するバリューが示すデータリストを示している。

　本発明による指向性近傍検出方法における他の実施例について詳細に説明する。本実施例では、範囲限定類似関数検索を行うための、入力される時系列データと任意の時系列データの、その範囲を限定した類似度を判定する機能について、以下に詳細に説明する。簡単のため、ここでは、図１５に模式的に示される２次元空間における時系列データ８１に対する時系列データ８２の類似度を計算することを考える。ここで、検索範囲の限定として、両者の時系列データのうちのユーザにより指定された時間間隔［ｔｍｉｎ：ｔｍａｘ_］に属する部分のみの局所的な特徴を比較することを考える。

　時系列データ８１は、その時間間隔に属するデータとして、｛Ｓｉ｝ｉ＝１，・・・，９を有している。時系列データ８２は、その時間間隔に属するデータとして、｛Ｒ_ｉ｝ｉ＝１，・・・，６を有している。このとき、図１６に示されているように、時系列データ８１から範囲限定された部分時系列データ８３は、｛Ｓｉ｝ｉ＝１，・・・，９から形成され、時系列データ８２から範囲限定された部分時系列データ８４は、｛Ｒ_ｉ｝ｉ＝１，・・・，６から形成される。

　ここで、ユーザは、更に、部分時系列データ８３の点群｛Ｓｉ｝ｉ＝１，・・・，９から中心的な参照点８５をクエリとして抽出する。参照点８５は、部分時系列データ８３を最も良く代表する点であり、例えば全ての点の平均でも良いし、平均に一番近い点でも良いし、最大・最小値の平均（この例ではＳ１とＳ９の平均）等でも良い。

　次に、その類似性検出装置は、参照点８５と、部分時系列データ８３及び部分時系列データ８４の各点が複数のテーブルセット７５の各々に属する複数のテーブルにおいて同じエントリに登録される確率（衝突確率）を計算し、複数の指向パラメータ７４に対応する複数の衝突確率分布を算出する。その複数の衝突確率分布は、それぞれ、参照点８５から部分時系列データ８３と部分時系列データ８４とに属する各データまでの距離の関数を示している。

　図１７は、複数の指向パラメータのうちの第１指向パラメータに対応する衝突確率等値線を示している。その衝突確率等値線８６は、ｘ軸方向に長軸をもちｙ軸方向に短軸を有している。図１８は、その複数の指向パラメータのうちの第２指向パラメータに対応する衝突確率等値線を示している。その衝突確率等値線８７は、ｘ軸方向に長軸をもちｙ軸方向に短軸を有している。

　図１９は、衝突確率分布を示している。その衝突確率分布８８は、部分時系列データ８３と部分時系列データ８４とに属する各データが参照点８５とその第１指向パラメータに基づいて算出されたテーブルで同じエントリに登録される衝突確率を示している。

　図２０は、他の衝突確率分布を示している。その衝突確率分布８９は、部分時系列データ８３と部分時系列データ８４とに属する各データが参照点８５とその第２指向パラメータに基づいて算出されたテーブルで同じエントリに登録される衝突確率を示している。

　これらの値は、各指向性パラメータの全テーブル数Ｋに対して、実際に両者が衝突していた（同じエントリに登録されていた）数Ｌを測定し、Ｌ／Ｋで衝突確率を計算することで近似される。衝突確率分布８８と衝突確率分布８９とは、時系列データの各点と参照点８５の衝突確率が、両者の場所の位置関係と指向性パラメータの示す方向や強度によって異なる値を取ることを示している。衝突確率分布８８と衝突確率分布８９とは、この衝突確率分布は、比較する二つの部分時系列データが近いほど同じ形をとるため、この形の違いを比較することで任意の二つの部分時系列データの類似性を評価することが可能である。

　図２１は、特徴分布を示している。その特徴分布９０は、衝突確率分布８８と衝突確率分布８９とでの各部分時系列データの衝突確率の差を示し、各部分時系列データの特徴分布９０の形は、類似度を部分時系列データの類似度として評価されることができる。この類似度の計算には、滑らかに補間した関数間の内積を計算する方法、もしくは、Ｅ_ａｒ_ｔｈ　Ｍｏｖｅｒ_’ｓ　Ｄｉｓｔａｎｃｅのような距離評価尺度を使う方法等が考えられるが、これに限るものではなく、関数の形（ある距離が与えられた時の関数値）の類似度が定量的に評価できるものであれば良い。

　上記の手法によって、クエリで指定された時系列データに対して、指定された検索範囲に限定した時に、一番類似性の高い時系列データを抽出することが可能である。具体的には、クエリで指定された部分時系列データから参照点を計算し、複数のテーブルセット７５に属する全てのテーブルにおける参照点と衝突するデータの中で検索範囲内のもののみを抽出（本例では時間が指定された時間範囲のものを抽出）し、各時系列データに対応する衝突確率分布を作成し、クエリで指定された部分時系列データの衝突確率分布との類似性を評価すれば良い。

　ここで、本例では検索範囲の指定を連続した一つの区間としたが、一般に複数の区間で行うことも、それぞれの区間で同様の手法を適用し、各区間における類似性を合わせて評価することで容易に実現可能である。

　次に本実施例における効果を説明する。本実施例によれば、実際のクエリと範囲の入力に対して、検索対象の全ての時系列データの中から最も類似する時系列データの抽出処理を大幅に高速化することが可能である。

　なぜなら、通常の手法では、検索範囲のみを取り出した全ての部分時系列データとクエリの部分時系列データの比較をオンラインで行わなくてはいけないため、検索対象データ数が増加すると計算時間も増加し、応答速度が遅くなってしまう。

　しかし、本実施例によれば、検索対象の時系列データは予めオフラインでテーブルに登録しておくことが可能であり、オンライン処理で実際に評価が必要なのは、参照点と衝突するデータによって構成される時系列データ及びその対応する衝突確率分布のみであるからである。特に検索対象時系列データの数が膨大の時に、対象データ数の大幅な削減が期待できる。

　なお、本実施例では、時刻をパラメータとして扱ったが、例えば、時刻自体を適当に定数倍したり、時刻に適当な変換を施したりして時系列データの値と比較できる形で座標値の一つとして取り組んで検索を行うことも可能である。

　次に本発明の第三の実施例について詳細に説明する。第三の実施例では、本発明による類似性検出装置は、図２２に示されているように、移動体管理システム１００に適用されている。

　移動体管理システム１００は、ネットワーク１０３を介して、複数のコンピュータが互いに双方向に情報を伝送することができるように接続されている。ネットワーク１０３としては、インターネット、携帯電話網等が例示される。その複数のコンピュータは、移動体管理装置１０１と複数の移動体端末１０２－１～１０２－３とを含んでいる。複数の移動体端末１０２－１～１０２－３は、それぞれ、ユーザにより携帯され、現在位置情報を取得できるデバイスである。そのデバイスとしては、スマートフォンやＧＰＳロガー等が例示される。

　移動体管理装置１０１は、既述の実施の形態における類似性検出装置を備え、複数の移動体端末１０２－１～１０２－３の移動方向を管理し、似た方向に進んでいる移動体端末をグルーピングする機能を提供する。例えば、移動体管理装置１０１は、複数の移動体端末１０２－１～１０２－３の各移動体端末に関してその現在位置と適当な時間τだけ前にいた位置のペアを管理する。ここで、簡単のため扱う空間を２次元空間とし、検出したい主たる移動方向をｘ軸方向とし、ｙ軸方向に比べｘ軸方向に適当に指向性を持たせるように強度を設定した指向性パラメータを設定する。強度の例として例えば、ｘ軸方向へはｖ_τの定数倍とし、ｙ軸方向は例えばｘ軸方向の強度の０．１倍等とすることで、ｘ軸方向の強度は検出したい速度上限を規定し、ｙ軸方向は方向のぶれの許容範囲を規定することができる。

　複数の移動体端末１０２－１～１０２－３は、ある時刻ｔにそれぞれ位置１０１０，位置１０２０，位置１０３０に存在し、時刻ｔ＋τにそれぞれ位置１０１１，位置１０２１，位置１０３１に移動したとする。複数の移動体端末１０２－１～１０２－３は、ＧＰＳによって現在位置を取得し、定期的にネットワーク１０３を通して移動体管理装置１０１に位置情報をアップロードする。

　移動体管理装置１０１は、既述の実施の形態における類似性検出装置と同様にして、図２３に示されているように、複数の指向性パラメータ１１１に対応する複数のテーブルセット１１２を作成する。移動体管理装置１０１は、複数のテーブルセット１１２を用いて複数の移動体端末１０２－１～１０２－３の位置を管理し、位置１０１０，位置１０１１，位置１０２０，位置１０２１，位置１０３０，位置１０３１に対して各テーブルのキーを計算し、そのキーに対応するバリューに登録する。移動体管理装置１０１は、このテーブルセットを用いて、複数の移動体端末１０２－１～１０２－３のうちのｘ軸方向に進む移動体端末をグループ化し、そのグループの特性に関する情報を含む移動体グループ情報１０５を出力する。

　次に、移動体管理装置１０１がこの移動体グループ情報１０５を作成する手法を説明する。もし、移動体端末がｘ軸方向に想定速度程度の速度で移動していれば、時刻ｔと時刻ｔ＋τにおける位置座標は、同じキーを持つ可能性が高いが、直交するｙ軸方向に移動している移動体端末は、異なるキーを持つ可能性が高いため、両者を区別することができる。

　本実施例では、移動体端末１０２－１と移動体端末１０２－２の位置情報である位置１０１０，位置１０１１，位置１０２０，位置１０２１は、同じエントリに登録され、移動体端末１０２－３の位置情報である位置１０３０及び位置１０３１は異なるエントリに登録される可能性が高い。そのため、ｘ軸方向に同じような速度で移動している移動体端末１０２－１及び移動体端末１０２－２を同じグループとしてグルーピングすることが可能となる。

　本例では、１種類の指向性パラメータのみの場合を示したが、一般には、複数の指向性パラメータを指定することで、複数の関心方向や、複数の移動速度上限を設定することが可能であり、様々な移動体端末のグルーピングポリシーを作成することが可能である。

　また、ある移動体端末に注目し、その移動体端末が登録されているテーブルエントリをモニターすることで、この移動体端末と並走する他の移動体端末を検出することもできる。例えば、検索対象移動体端末の入力に対して、過去もしくは現在に、この検索対象移動体端末と同じグループに属する移動体端末を並走移動体端末として出力することができる。

　その際に、必要ならばグルーピングポリシーを合わせて設定することで、そのポリシーに合わせてグルーピングを修正することも可能である。例えば、グルーピングポリシーとして、「検索対象移動体端末と過去１０分以上半径１００ｍ以内に存在しながら並走した移動体端末」のように設定すれば、本発明によって出力された移動体端末グループの中から条件を満足させるもののみをフィルタリングして出力すれば良い。

　更に、移動体端末の数が大量であった時は、各テーブルの各エントリに登録された移動体端末のうち、時刻ｔと時刻ｔ＋τにおける位置のどちらも同じエントリに登録されているものの数を数え、その数の多い順に適当な数だけエントリに登録された移動体端末の集合を抽出する。

　これは、全移動体端末の中から、同じ方向に沿って進む移動体端末をその合計数が多いグループからサンプリングすることを意味する。それらのサンプルされた移動体端末をその移動方向や速度からグルーピングすることで、システム全体の移動体端末移動パターンの主たる傾向（多くの移動体端末がどの方向にどれくらいの速度で移動しているか、等）を取り出して、その移動体端末グループのサイズや方向・速度等の移動体端末グループ情報を作成し、移動体端末の移動状態を分類・表示ことが可能である。

　次に、本実施例の効果について述べる。移動体管理システム１００は、基本的に、移動体端末の位置アップデートに対して管理するテーブルを更新し、上記の方法でテーブルから関心の高い移動体端末をサンプリングしてグルーピングを行うため、全ての移動体端末の移動に関する相互関係を計算してグルーピングする必要がない。そのため移動体端末数が増加してもその計算負荷の増加を抑えることができ、計算時間の大幅な削減が望める。

　なお、本発明で示した全ての実施の形態及び実施例においては、テーブルのキーの計算方法として、既述の実施の形態におけるキー計算関数Ｌ^（ｐ）（ｘ）と基本関数ｆ^（ｐ） _ｂ（ｘ）とランダムベクトルΦ^（ｐ） _ｂとを用いたが、指向性を指定するパラメータによって、望む方向・強度に対応する非対称性が導入されたものであればこれに限るものではない。

　なお、本発明で示した全ての実施の形態及び実施例では、テーブルにおけるデータの衝突は、厳密に同じエントリに登録されるとして説明したが、バリエーションとしてテーブルのエントリ距離を定義し、近くのエントリ（例えば、キー計算関数Ｌ^（ｐ）（ｘ）であらわされるキーの一ビットだけ異なる「隣のエントリ」等）までに登録されているデータは衝突すると衝突範囲を拡大しても良い。

　＜備考＞
　以上、本発明の実施の形態及び実施例を詳述してきたが、実際には、上記の実施の形態及び実施例に限られるものではなく、本発明の要旨を逸脱しない範囲の変更があっても本発明に含まれる。

　＜付記＞
　上記の実施の形態及び実施例の一部又は全部は、以下の付記のように記載することも可能である。但し、実際には、以下の記載例に限定されない。

　［付記１］
　入力装置を介して入力された複数の方向パラメータと複数の強度パラメータとに基づいて複数の乱数情報を算出する乱数発生部と、
　前記複数の乱数情報に基づいて複数のキー計算関数を算出する初期化部と、
　入力装置を介して入力された複数の検索対象データに基づいて、前記複数のキー計算関数に対応する複数のテーブルを算出し、前記複数のテーブルをテーブル保持装置に記録するデータ登録部と、
　前記複数のテーブルを参照して、入力装置を介して入力された検索条件が示すクエリに基づいて候補データリストを算出する検索部と、
　前記候補データリストに属する複数の検索データから前記検索条件が示す条件を満足する検索結果データを算出し、前記検索結果データを出力装置に出力するデータ処理部と
を具備し、
　前記データ登録部は、前記複数のテーブルのうちの任意のキー計算関数に対応するテーブルを算出する際、複数のキーを複数のデータリストに対応付け、前記複数のデータリストのうちの任意のキーに対応するデータリストに属するデータを前記任意のキー計算関数に代入することにより算出される値が前記任意のキーに等しくなるように該テーブルを算出し、
　前記候補データリストは、前記複数のキー計算関数に対応する複数の検索データリストを含み、
　前記複数の検索データリストのうちの前記任意のキー計算関数に対応する検索データリストは、前記複数のデータリストのうちの、前記クエリが前記キー計算関数に代入されることにより算出されるクエリ値に対応するデータリストを示す
　類似性検出装置。

　［付記２］
　付記１に記載の類似性検出装置であって、
　前記データ登録部は、前記複数の検索対象データに基づいて複数のテーブルセットを更に算出し、
　前記検索部は、前記複数のテーブルセットのうちの前記検索条件が示すテーブルセットが前記複数のテーブルを示すときに、前記複数のテーブルを参照して前記候補データリストを算出する
　類似性検出装置。

　［付記３］
　付記１乃至２のいずれかに記載の類似性検出装置であって、
　前記複数の方向パラメータは、前記複数の検索対象データのうちの類似する２つの状態変化類似データが前記任意のキー計算関数に代入されることによりそれぞれ算出される２つの値が等しくなるように、又は、前記２つの値の差が所定の値より小さくなるように、設定される
　類似性検出装置。

　［付記４］
　付記１乃至３のいずれかに記載の類似性検出装置であって、
　前記複数の検索対象データは、それぞれ画像を示す
　類似性検出装置。

　［付記５］
　付記１乃至４のいずれかに記載の類似性検出装置であって、
　前記データ登録部は、前記複数の検索対象データが更新されたときに、前記複数のテーブルを更新する
　類似性検出装置。

　［付記６］
　入力装置を介して入力された複数の方向パラメータと複数の強度パラメータとに基づいて複数の乱数情報を算出するステップと、
　前記複数の乱数情報に基づいて複数のキー計算関数を算出するステップと、
　入力装置を介して入力された複数の検索対象データに基づいて、前記複数のキー計算関数に対応する複数のテーブルを算出するステップと、
　前記複数のテーブルをテーブル保持装置に記録するステップと、
　前記複数のテーブルを参照して、入力装置を介して入力された検索条件が示すクエリに基づいて候補データリストを算出するステップと、
　前記候補データリストに属する複数の検索データから前記検索条件が示す条件を満足する検索結果データを算出するステップと、
　前記検索結果データを出力装置に出力するステップと、
　前記複数のテーブルのうちの任意のキー計算関数に対応するテーブルを算出する際、複数のキーを複数のデータリストに対応付け、前記複数のデータリストのうちの任意のキーに対応するデータリストに属するデータを前記任意のキー計算関数に代入することにより算出される値が前記任意のキーに等しくなるように該テーブルを算出するステップと
を具備し、
　前記候補データリストは、前記複数のキー計算関数に対応する複数の検索データリストを含み、
　前記複数の検索データリストのうちの前記任意のキー計算関数に対応する検索データリストは、前記複数のデータリストのうちの、前記クエリが前記キー計算関数に代入されることにより算出されるクエリ値に対応するデータリストを示す
　指向性近傍検出方法。

　［付記７］
　付記６に記載の指向性近傍検出方法であって、
　前記複数の検索対象データに基づいて複数のテーブルセットを更に算出するステップと、
　前記複数のテーブルセットのうちの前記検索条件が示すテーブルセットが前記複数のテーブルを示すときに、前記複数のテーブルを参照して前記候補データリストを算出するステップと
を更に具備する
　指向性近傍検出方法。

　［付記８］
　付記６乃至７のいずれかに記載の指向性近傍検出方法であって、
　前記複数の方向パラメータは、前記複数の検索対象データのうちの類似する２つの状態変化類似データが前記任意のキー計算関数に代入されることによりそれぞれ算出される２つの値が等しくなるように、又は、前記２つの値の差が所定の値より小さくなるように、設定される
　指向性近傍検出方法。

　［付記９］
　付記６乃至８のいずれかに記載の指向性近傍検出方法であって、
　前記複数の検索対象データは、それぞれ画像を示す
　指向性近傍検出方法。

　［付記１０］
　付記６乃至９のいずれかに記載の指向性近傍検出方法であって、
　前記複数の検索対象データが更新されたときに、前記複数のテーブルを更新するステップ
を更に具備する
　指向性近傍検出方法。

　［付記１１］
　大量の検索対象データに対して、任意の類似度判定基準で類似するデータを高速に検出する類似性検出装置であり、
　前述の類似性検出装置は、前述の検索対象データを登録・管理するための、類似度判定基準を設定するパラメータによって作成される乱数情報と関連付けられたテーブルを保持し、
　任意の参照点からの近傍検索要求に対して、前述のテーブルを利用し、前述の設定された類似度判定基準によって類似性判断を行い、近傍と判断されるデータを出力する
　ことを特徴とする類似性検出装置。

　［付記１２］
　付記１１に記載の類似性検出装置において、複数の異なる類似度判定基準を有し、それぞれの類似度判定基準と関連付けられた複数のテーブルを有し、検索対象データを全てのテーブルで並列に管理する
　ことを特徴とする類似性検出装置。

　［付記１３］
　付記１１に記載の類似度判定基準として、興味の方向と、その方向の重要度パラメータの組の集合とする
　ことを特徴とする類似性検出装置。

　［付記１４］
　付記１１に記載の検索対象データとして、任意の２点の距離がユークリッド空間上の距離として定義されている
　ことを特徴とする類似性検出装置。

　［付記１５］
　付記１２に記載の類似性検出装置において、検索においてその検索中心とともに検索類似度判定基準を入力し、複数のテーブルにおける近傍検出結果と、各テーブルに指定された類似度判定基準パラメータと検索類似度判定基準との関連性とを用いて出力する近傍を決定する
　ことを特徴とする類似性検出装置。

　［付記１６］
　付記１１又は付記１２に記載の検索対象データとして、予めその値が静的に固定されたデータだけでなく、動的にその値を更新するデータであり、値の更新に合わせて前述のテーブルの登録状態を更新する
　ことを特徴とする類似性検出装置。

　［付記１７］
　付記１１又は付記１２に記載の類似性検出装置として、前述のテーブルを用いた類似性判断結果を利用して、各データの状態変化が類似するものをグルーピングする
　ことを特徴とする類似性検出装置。

　［付記１８］
　付記１１に記載のテーブルは、キーとバリューのペアで構成され、ある任意のデータの登録に当たって、前記乱数情報を用いてデータを登録すべきキーを計算し、対応するバリューに当たるデータのリストに追加登録することでデータを管理する
　ことを特徴とする類似性検出装置。

　［付記１９］
　付記１１に記載の類似性判断として、同一もしくは差異の小さいキーを持つデータ同士を類似性が高いと扱う
　ことを特徴とする類似性検出装置。

　なお、本出願は、日本出願番号２０１１－２１９５４７に基づく優先権を主張するものであり、日本出願番号２０１１－２１９５４７における開示内容は引用により本出願に組み込まれる。

Claims (10)

1. 　検索対象データに対して、任意の類似度判定基準で類似するデータを検出する類似性検出装置であって、
   　類似度判定基準を設定するパラメータによって作成される乱数情報と関連付けられたテーブルを保持する手段と、
   　検索対象データを前記テーブルに登録し管理する手段と、
   　任意の参照点からの近傍検索要求に対して、前記テーブルを利用し、前記設定された類似度判定基準によって類似性判断を行い、近傍と判断されるデータを出力する手段と
   を具備する
   　類似性検出装置。
2. 　請求項１に記載の類似性検出装置であって、
   　複数の異なる類似度判定基準を設定する手段と、
   　前記複数の異なる類似度判定基準のそれぞれと関連付けられた複数のテーブルを保持する手段と、
   　前記検索対象データを前記複数のテーブルで並列に管理する手段と
   を更に具備する
   　類似性検出装置。
3. 　請求項１又は２に記載の類似性検出装置であって、
   　興味の方向と、該方向の重要度パラメータとの組の集合を、前記類似度判定基準とする手段
   を更に具備する
   　類似性検出装置。
4. 　請求項１乃至３のいずれか一項に記載の類似性検出装置であって、
   　任意の２点の距離がユークリッド空間上の距離として定義されているデータを、前記検索対象データとする手段
   を更に具備する
   　類似性検出装置。
5. 　請求項１乃至４のいずれか一項に記載の類似性検出装置であって、
   　検索の中心とともに検索類似度判定基準を入力し、前記複数のテーブルにおける近傍検出結果と、前記複数のテーブルの各々に指定された類似度判定基準パラメータと検索類似度判定基準との関連性とを用いて出力する近傍を決定する手段
   を更に具備する
   　類似性検出装置。
6. 　請求項１乃至５のいずれか一項に記載の類似性検出装置であって、
   　予め値が静的に固定されたデータ、及び動的に値を更新するデータのいずれも、前記検索対象データとして使用する手段と、
   　前記検索対象データとして使用されるデータの値の更新に合わせて前記テーブルの登録状態を更新する手段と
   を更に具備する
   　類似性検出装置。
7. 　請求項１乃至６のいずれか一項に記載の類似性検出装置であって、
   　前記テーブルを用いた類似性判断結果を利用して、状態変化が類似するデータをグルーピングする手段
   を更に具備する
   　類似性検出装置。
8. 　請求項１乃至７のいずれか一項に記載の類似性検出装置であって、
   　前記テーブルをキーとバリューとの組で構成し、ある任意のデータの登録に当たって、前記乱数情報を用いてデータを登録すべきキーを計算し、対応するバリューに当たるデータのリストに追加登録することでデータを管理する手段
   を更に具備する
   　類似性検出装置。
9. 　請求項１乃至８のいずれか一項に記載の類似性検出装置であって、
   　同一もしくは差異の小さいキーを持つデータ同士を類似性が高いと判断する手段
   を更に具備する
   　類似性検出装置。
10. 　類似性検出装置により実施され、検索対象データに対して、任意の類似度判定基準で類似するデータを検出するための指向性近傍検出方法であって、
    　類似度判定基準を設定するパラメータによって作成される乱数情報と関連付けられたテーブルを保持することと、
    　検索対象データを前記テーブルに登録し管理することと、
    　任意の参照点からの近傍検索要求に対して、前記テーブルを利用し、前記設定された類似度判定基準によって類似性判断を行い、近傍と判断されるデータを出力することと
    を含む
    　指向性近傍検出方法。

Images