(57)【要約】  大量のデータから類似のデータを高速に検出するために、パラメータリストに基づいて乱数情報を算出する乱数発生装置３と、その乱数情報に基づいて複数のキー計算関数を算出し、入力データに基づいて複数のテーブルを算出し、検索条件が示すクエリに基づいて候補データリストを算出するテーブル管理装置５と、その候補データリストから検索条件が示す条件を満足する検索結果データを算出するデータ処理装置６とを備えている。その各テーブルは、あるキーに対応するバリューが、あるキー計算関数に代入した値がそのキーに等しくなるデータのデータリストを示すように算出される。その候補データリストは、複数の検索データリストを含み、そのテーブルに対応する検索データリストは、そのクエリをそのキー計算関数に代入したクエリ値に対応するバリューを示している。
2013051619.tif 000002
【特許請求の範囲】
【請求項１】
検索対象データに対して、任意の類似度判定基準で類似するデータを検出する類似性検出装置であって、
類似度判定基準を設定するパラメータによって作成される乱数情報と関連付けられたテーブルを保持する手段と、
検索対象データを前記テーブルに登録し管理する手段と、
任意の参照点からの近傍検索要求に対して、前記テーブルを利用し、前記設定された類似度判定基準によって類似性判断を行い、近傍と判断されるデータを出力する手段と
を具備する
類似性検出装置。
【請求項２】
請求項１に記載の類似性検出装置であって、
複数の異なる類似度判定基準を設定する手段と、
前記複数の異なる類似度判定基準のそれぞれと関連付けられた複数のテーブルを保持する手段と、
前記検索対象データを前記複数のテーブルで並列に管理する手段と
を更に具備する
類似性検出装置。
【請求項３】
請求項１又は２に記載の類似性検出装置であって、
興味の方向と、該方向の重要度パラメータとの組の集合を、前記類似度判定基準とする手段
を更に具備する
類似性検出装置。
【請求項４】
請求項１乃至３のいずれか一項に記載の類似性検出装置であって、
任意の２点の距離がユークリッド空間上の距離として定義されているデータを、前記検索対象データとする手段
を更に具備する
類似性検出装置。
【請求項５】
請求項１乃至４のいずれか一項に記載の類似性検出装置であって、
検索の中心とともに検索類似度判定基準を入力し、前記複数のテーブルにおける近傍検出結果と、前記複数のテーブルの各々に指定された類似度判定基準パラメータと検索類似度判定基準との関連性とを用いて出力する近傍を決定する手段
を更に具備する
類似性検出装置。
【請求項６】
請求項１乃至５のいずれか一項に記載の類似性検出装置であって、
予め値が静的に固定されたデータ、及び動的に値を更新するデータのいずれも、前記検索対象データとして使用する手段と、
前記検索対象データとして使用されるデータの値の更新に合わせて前記テーブルの登録状態を更新する手段と
を更に具備する
類似性検出装置。
【請求項７】
請求項１乃至６のいずれか一項に記載の類似性検出装置であって、
前記テーブルを用いた類似性判断結果を利用して、状態変化が類似するデータをグルーピングする手段
を更に具備する
類似性検出装置。
【請求項８】
請求項１乃至７のいずれか一項に記載の類似性検出装置であって、
前記テーブルをキーとバリューとの組で構成し、ある任意のデータの登録に当たって、前記乱数情報を用いてデータを登録すべきキーを計算し、対応するバリューに当たるデータのリストに追加登録することでデータを管理する手段
を更に具備する
類似性検出装置。
【請求項９】
請求項１乃至８のいずれか一項に記載の類似性検出装置であって、
同一もしくは差異の小さいキーを持つデータ同士を類似性が高いと判断する手段
を更に具備する
類似性検出装置。
【請求項１０】
類似性検出装置により実施され、検索対象データに対して、任意の類似度判定基準で類似するデータを検出するための指向性近傍検出方法であって、
類似度判定基準を設定するパラメータによって作成される乱数情報と関連付けられたテーブルを保持することと、
検索対象データを前記テーブルに登録し管理することと、
任意の参照点からの近傍検索要求に対して、前記テーブルを利用し、前記設定された類似度判定基準によって類似性判断を行い、近傍と判断されるデータを出力することと
を含む
指向性近傍検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴検出装置及び指向性近傍検出方法に関し、特に、多次元連続データ集合から所望のデータを検索する特徴検出装置及び指向性近傍検出方法に関する。
【背景技術】
【０００２】
近傍検索技術は、様々な応用範囲で用いられる重要な技術であり、例えば、画像やＷｅｂページ等のデータの類似性を考慮し、膨大なデータベースの中から特徴が似たデータを検出する等のアプリケーションに用いられる。非常に単純な方法として、それぞれのデータの特徴を距離の定義された空間の一点（例えばユークリッド空間の一点）で表現し、クエリ点からの全てのデータへの距離を計算することで、クエリに近いデータを検出することができる。しかし、このような距離を直接計算する方法は、非常にコストがかかり、データ数の増大とともに計算負荷が非線形に増加してしまうため、様々な方法が提案されている。【０００３】
特許文献１（特開２００４−０２１４３０号公報）には、ユーザの操作を煩雑にすることなく、特定の被写体を含む画像を類似画像として的確に検索し得る画像検索装置が開示されている。その画像検索装置は、検索の対象となる画像を複数含む検索対象画像群の中から、検索キーである基準画像に類似する画像を抽出する画像検索装置であって、基準画像及び検索対象画像群に含まれる各画像をそれぞれ複数の領域に分割する手段と、基準画像及び検索対象画像群に含まれる各画像の各領域から少なくとも１つの特徴量を抽出する手段と、検索対象画像群に含まれる各画像について領域の一部を選択する手段であって、検索対象画像群から画像を順次選択し、基準画像の各領域から抽出された特徴量と、当該選択した画像の各領域から抽出された特徴量と、の類似性に基づいて、所定数の当該選択された画像の領域を選択する手段と、前記検索対象画像群に含まれる各画像について選択された一部の領域の特徴量に基づいて、検索対象画像群から基準画像に類似する画像を抽出する手段と、を含むことを特徴としている。【０００４】
特許文献２（特開２００５−０７０９２７号公報）には、画像自体の一致度に拘泥されず、描画形状が類似している画像を検出することができるような画像特徴を取得する画像特徴取得方法が開示されている。その画像特徴取得方法は、二次元画像の画像特徴を取得する画像特徴取得方法であって、上記二次元画像を所定の大きさにサイズ変更し、該画像がカラー画像であれば一色の濃淡の階調で形成するスケール画像に変換し、各スケール画像に対して、二次元画像の左右のいずれか一方に設定した起点から水平方向へ連なる画素列を、該画素列の終点と次の画素列の起点とを鉛直方向へ順番に連結して水平成分の一次元ラスタ画像を作成し、二次元画像の上下のいずれか一方に設定した起点から鉛直方向へ連なる画素列を、該画素列の終点と次の画素列の起点とを水平方向へ順番に連結して鉛直成分の一次元ラスタ画像を作成し、これらの一次元ラスタ画像に対して適宜の変換処理を実行する。【０００５】
特許文献３（特開平１０−３２６２８６号公報）には、類似検索の精度が向上でき、また重要な類似データが検索結果からぬけおちる可能性が低い類似検索装置が開示されている。その類似検索装置は、複数の対象に対して各々作成され、対象を特徴づける複数の属性をベクトル構成要素とするベクトルデータを複数蓄積するベクトルデータベースと、指定された類似検索対象に対するベクトルデータを作成する対象ベクトルデータ作成部と、複数の検索条件を生成する検索条件集合生成部と、この検索条件集合生成部で生成された個々の検索条件ごとに、上記ベクトルデータベースに蓄積された複数のベクトルデータの中から、上記検索条件を満足し、かつ上記対象ベクトルデータに類似するベクトルデータを検索する類似検索エンジンと、上記類似検索エンジンにより検索された結果を個々の検索条件ごとに表示する検索結果表示部とを備えたことを特徴としている。【０００６】
一般に、高次元の空間における近傍検索は、低次元の場合に比べ、更に問題が困難になる。そのため、大量な高次元データに対して、厳密に距離を計算して近傍データを求めるのではなく、近似的に、もしくは確率的に近距離のデータを求める近似的近傍検索方法が提案されている。その一つの代表例は、ＬＳＨ（Ｌｏｃａｌｉｔｙ  Ｓｅｎｓｉｔｉｖｅ  Ｈａｓｈｉｎｇ）（非特許文献１参照）である。ＬＳＨは、任意の２点に対して、その２点の距離が近いほど高い確率で衝突する（同じ値をもつ）ハッシュ関数を利用する方法であり、クエリ入力に対する近傍検出演算にかかる時間を削減することができる。ここで、ＬＳＨを用いると、あるクエリｑに対してデータｐが衝突する確率は、その距離ｄ（ｐ、ｑ）にのみ依存するため、クエリｑを中心とする１つの円の円周上にある複数のデータは、全て等確率でクエリｑに衝突することになる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−０２１４３０号公報
【特許文献２】特開２００５−０７０９２７号公報
【特許文献３】特開平１０−３２６２８６号公報
【非特許文献】
【０００８】
【非特許文献１】Ｄａｔａｒ，  Ｍ．，  Ｉｍｍｏｒｌｉｃａ，  Ｎ．，  Ｉｎｄｙｋ，  Ｐ．，  ａｎｄ  Ｍｉｒｒｏｋｎｉ，  Ｖ．  ２００４．  Ｌｏｃａｌｉｔｙ  ｓｅｎｓｉｔｉｖｅ  ｈａｓｈｉｎｇ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  ｐ−ｓｔａｂｌｅ  ｄｉｓｔｒｉｂｕｔｉｏｎｓ．  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｇｅｏｍｅｔｒｙ
【発明の概要】
【０００９】
第１の問題点は、２つのデータの特徴の近さの指標として、方向に代表される詳細な位置関係が考えられていないことである。具体的には、ある方向に関する距離を他の方向に関する距離より重要視する場合等、方向の違いを区別して近傍検索を行うことができない。その理由は、従来の近傍検索はその距離のみに依存する手法が用いられているからである。
【００１０】
第２の問題点は、ある観点に対する類似度のみに関心がある場合、従来手法では、余計な計算時間がかかってしまうことである。その理由は、従来手法では、方向の考慮がないため、全方向での近傍検出によって候補を抽出した後に、関心がある方向に沿ったデータのみを取り出すという２段階の処理が必要であるからである。方向によって関心の高さの違いが大きい（ある方向に沿った距離の重みと、他の方向の距離の重みの差が非常に大きい時）ほど、近傍検出した候補の数が膨大になるため、計算時間の削減効果はあまり期待できなくなってしまう。
【００１１】
本発明の目的は、特徴の違いが、距離として定義された空間内での近傍検出において、任意の類似度判定基準（任意の方向と、任意の距離の重要度）を指定して、近傍データを高速に検出する類似性検出装置及び指向性近傍検出方法を提供することにある。
【００１２】
本発明による類似性検出装置は、乱数発生部と初期化部とデータ登録部と検索部とデータ処理部とを備えている。その乱数発生部は、入力装置を介して入力された複数の方向パラメータと複数の強度パラメータとに基づいて複数の乱数情報を算出する。その複数の方向パラメータは、ユークリッド空間上の方向を示している。その初期化部は、その複数の乱数情報に基づいて複数のキー計算関数を算出する。そのデータ登録部は、入力装置を介して入力された複数の検索対象データに基づいて、その複数のキー計算関数に対応する複数のテーブルを算出し、その複数のテーブルをテーブル保持装置に記録する。その複数の検索対象データは、それぞれ、そのユークリッド空間上の点を示している。その複数の検索対象データのうちの任意の２つの検索対象データがそれぞれ示している２つの点の距離は、その２つの検索対象データの類似度を示している。その複数のテーブルのうちの任意のキー計算関数に対応するテーブルは、複数のキーを複数のデータリストに対応付け、その複数のデータリストのうちの任意のキーに対応するデータリストに属するデータがその任意のキー計算関数に代入されることにより算出される値がその任意のキーに等しくなるように算出される。その検索部は、その複数のテーブルを参照して、入力装置を介して入力された検索条件が示しているクエリに基づいて候補データリストを算出する。その候補データリストは、その複数のキー計算関数に対応する複数の検索データリストを含んでいる。その複数の検索データリストのうちのその任意のキー計算関数に対応する検索データリストは、その複数のデータリストのうちの、そのクエリがそのキー計算関数に代入されることにより算出されるクエリ値に対応するデータリストを示している。そのデータ処理部は、その候補データリストに属する複数の検索データからその検索条件が示している条件を満足する検索結果データを算出し、その検索結果データを出力装置に出力する。
【００１３】
本発明による指向性近傍検出方法では、入力装置を介して入力された複数の方向パラメータと複数の強度パラメータとに基づいて複数の乱数情報を算出する。また、その複数の乱数情報に基づいて複数のキー計算関数を算出する。また、入力装置を介して入力された複数の検索対象データに基づいて、その複数のキー計算関数に対応する複数のテーブルを算出する。また、その複数のテーブルをテーブル保持装置に記録する。また、その複数のテーブルを参照して、入力装置を介して入力された検索条件が示しているクエリに基づいて候補データリストを算出する。また、その候補データリストに属する複数の検索データからその検索条件が示している条件を満足する検索結果データを算出する。また、その検索結果データを出力装置に出力する。その複数の方向パラメータは、ユークリッド空間上の方向を示している。その複数の検索対象データは、それぞれ、そのユークリッド空間上の点を示している。その複数の検索対象データのうちの任意の２つの検索対象データがそれぞれ示している２つの点の距離は、その２つの検索対象データの類似度を示している。その複数のテーブルのうちの任意のキー計算関数に対応するテーブルは、複数のキーを複数のデータリストに対応付け、その複数のデータリストのうちの任意のキーに対応するデータリストに属するデータがその任意のキー計算関数に代入されることにより算出される値がその任意のキーに等しくなるように算出される。その候補データリストは、その複数のキー計算関数に対応する複数の検索データリストを含んでいる。その複数の検索データリストのうちのその任意のキー計算関数に対応する検索データリストは、その複数のデータリストのうちの、そのクエリがそのキー計算関数に代入されることにより算出されるクエリ値に対応するデータリストを示している。
【００１４】
第１の効果は、膨大なデータの中で、あるクエリ点からある興味方向に沿った自由度の高い近傍点の検出が行えることである。その理由は、任意の２点が、任意の興味の方向に沿った任意の距離重み（重要度）で測った距離が短いほど高い確率で同じエントリに登録されるテーブルを具備するデータ管理機能を提供することで、指向性近傍検出機能を実現するからである。
【００１５】
第２の効果は、指向性近傍検索処理の高速化である。その理由は、事前に所望の指向性を登録した複数のテーブルにデータを登録しておくことで、クエリ点からの指向性近傍検索に当たって、クエリ点と同じエントリに登録されたデータのみを扱えば良く、全てのデータとの距離を計算する必要がないためオンライン処理時間が大幅に短縮化されるからである。
【図面の簡単な説明】
【００１６】
【図１】図１は、本発明による類似性検出装置を示すブロック図である。
【図２】図２は、テーブル管理装置を示すブロック図である。
【図３】図３は、初期化動作を示す流れ図である。
【図４】図４は、検索動作を示す流れ図である。
【図５】図５は、指向パラメータの例を示す表である。
【図６】図６は、指向パラメータに対応する衝突確率等値線を示すグラフである。
【図７】図７は、指向パラメータの例を示す表である。
【図８】図８は、複数のテーブルセットの例を示す表である。
【図９】図９は、複数の指向パラメータに対応する複数の衝突確率等値線を示すグラフである。
【図１０】図１０は、画像を示す図である。
【図１１】図１１は、複数の検索対象データ示すグラフである。
【図１２】図１２は、複数のテーブルセットの例を示す表である。
【図１３】図１３は、検索条件のクエリの例を示すグラフである。
【図１４】図１４は、検索結果データの例を示すグラフである。
【図１５】図１５は、複数の時系列データを示すグラフである。
【図１６】図１６は、複数の時系列データのうちの複数の検索対象データを示すグラフである。
【図１７】図１７は、複数の衝突確率等値線を示すグラフである。
【図１８】図１８は、他の複数の衝突確率等値線を示すグラフである。
【図１９】図１９は、衝突確率分布を示すグラフである。
【図２０】図２０は、他の衝突確率分布を示すグラフである。
【図２１】図２１は、特徴分布を示すグラフである。
【図２２】図２２は、移動体管理システムを示すブロック図である。
【図２３】図２３は、複数のテーブルセットを示す表である。
【発明を実施するための形態】
【００１７】
図面を参照して、本発明による類似性検出装置の実施の形態を説明する。その類似性検出装置１は、図１に示されているように、複数のコンピュータが互いに双方向に情報を伝送することができるように接続されている。
【００１８】
その複数のコンピュータの各コンピュータは、図示されていないが、ＣＰＵと、記憶装置と、インターフェースとを備えている。
【００１９】
そのＣＰＵは、そのコンピュータにインストールされているコンピュータプログラムを実行することにより、その記憶装置とそのインターフェースとを制御する。
【００２０】
その記憶装置は、そのコンピュータプログラムを記録し、そのＣＰＵにより作成される情報を一時的に記録する。
【００２１】
そのインターフェースは、そのコンピュータに接続されている外部機器により生成される情報をそのＣＰＵに出力したり、そのＣＰＵにより生成された情報をその外部機器に出力したりする。
【００２２】
その外部機器としては、入力装置、出力装置、通信装置、リムーバルメモリドライブが例示される。
【００２３】
その入力装置は、ユーザに操作されることにより情報を作成し、その情報をそのＣＰＵに出力する。その入力装置としては、キーボード、ポインティングデバイス、タッチパネルが例示される。
【００２４】
その出力装置は、そのＣＰＵにより生成される情報をユーザに認識可能に出力する。その出力装置としては、ディスプレイ、音響装置、タッチパネルが例示される。
【００２５】
その通信装置は、通信ネットワークを介してそのＣＰＵにより作成された情報を他のコンピュータに送信し、その通信ネットワークを介して他のコンピュータから受信された情報をそのＣＰＵに出力する。その通信装置は、更に、そのコンピュータにインストールされるコンピュータプログラムを他のコンピュータからダウンロードすることに利用される。
【００２６】
そのリムーバルメモリドライブは、記録媒体が挿入されたときに、その記録媒体に記録されているデータを読み出すことに利用される。そのリムーバルメモリドライブは、更に、コンピュータプログラムが記録されている記録媒体が挿入されたときに、そのコンピュータプログラムをそのコンピュータにインストールするときに利用される。その記録媒体としては、磁気ディスク（フレキシブルディスク、ハードディスク）、光ディスク（ＣＤ、ＤＶＤ）、光磁気ディスク、フラッシュメモリが例示される。
【００２７】
その複数のコンピュータは、パラメータ管理装置２と、乱数発生装置３と、テーブル管理装置５と、データ処理装置６とを含んでいる。
【００２８】
パラメータ管理装置２は、入力装置７を備えている。パラメータ管理装置２は、入力装置７を介してパラメータリスト８がパラメータ管理装置２に入力されるように、入力装置７を制御する。
【００２９】
乱数発生装置３は、テーブル管理装置５から乱数情報を要求されたときに、テーブル管理装置５から出力された情報に基づいて乱数情報を算出する。
【００３０】
テーブル管理装置５は、テーブル保持装置１０と、入力装置１１とを備えている。テーブル管理装置５は、入力装置１１を介して入力データ１２がテーブル管理装置５に入力されるように、入力装置１１を制御する。テーブル管理装置５は、入力データ１２と乱数発生装置３により算出された乱数情報とに基づいて複数のテーブルを算出する。テーブル管理装置５は、その複数のテーブルがテーブル保持装置１０に記録されるように、テーブル保持装置１０を制御する。テーブル管理装置５は、更に、データ処理装置６からデータリストを要求されたときに、その複数のテーブルを参照して、データ処理装置６から出力された情報に基づいてデータリストを算出し、そのデータリストをデータ処理装置６に出力する。
【００３１】
データ処理装置６は、入力装置１４と、出力装置１５とを備えている。データ処理装置６は、入力装置１４を介して検索条件１６がデータ処理装置６に入力されるように、入力装置１４を制御する。検索条件１６は、クエリと条件とを示している。データ処理装置６は、更に、そのクエリをテーブル管理装置５に出力することにより、テーブル管理装置５にデータリストを要求する。データ処理装置６は、その条件とテーブル管理装置５により算出されたデータリストとに基づいて検索結果データを算出する。その検索結果データは、そのデータリストが示すデータのうちのその条件を満足するデータを示している。データ処理装置６は、更に、テーブル管理装置５により算出された検索結果データがユーザに認識可能に表現されるように、出力装置１５を制御する。
【００３２】
図２は、テーブル管理装置５を示している。テーブル管理装置５にインストールされるコンピュータプログラムは、テーブル管理装置５に複数の機能をそれぞれ実現させる複数のコンピュータプログラムから形成されている。
【００３３】
テーブル管理装置５にその複数の機能をそれぞれ実現させた場合、テーブル管理装置５は、乱数情報取得部２１と、初期化部２２と、データ登録部２３と、検索部２４とを含んでいる。
【００３４】
乱数情報取得部２１は、パラメータ管理装置２に入力されたパラメータリスト８をパラメータ管理装置２から収集する。パラメータリスト８は、テーブルパラメータと管理パラメータと指向パラメータとを示している。そのテーブルパラメータは、テーブルの面数Ｐとウィンドウ幅Ｗと基数Ｃとビット長Ｂとを示している。面数Ｐは、正の整数を示している。ウィンドウ幅Ｗは、正の実数を示している。基数Ｃは、２以上の整数を示している。ビット長Ｂは、正の整数を示している。その管理パラメータは、次元数Ｄを示している。その指向パラメータは、集合Ｕを示している。
【００３５】
集合Ｕは、指向パラメータｕｊから形成され、以下の式により表現される。
Ｕ＝｛ｕｊ｜ｕｊ∈ＲＤ×Ｒ＋｝（ｊ＝１，・・・，Ｄ）
ここで、集合ＲＤは、Ｄ次元数ベクトル空間を示している。例えば、集合Ｒ２は、２次元数ベクトル空間を示している。
【００３６】
集合Ｒ＋は、正の実数の集合を示している。すなわち、指向パラメータｕｊは、以下の式により表現される。
ｕｊ＝＜ｖｊ，σｊ＞
ここで、方向パラメータｖｊは、Ｄ次元のベクトルを示している。強度パラメータσｊは、正の実数であり、方向パラメータｖｊを重視する程度を示している。
【００３７】
乱数情報取得部２１は、パラメータリスト８のうちのウィンドウ幅Ｗとビット長Ｂと次元数Ｄと集合Ｕとを乱数発生装置３に出力することにより、乱数発生装置３に乱数情報を要求する。乱数情報取得部２１は、乱数発生装置３により算出された乱数情報を乱数発生装置３から収集する。乱数情報取得部２１は、その要求をＰ回繰り返すことにより、複数（Ｐ個）の乱数情報を乱数発生装置３から収集し、乱数情報集合Ｚを作成する。
【００３８】
乱数情報集合Ｚは、以下の式により表現される。
Ｚ＝｛Ｚｐ｝（ｐ＝１，・・・，Ｐ）
ここで、集合Ｚｐは、乱数発生装置３により算出された１つの乱数情報を示している。
【００３９】
集合Ｚｐは、以下の式により表現される。
Ｚｐ＝｛Ｚｂ｜Ｚｂ＝＜Φ（ｐ）ｂ，Ｒ（ｐ）ｂ＞｝（ｂ＝１，・・・，Ｂ）
ここで、乱数Ｒ（ｐ）ｂは、一様分布Ｕ［０，Ｗ］に従う乱数を示している。ランダムベクトルΦ（ｐ）ｂは、Ｄ次元のベクトルを示している。
【００４０】
ランダムベクトルΦ（ｐ）ｂは、以下の式により表現される。
Φ（ｐ）ｂ＝ＶΛ−１／２Ａｂ
【００４１】
行列Ｖは、以下の式により表現される。
Ｖ＝（ｖ１，・・・，ｖＤ）
【００４２】
対角行列Λ−１／２は、以下の式により表現される。
Λ−１／２＝ｄｉａｇ｛１／σ１，・・・，１／σＤ｝
【００４３】
ベクトルＡｂは、Ｄ次元ベクトルであり、ベクトルＡｂのｄ成分Ａｂ，ｄ（ｄ＝１，・・・，Ｄ）は、正規分布Ｎ（０，１）に従う乱数を示している。
【００４４】
初期化部２２は、更に、パラメータ管理装置２により収集されたパラメータリスト８と乱数情報取得部２１により収集された乱数情報とに基づいて複数（Ｐ個）のキー計算関数を算出する。その複数のキー計算関数のうちの任意の自然数ｐ（ｐ≦Ｐ）に対応するキー計算関数Ｌ（ｐ）（ｘ）は、Ｄ次元数ベクトルｘの関数である。
【００４５】
キー計算関数Ｌ（ｐ）（ｘ）は、Ｄ次元数ベクトルｘを用いて、以下の式により表現される。
Ｌ（ｐ）（ｘ）＝（ｆ（ｐ）１（ｘ），・・・，ｆ（ｐ）Ｂ（ｘ））
【００４６】
基本関数ｆ（ｐ）ｂ（ｘ）は、以下の式により表現される。
【数１】
2013051619.tif 000003
【００４７】
データ登録部２３は、入力装置１１を介してテーブル管理装置５に入力データ１２が入力されるように、入力装置１１を制御する。入力データ１２は、データ集合Ｘを示している。
【００４８】
データ集合Ｘは、データｘｉから形成され、以下の式により表現される。
Ｘ＝｛ｘｉ｜ｘｉ∈ＲＤ｝（ｉ＝１，・・・，Ｎ）
ここで、集合ＲＤは、Ｄ次元数ベクトル空間を示している。自然数Ｎは、データ集合Ｘのデータｘｉの要素の総数を示し、１より大きい自然数を示している。データｘｉは、Ｄ次元数ベクトルを示している。
【００４９】
データ登録部２３は、更に、入力データ１２と初期化部２２により算出された複数のキー計算関数とに基づいて、複数（Ｐ個）のテーブルを作成する。その複数のテーブルのうちの任意の自然数ｐに対応するテーブルは、複数のエントリから形成されている。そのテーブルは、その複数のエントリの各エントリが１つのキーと１つのバリューとのペア（組）を示すことにより、複数のキーを複数のバリューに対応付けている。すなわち、その複数のキーのうちの任意のキーは、その複数のバリューのうちの１つのバリューに対応している。
【００５０】
その複数のキーのうちの任意のキーは、初期化部２２により算出された複数のキー計算関数のうちの任意の自然数ｐに対応するキー計算関数Ｌ（ｐ）（ｘ）に、データ集合Ｘのうちのいずれかのデータｘが代入されることにより算出された値を示している。更に、その複数のキーは、互いに異なり、データ集合Ｘに属する全てのデータｘがキー計算関数Ｌ（ｐ）（ｘ）に代入されることによりそれぞれ算出される複数の値を含んでいる。
【００５１】
その複数のバリューのうちの任意のキーＬに対応するバリューＴａｂｌｅ（ｐ）［Ｌ］は、所定のデータの集合であるデータリストを示している。このとき、バリューＴａｂｌｅ（ｐ）［Ｌ］は、そのデータリストに属するデータのうちの任意のデータｘがキー計算関数Ｌ（ｐ）（ｘ）に代入されることにより算出された値がキーＬに一致するように、算出される。
【００５２】
データ登録部２３は、更に、その複数のテーブルがテーブル保持装置１０に記録されるように、テーブル保持装置１０を制御する。
【００５３】
検索部２４は、データ処理装置６からクエリが出力されたときに、データ登録部２３により作成された複数のテーブルを参照して、そのクエリに基づいてデータリストを算出する。すなわち、検索部２４は、そのクエリｑに基づいてその複数のテーブルに対応する複数の検索キーを算出する。その複数の検索キーのうちの自然数ｐに対応する検索キーＬ（ｐ）（ｑ）は、初期化部２２により算出された複数のキー計算関数のうちの自然数ｐに対応するキー計算関数Ｌ（ｐ）（ｘ）にクエリｑが代入されることにより算出された値を示している。
【００５４】
検索部２４は、データ登録部２３により作成された複数のテーブルを参照して、その複数の検索キーに基づいてデータリストＬｉｓｔ＜ｘ＞を算出する。データリストＬｉｓｔ＜ｘ＞は、データ集合Ｘに属するデータのうちの所定のデータの集合を示している。データリストＬｉｓｔ＜ｘ＞は、その複数のテーブルのうちの自然数ｐに対応するテーブルがキーＬ（ｐ）（ｑ）に対応するエントリを含むときに、そのエントリが示すバリューＴａｂｌｅ（ｐ）［Ｌ］が示すデータリストに属するデータを含むように、算出される。
【００５５】
このとき、データ処理装置６は、検索条件１６と検索部２４により算出されたデータリストＬｉｓｔ＜ｘ＞とに基づいて検索結果データｘ＊を算出する。検索結果データｘ＊は、データリストＬｉｓｔ＜ｘ＞に属するデータのうちの検索条件１６が示す条件が満足するデータの集合を示している。データ処理装置６は、更に、検索結果データｘ＊が表示されるように、出力装置１５を制御する。
【００５６】
本発明による指向性近傍検出方法の実施の形態は、類似性検出装置１により実行され、初期化動作とデータ登録動作と検索動作とを備えている。
【００５７】
図３は、その初期化動作を示している。ユーザは、まず、パラメータリスト８を用意し、入力装置７を操作することにより、パラメータリスト８をパラメータ管理装置２に入力する。パラメータ管理装置２は、入力装置７を介してパラメータリスト８が入力されると、パラメータリスト８を記憶装置に記録する。テーブル管理装置５は、パラメータ管理装置２に入力されたパラメータリスト８をパラメータ管理装置２から取得する（ステップＳ１）。
【００５８】
パラメータリスト８は、テーブルパラメータと管理パラメータと指向パラメータとを示している。そのテーブルパラメータは、テーブルの作成に必要である情報を示し、すなわち、テーブルの面数Ｐとウィンドウ幅Ｗと基数Ｃとビット長Ｂとを示している。面数Ｐは、正の整数を示している。ウィンドウ幅Ｗは、正の実数を示している。基数Ｃは、２以上の整数を示している。ビット長Ｂは、正の整数を示している。その管理パラメータは、その他管理運用に必要である情報を示し、すなわち、次元数Ｄを示している。その指向パラメータは、特徴検出の方向や距離の重み情報を含み、近傍検出における指向性を表現し、集合Ｕを示している。
【００５９】
集合Ｕは、指向パラメータｕｊから形成され、以下の式により表現される。
Ｕ＝｛ｕｊ｜ｕｊ＝＜ｖｊ，σｊ＞｝（ｊ＝１，・・・，Ｄ）
ここで、方向パラメータｖｊは、Ｄ次元のベクトルを示している。強度パラメータσｊは、正の実数であり、方向パラメータｖｊを重視する程度を示している。
【００６０】
テーブル管理装置５は、テーブル面番号ｐに１を代入する（ステップＳ２）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐの大小関係を算出する（ステップＳ３）。
【００６１】
テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きくないときに（ステップＳ３、ｐ≦Ｐ）、パラメータリスト８のうちのウィンドウ幅Ｗとビット長Ｂと次元数Ｄと集合Ｕとを乱数発生装置３に出力することにより、乱数発生装置３に乱数情報を要求する。乱数発生装置３は、テーブル管理装置５から乱数情報を要求されたときに、ウィンドウ幅Ｗとビット長Ｂと次元数Ｄと集合Ｕとに基づいて、集合Ｚｐを示す乱数情報を算出する。
【００６２】
集合Ｚｐは、要素Ｚｂから形成され、以下の式により表現される。
Ｚｐ＝｛Ｚｂ｜Ｚｂ＝＜Φ（ｐ）ｂ，Ｒ（ｐ）ｂ＞｝（ｂ＝１，・・・，Ｂ）
ここで、乱数Ｒ（ｐ）ｂは、一様分布Ｕ［０，Ｗ）に従う乱数を示し、Ｂ回の独立な試行により生成される。ランダムベクトルΦ（ｐ）ｂは、Ｄ次元のベクトルを示している。
【００６３】
ランダムベクトルΦ（ｐ）ｂは、以下の式により表現される。
Φ（ｐ）ｂ＝ＶΛ−１／２Ａｂ
【００６４】
行列Ｖは、以下の式により表現される。
Ｖ＝（ｖ１，・・・，ｖＤ）
【００６５】
対角行列Λ−１／２は、以下の式により表現される。
Λ−１／２＝ｄｉａｇ｛１／σ１，・・・，１／σＤ｝
【００６６】
ベクトルＡｂは、Ｄ次元ベクトルであり、ベクトルＡｂのｄ成分Ａｂ，ｄ（ｄ＝１，・・・，Ｄ）は、正規分布Ｎ（０，１）に従う乱数を示している。ベクトルＡｂの全ての成分は、それぞれ、独立な試行により生成される。テーブル管理装置５は、乱数発生装置３により算出された乱数情報を乱数発生装置３から収集する（ステップＳ４）。
【００６７】
テーブル管理装置５は、その乱数情報が収集された後に、テーブル面番号ｐを１だけインクリメントし、すなわち、テーブル面番号ｐが示す値に１を加算することにより算出された和をテーブル面番号ｐに代入する（ステップＳ５）。
【００６８】
テーブル管理装置５は、テーブル面番号ｐをインクリメントした後に、テーブル面番号ｐが示す値と面数Ｐとの大小関係を算出する（ステップＳ３）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きくないときに（ステップＳ３、ｐ≦Ｐ）、ステップＳ４〜Ｓ５を繰り返して実行する。
【００６９】
テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きいときに（ステップＳ３、ｐ＞Ｐ）、乱数情報集合Ｚとパラメータリスト８と基づいて、複数（Ｐ個）のキー計算関数を算出する（ステップＳ６）。
【００７０】
ここで、乱数情報集合Ｚは、ステップＳ４が繰り返し実行されることにより収集された複数（Ｐ個）の乱数情報を示している。その複数のキー計算関数のうちのテーブル面番号ｐに対応するキー計算関数Ｌ（ｐ）（ｘ）は、Ｄ次元数ベクトルｘの関数である。
【００７１】
乱数情報集合Ｚは、以下の式により表現される。
Ｚ＝｛Ｚｐ｝（ｐ＝１，・・・，Ｐ）
【００７２】
キー計算関数Ｌ（ｐ）（ｘ）は、Ｄ次元数ベクトルｘを用いて、以下の式により表現される。
Ｌ（ｐ）（ｘ）＝（ｆ（ｐ）１（ｘ），・・・，ｆ（ｐ）Ｂ（ｘ））
ここで、基本関数ｆ（ｐ）ｂ（ｘ）は、前述の式により表現される（数１参照）。
【００７３】
テーブル管理装置５は、その複数（Ｐ個）のキー計算関数が算出された後に、エントリが空の複数（Ｐ個）のテーブルを作成する（ステップＳ７）。その複数のテーブルは、その複数のキー計算関数に対応している。テーブル管理装置５は、テーブル保持装置１０を制御することにより、その複数（Ｐ個）のテーブルをテーブル保持装置１０に記録する。
【００７４】
そのデータ登録動作は、その初期化動作が実行された後に実行される。ユーザは、まず、入力データ１２を用意し、入力装置１１を操作することにより、入力データ１２をテーブル管理装置５に入力する。入力データ１２は、データ集合Ｘを示している。
【００７５】
データ集合Ｘは、データｘｉから形成され、以下の式により表現される。
Ｘ＝｛ｘｉ｜ｘｉ∈ＲＤ｝（ｉ＝１，・・・，Ｎ）
ここで、集合ＲＤは、Ｄ次元数ベクトル空間を示している。自然数Ｎは、データ集合Ｘの要素であるデータｘｉの総数を示し、１より大きい自然数を示している。データｘｉは、Ｄ次元数ベクトルを示している。
【００７６】
テーブル管理装置５は、入力装置１１を介して入力データ１２が入力されると、記憶装置を制御することにより、入力データ１２をその記憶装置に記録する。
【００７７】
テーブル管理装置５は、入力装置１１を介して入力データ１２が入力されると、その初期化動作により作成された複数（Ｐ個）のテーブルに対応する複数（Ｐ個）のテーブル作成動作を実行する。その複数のテーブル作成動作のうちのテーブル面番号ｐに対応するテーブル作成動作は、データ集合Ｘに属する全てのデータに対応する複数（Ｎ個）のエントリ作成動作から形成されている。
【００７８】
その複数（Ｎ個）のエントリ作成動作のうちのあるデータｘｉに対応するエントリ作成動作では、テーブル管理装置５は、その初期化動作により作成された複数（Ｐ個）のキー計算関数のうちのテーブル面番号ｐに対応するキー計算関数Ｌ（ｐ）（ｘ）にデータｘｉを代入することによりキーＬ（ｐ）（ｘｉ）を算出する。テーブル管理装置５は、その初期化動作により作成された複数（Ｐ個）のテーブルのうちのテーブル面番号ｐに対応するテーブルに、キーＬ（ｐ）（ｘｉ）に対応するエントリが存在しているかどうかを判別する。
【００７９】
テーブル管理装置５は、そのテーブルにキーＬ（ｐ）（ｘｉ）に対応するエントリが存在するときに、そのエントリのバリューＴａｂｌｅ（ｐ）［Ｌ（ｐ）（ｘｉ）］が示すデータリストにデータｘｉを追加する。テーブル管理装置５は、そのテーブルにキーＬ（ｐ）（ｘｉ）に対応するエントリが存在しないときに、キーＬ（ｐ）（ｘｉ）に対応するエントリをそのテーブルに追加する。このとき、そのエントリのバリューＴａｂｌｅ（ｐ）［Ｌ（ｐ）（ｘｉ）］は、データｘｉのみを要素とするデータリストを示している。
【００８０】
テーブル管理装置５は、その複数（Ｎ個）のエントリ作成動作の全てを実行することにより、その複数（Ｐ個）のテーブルのうちのテーブル面番号ｐに対応するテーブルを作成する。テーブル管理装置５は、その複数（Ｐ個）のテーブル作成動作の全てを実行することにより、その複数（Ｐ個）のテーブルの全てを作成する。テーブル管理装置５は、テーブル保持装置１０を制御することにより、その複数のテーブルをテーブル保持装置１０に記録する。
【００８１】
このように作成されたテーブルでは、任意の２つのデータに対応する２つのキーがそれぞれ示す任意の２点が、指向パラメータｕｊが示す方向に沿った任意の距離重み（重要度）で測った距離が短いほど高い確率で同じエントリに登録される。
【００８２】
図４は、その検索動作を示している。ユーザは、まず、検索条件１６を用意し、入力装置１４を操作することにより、検索条件１６をデータ処理装置６に入力する。検索条件１６は、クエリｑと条件とを示している。その条件としては、「クエリｑの最近傍のデータを１つ取得する」「クエリｑに近いものからＫ個のデータを取得する」が例示される。データ処理装置６は、入力装置１４を介して検索条件１６が入力されると、記憶装置を制御することにより、検索条件１６をその記憶装置に記録する（ステップＳ１１）。データ処理装置６は、検索条件１６が入力されると、更に、クエリｑをテーブル管理装置５に出力することにより、テーブル管理装置５にデータリストを要求する（ステップＳ１２）。
【００８３】
テーブル管理装置５は、データ処理装置６からクエリｑが出力されると、テーブル面番号ｐに１を代入し、空のデータリストＬｉｓｔ＜ｘ＞＝φを用意する（ステップＳ１３）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐの大小関係を算出する（ステップＳ１４）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きくないときに（ステップＳ１４、ｐ≦Ｐ）、クエリｑに基づいて検索キーＬ（ｐ）（ｑ）を算出する（ステップＳ１５）。
【００８４】
検索キーＬ（ｐ）（ｑ）は、その初期化動作により算出された複数のキー計算関数のうちのテーブル面番号ｐに対応するキー計算関数Ｌ（ｐ）（ｘ）にクエリｑが代入されることにより算出される値を示している。
【００８５】
テーブル管理装置５は、そのデータ登録動作により作成された複数のテーブルのうちのテーブル面番号ｐに対応するテーブルを参照して、検索キーＬ（ｐ）（ｑ）に対応するバリューＴａｂｌｅ（ｐ）［Ｌ（ｐ）（ｑ）］を取得する（ステップＳ１６）。テーブル管理装置５は、バリューＴａｂｌｅ（ｐ）［Ｌ（ｐ）（ｑ）］が示すデータリストに属するデータをデータリストＬｉｓｔ＜ｘ＞に追加する（ステップＳ１７）。
【００８６】
ここで、テーブル管理装置５は、データリストＬｉｓｔ＜ｘ＞とバリューＴａｂｌｅ（ｐ）［Ｌ（ｐ）（ｑ）］とに重複して属するデータがあった場合に、バリューＴａｂｌｅ（ｐ）［Ｌ（ｐ）（ｑ）］が示すデータのうちのデータリストＬｉｓｔ＜ｘ＞に登録されていないデータのみをデータリストＬｉｓｔ＜ｘ＞に追加する。
【００８７】
テーブル管理装置５は、ステップＳ１７が実行された後に、テーブル面番号ｐを１だけインクリメントし、すなわち、テーブル面番号ｐが示す値に１を加算することにより算出された和をテーブル面番号ｐに代入する（ステップＳ１８）。テーブル管理装置５は、テーブル面番号ｐをインクリメントした後に、テーブル面番号ｐが示す値と面数Ｐとの大小関係を算出する（ステップＳ１４）。テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きくないときに（ステップＳ１４、ｐ≦Ｐ）、ステップＳ１５〜Ｓ１８を繰り返して実行する。
【００８８】
テーブル管理装置５は、テーブル面番号ｐが示す値が面数Ｐより大きいときに（ステップＳ１４、ｐ＞Ｐ）、データリストＬｉｓｔ＜ｘ＞をデータ処理装置６に出力する。こうして出来上がったデータリストＬｉｓｔ＜ｘ＞は、クエリｑの特定方向を適当な重みで重要視して距離計算した時に近距離となるデータの候補となっている。
【００８９】
データ処理装置６は、テーブル管理装置５によりデータリストＬｉｓｔ＜ｘ＞が出力されると、検索条件１６が示す条件とデータリストＬｉｓｔ＜ｘ＞とに基づいて検索結果データｘ＊を算出する（ステップＳ１９）。
【００９０】
検索結果データｘ＊は、データリストＬｉｓｔ＜ｘ＞に属するデータのうちのその条件が満足するデータの集合を示している。もし、その条件が「クエリｑに近いものからＫ個のデータを取得する」を示し、データリストＬｉｓｔ＜ｘ＞がＫ個以下のデータしか含まない場合には、検索結果データｘ＊は、データリストＬｉｓｔ＜ｘ＞の全てのデータを示している。なお、データリストＬｉｓｔ＜ｘ＞からクエリｑに近いデータを選択する計算としては、普通のユークリッド距離を用いても良いし、指向パラメータで指定した重要度を考慮して距離を計算しても良い。
【００９１】
データ処理装置６は、検索結果データｘ＊が算出された後に、出力装置１５を制御することにより、検索結果データｘ＊を出力装置１５に表示させる（ステップＳ２０）。
【００９２】
このような指向性近傍検出方法によれば、ユーザが興味の方向やその度合い等を示す関心情報を考慮して指向パラメータを設定しておくことで、類似性検出装置１は、高次元データにおいても、その関心に沿った中で、関心中心から近いデータを高速に優先的選択する指向性近傍検出が可能である。
【００９３】
既存手法では、同じ距離（類似度）にあるデータは同じ確率で選択するため、ある検索中心から同心球上の点は、全て同じ確率で検出される。そのため、ある興味方向にある距離ｒのデータだけを取り出すには、一度半径ｒの球内にあるデータを全て選択し、そこからある方向のみのものを優先的に取り出す必要がある。このような手法では、指向性が強くなるほど（ある方向の重要度の重みが他の方向の重要度の重みに比べて大きくなるほど）、不必要なデータを大量に取得しなければならず、その分計算時間が増大する。
【００９４】
それに対して、本発明による技術では、衝突確率等値線が等方的な球ではなく、衝突確率等値線が興味方向に長軸をもつ楕円体として制御できるため、任意の方向に任意の重みで指向性近傍検出を行うことが可能となり大幅な時間削減が望める。
【００９５】
なお、類似性検出装置１は、データ処理装置６が、乱数情報取得部２１と初期化部２２とデータ登録部２３と検索部２４とがそれぞれ実現される複数のコンピュータに置換されることができる。更に、類似性検出装置１は、パラメータ管理装置２と乱数発生装置３とテーブル管理装置５とデータ処理装置６とが実現される１つのコンピュータに置換されることもできる。更に、パラメータ管理装置２と乱数発生装置３とデータ処理装置６と乱数情報取得部２１と初期化部２２とデータ登録部２３と検索部２４とのいずれかが実現される複数のコンピュータから形成されることもできる。このように置換された類似性検出装置も、類似性検出装置１と同様にして、任意の方向に任意の重みで指向性近傍検出を行うことが可能となる。
【００９６】
次に、本発明による指向性近傍検出方法が二次元（Ｄ＝２）ユークリッド空間に適用される例を考える。例えば、図５に示されているように、集合Ｕが複数の指向パラメータ３６を複数の方向パラメータ３７と複数の強度パラメータ３８とに対応付けている例を考える。
【００９７】
複数の指向パラメータ３６は、２つの指向パラメータｕ１，ｕ２から形成されている。複数の方向パラメータ３７は、（１／ｓｑｒｔ（２）、１／ｓｑｒｔ（２））を示す方向パラメータｖ１と（−１／ｓｑｒｔ（２）、１／ｓｑｒｔ（２））を示す方向パラメータｖ２とから形成されている。複数の強度パラメータ３８は、２を示す強度パラメータσ１と１を示す強度パラメータσ１とから形成されている。指向パラメータｕ１は、方向パラメータｖ１を強度パラメータσ１に対応付けている。指向パラメータｕ２は、方向パラメータｖ２を強度パラメータσ２に対応付けている。
【００９８】
すなわち、集合Ｕは、以下の式により表現される。
Ｕ＝｛＜（１／ｓｑｒｔ（２）、１／ｓｑｒｔ（２））、２＞、＜（−１／ｓｑｒｔ（２）、１／ｓｑｒｔ（２））、１＞｝
【００９９】
このとき、方向パラメータｖ１は、図６に示されているように、ｘ軸から反時計回りに４５度傾いた方向を示している。方向パラメータｖ２は、方向パラメータｖ１が示す方向と直交する方向を示している。集合Ｕは、強度パラメータσ２が示す値の２倍の値を強度パラメータσ１が示すことから、方向パラメータｖ１の方向を方向パラメータｖ２の方向に比べて２倍重視することを意味する。
【０１００】
入力データ１２は、集合Ｘに属するデータの分布が任意とする。検索条件１６の条件としては、「クエリｑの入力に対して、クエリｑとの距離が最も近いデータである」ことを示す。
【０１０１】
このとき、衝突確率等値線３１は、方向パラメータｖ１の方向に長軸をもつ楕円に形成される。すなわち、衝突確率等値線３１の上のデータは、全て同じ確率で検出される。類似性検出装置１は、方向パラメータｖ２の方向に比べ、方向パラメータｖ１の方向に２倍遠い場所を同一視して、集合Ｘに属するデータから検索結果データを検索することができる。すなわち、類似性検出装置１は、検出確率を制御することができるため、方向パラメータｖ１の方向に強度パラメータσ１の重みで指向性近傍検出を行うことが可能となる。
【０１０２】
本発明による類似性検出装置の第２の実施の形態は、既述の実施の形態に記載されたパラメータリスト８が示す指向パラメータが他の指向パラメータに置換されている。
【０１０３】
その指向パラメータは、集合Ｕｋから形成される集合を示し、その集合は、以下の式により表現される。
｛Ｕｋ｝（ｋ＝１，・・・，Ｋ）
【０１０４】
集合Ｕｋは、以下の式により表現される。
Ｕｋ＝｛ｕｊ｜ｕｊ∈ＲＤ×Ｒ＋｝（ｊ＝１，・・・，Ｄ）
このとき、集合Ｕｋは、互いに異なる。すなわち、方向パラメータｖ又は強度パラメータσのどれかが異なっている。
【０１０５】
例えば、簡単のためＤ＝２の２次元の場合を考えると、集合Ｕｋは、以下の式により表現される。
Ｕｋ＝｛＜ｖｘ，σｘ２ｐ＞、＜ｖｙ，σｙ２ｐ＞｝
ここで、方向パラメータｖｘは、ｘ軸方向の単位ベクトルを示している。方向パラメータｖｙは、ｙ軸方向の単位ベクトルを示している。変数ｐは、０以上の整数を示している。強度パラメータσｘは、ｘ軸方向の基本重みを示している。強度パラメータσｙは、ｙ軸方向の基本重みを示している。
【０１０６】
例えば、指向パラメータＵとしては、図７に示されているように、ｐ＝０，１，２，３の４通りとし、（σｘ，σｙ）＝（１，３）、（３，１）の２通りとすると、Ｋ＝２×４＝８通りの指向パラメータ集合Ｕｋが指定される。
【０１０７】
このとき、その類似性検出装置は、その指向パラメータに基づいて、その指向パラメータが示す集合Ｕに属する複数の集合に対応する複数のキー計算関数集合を作成する。その複数のキー計算関数集合のうちの集合Ｕｋに対応するキー計算関数集合は、複数のキー計算関数を示している。その複数のキー計算関数は、既述の実施の形態における類似性検出装置１により集合Ｕに基づいて算出される複数のキー計算関数と同様にして、集合Ｕｋに基づいて算出される。
【０１０８】
その類似性検出装置は、入力データ１２とその複数のキー計算関数集合とに基づいて、図８に示されているように、その複数のキー計算関数集合５２に対応する複数のテーブルセット５１を作成する。複数のテーブルセット５１の任意のテーブルセットは、複数のテーブルから形成されている集合を示している。
【０１０９】
その複数のテーブルは、既述の実施の形態における複数のテーブルと同様にして、作成されている。すなわち、その複数のテーブルのうちの任意のテーブル面番号ｐに対応するテーブルは、複数のキーを複数のバリューに対応付けている。
【０１１０】
その複数のキーのうちの任意のキーは、その複数のキー計算関数のうちのテーブル面番号ｐに対応するキー計算関数Ｌ（ｐ）（ｘ）に、データ集合Ｘのうちのいずれかのデータｘが代入されることにより算出された値を示している。
【０１１１】
その複数のバリューのうちの任意のキーＬに対応するバリューＴａｂｌｅ（ｐ）［Ｌ］は、所定のデータの集合であるデータリストを示している。このとき、バリューＴａｂｌｅ（ｐ）［Ｌ］は、そのデータリストに属するデータのうちの任意のデータｘがキー計算関数Ｌ（ｐ）（ｘ）に代入されることにより算出された値がキーＬに一致するように、算出される。
【０１１２】
図９は、集合Ｕｋが指定する指向性をそれぞれ示す複数の衝突確率等値線を示している。その複数の衝突確率等値線は、それぞれ、方向パラメータの方向に長軸をもつ楕円に形成され、互いに異なっている。
【０１１３】
その複数の衝突確率等値線のうちの集合Ｕｋに対応する衝突確率等値線の上のデータは、図６に示される衝突確率等値線３１と同様にして、複数のテーブルセット５１のうちの集合Ｕｋに対応するテーブルセットが示す複数のテーブルを用いて、全て同じ確率で検出される。その類似性検出装置は、既述の最良の実施の形態で述べた方法と同様に、それぞれの指向パラメータに対応するテーブルを指定された面数だけ作成したテーブルを作成・管理する。
【０１１４】
ユーザは、その検索動作の際に、検索条件１６と異なる他の検索条件をその類似性検出装置に入力する。
【０１１５】
その検索条件は、指向性パラメータと検索条件１６が示すクエリと条件とを示している。その指向性パラメータは、方向と強度のペアの集合を示している。その類似性検出装置は、複数のテーブルセット５１からその指向性パラメータに一番近い指向パラメータを示す集合Ｕｋに対応するテーブルセットを選択する。その類似性検出装置は、そのテーブルセットに属する複数のテーブルを用いて複数の検索データリストを算出し、データリストＬｉｓｔ＜ｘ＞を算出する。
【０１１６】
その複数の検索データリストのうちのあるテーブルセットに対応する検索データリストは、そのテーブルセットの複数のバリューのうちのクエリのキーに対応するバリューが示すデータリストに一致している。データリストＬｉｓｔ＜ｘ＞は、その複数のテーブルセットに対応する複数の検索データリストを含んでいる。
【０１１７】
このような第２の実施の形態における類似性検出装置は、予め複数のテーブルセットを作成し、検索に合わせて利用するテーブルを選択する機能が設けられていることにより、事前に指向性パラメータが不明な場合でも、検索動作時に「この点のこちらの方向にこれくらいの強さで」という指向性パラメータを合わせて入力することで、指向性近傍検索が可能となる。
【０１１８】
なお、ここでは、８通りのみの指向性パラメータを持つテーブルを用意する例を示したが、一般には、もっと多くても良く、様々な方向や強度の組み合わせを用意しておくほど様々な検索要求に対して精度良い出力を返すことができる。そのテーブルセットの個数は、計算資源等とのトレードオフで決めれば良い。
【０１１９】
また、検索の指向性パラメータの指定として、この例では、検索者が指向性パラメータＵの書式（方向と強度のペアの集合）で入力するとしたが、これは、より直感的な入力を定義しデータ処理装置において指向性パラメータの書式に変換しても良い。
【０１２０】
より直感的な入力の例として、関心のない軸方向の単位長さと同一視する関心がある方向にそった長さを指定することで、検索の指向性を指定することも可能である（例えばｘ軸から４５°傾いた方向に沿った長さ１は、ｘ軸から−４５°傾いた方向に沿った長さ３に相当する場合は、ｘ軸から−４５°傾いた方向は４５°傾いた方向より実距離で３倍遠くても同じ確率で検出することになる）。
【０１２１】
更に、本例では、検索における指向性情報に対して、最適なテーブルを一つ選択して結果を出力する例を記載したが、複数のテーブルを組み合わせた指向性近傍検索結果を出力しても良い。具体的には、例えば、検索に指定された指向性情報と、テーブルの持つ指向性情報との距離を用いて、その重みで、各テーブルで行った近傍検索結果を表示しても良い。
【実施例１】
【０１２２】
本発明による指向性近傍検出方法における第２の実施例について詳細に説明する。本実施例では、ある特徴に関して類似する画像を高速検出する手法について説明する。【０１２３】
画像を示す画像データは、一般に、Ｄ次元特徴ベクトルで表現することが可能である。様々な手法が考えられるが、ここでは、一例として、図１０に示されているように、画像６１が適当なメッシュで複数の画素６２−１〜６２−１６に切られており、各画素６２−ｉで画素値を定義することによって表現される画像データを考える。【０１２４】
ここで、それぞれの画素における画素値をラスタ・スキャン（Ｒａｓｔｅｒ  ｓｃａｎ）して、画素値を並べることで特徴ベクトルを作成するとする。なお、ラスタ・スキャンでは、左上からはじめて、左から右に順に値を読んでいき、右端までいったら一段おりて同じことを繰り返す。【０１２５】
例えば、４ｘ４の画素に区切られた任意の画像の特徴ベクトルｕは、１６次元ベクトルで表現される。例えば、１６個の単位ベクトルｅ１〜ｅ１６と１６個の画素値とを用いて、以下の式により表現される。
【数２】
2013051619.tif 000004
ここで、単位ベクトルｅｉは、ｉ番目の成分のみが１を示し、あとの成分が０を示すベクトルである。【０１２６】
ここで、ユーザは、ある特徴方向に関してのみ興味があるとする。一番簡単には、ユーザは、画像６１のうちのある一部分である興味領域６３のみに関心があり、それ以外の類似性を無視するような場合が考えられる。その場合、ユーザは、特徴ベクトルｕの第１成分と第２成分と第５成分と第６成分とのみを重視し、他の画素を重視しないことになる。【０１２７】
ここで、重視する重みを１０倍とすると（非興味方向に沿った距離の１に対して興味方向に沿った距離の１０を同一視すると）、指向性パラメータＵ＝｛ｕｉ＝＜ｖｉ、σｉ＞｝ｉ＝１，・・・，１６をｖｉ＝ｅｉ、σｉ＝１０（ｉ＝１，２，５，６），１（その他）と設定する。この指向性パラメータＵを用いて、既述の最良の実施の形態に示した指向性近傍検出を行うことで、あるクエリ画像ｑの入力に対して、第１、２、５，６番目の画素の類似性を重視した類似画像検索が可能である。【０１２８】
更に、本発明による指向性近傍検出方法は、一般に、画素を適当な割合で組み合わせを特徴方向として類似画像の検出を行うことも可能である。例えば、第１，２，５，６番目の画素値の比率の類似性を重視する場合を考える。【０１２９】
興味方向として、第１，２，５，６番目の画素を同じ重みで足し合わせた方向パラメータｖ１を、以下の式により定義する。
ｖ１＝（ｅ１＋ｅ２＋ｅ５＋ｅ６）／２【０１３０】
方向パラメータｖ１は、グラム・シュミットの直交化法等を用いれば、方向パラメータｖ１と｛ｅｉ｝ｉ＝２，・・・，１６とから、互いに直交する正規直交座標系｛ｖ１，ｖ２，・・・，ｖ１６｝を構成することができる。【０１３１】
先の例と同様に方向パラメータｖ１の方向を他の方向に比べて１０倍重視する場合、指向性パラメータＵをＵ＝｛ｕｉ＝＜ｖｉ、σｉ＞｝（ｉ＝１，・・・，１６）をσｉ＝１０（ｉ＝１），１（その他）と設定することにより、第１，２，５，６番目の画素値の比率が同じ画像を類似画像として検出することができる。これは、例えば画素値として色の濃さを０〜１の実数値で表したときに、対象部分の濃さの比率が近ければ、対象部分以外の画素値の違いが多少大きくても類似画像として検出されることになる。
【実施例２】
【０１３２】
次いで、本発明による指向性近傍検出方法における第２の実施例について詳細に説明する。本実施例では、多次元関数の局所的特徴に着目した類似関数検索を行う。典型的な例として、多次元ベクトルの集合で表現される時系列データ｛ｖ（ｔｉ）｝ｉ＝１，２，・・・を考える。【０１３３】
ここで、ｖ（ｔｉ）は、時刻ｔｉにおける多次元ベクトルを示している。その時系列データとしては、ある地点で、時刻ｔｉに測定された加速度センサーのそれぞれｘ軸方向，ｙ軸方向，ｚ軸方向の加速度の値を３次元ベクトルとして表現したものが例示される。その場合、３次元ベクトル空間上における時刻をパラメータにした点の集合が時系列データとなる。【０１３４】
本実施例は、大量な時系列データ（例えば、大量の地点での加速度データの時系列データ）の中で、あるクエリとなる時系列データに対して、その部分的な領域のみで類似する時系列データを高速検索する。【０１３５】
図１１は、本実施例で検索対象となる複数の時系列データ７１−１〜７１−Ｔを示している。ユーザは、まず、複数の時系列データ７１−１〜７１−Ｔを本実施例における類似性検出装置に入力する。その類似性検出装置は、第２の実施の形態における類似性検出装置と同様にして、複数の指向パラメータに対応する複数のテーブルに時系列データの各点を順次登録する。【０１３６】
ここで、その複数の指向パラメータは、簡単に、ｘ軸方向に長軸をもちｙ軸方向に短軸をもつ指向パラメータと、その長軸から９０度回転した方向に指向性をもつ他の指向パラメータとの２種類とする。指向パラメータの強度は、一般に、複数指定可能だが、ここでは、例えば３：１の比率で設定するものとする。【０１３７】
その類似性検出装置は、図１２に示されているように、その複数の指向パラメータ７４に対応する複数のテーブルセット７５を作成する。ここで、複数のテーブルセット７５の各テーブルセットに属するテーブルの数は、Ｋ個とする。その類似性検出装置は、既述の実施の形態における類似性検出装置と同様にして、全てのテーブルに、時系列データの各点に対するキーを計算してバリューに登録する。【０１３８】
検索のときは、ユーザは、図１３に示されているように、時系列データ７６を入力し、時系列データ７６のうちの興味領域（検索対象領域）を示す検索範囲パラメータ７７をクエリとして指定する。ここで、検索範囲パラメータ７７は、時系列データ７６の興味領域が指定できれば良い。例えば、座標値の範囲を示すデータでも良いし、各データのパラメータ（例えば、時刻ｔ等）の範囲を示すデータでも良い。また、検索範囲パラメータ７７は、時系列データ７６のなかから興味領域の範囲内のデータのみ抜き出した部分時系列データそのものでも良い。【０１３９】
その類似性検出装置は、既述の実施の形態における類似性検出装置と同様にして、複数のテーブルセット７５のうちのユーザにより選択されたテーブルセットに属する複数のテーブルを参照して、図１４に示されているような時系列データ７８を抽出し、時系列データ７８がユーザ認識可能に表現されるように出力装置１５を制御する。時系列データ７８は、その複数のテーブルに対応する複数の検索データリストに含まれるデータから形成されている。その複数の検索データリストのうちのあるテーブルに対応する検索データリストは、そのテーブルに対応するキー計算関数にそのクエリが代入されることにより算出されるクエリ値に対応するバリューが示すデータリストを示している。【０１４０】
本発明による指向性近傍検出方法における他の実施例について詳細に説明する。本実施例では、範囲限定類似関数検索を行うための、入力される時系列データと任意の時系列データの、その範囲を限定した類似度を判定する機能について、以下に詳細に説明する。簡単のため、ここでは、図１５に模式的に示される２次元空間における時系列データ８１に対する時系列データ８２の類似度を計算することを考える。ここで、検索範囲の限定として、両者の時系列データのうちのユーザにより指定された時間間隔［ｔｍｉｎ：ｔｍａｘ］に属する部分のみの局所的な特徴を比較することを考える。【０１４１】
時系列データ８１は、その時間間隔に属するデータとして、｛Ｓｉ｝ｉ＝１，・・・，９を有している。時系列データ８２は、その時間間隔に属するデータとして、｛Ｒｉ｝ｉ＝１，・・・，６を有している。このとき、図１６に示されているように、時系列データ８１から範囲限定された部分時系列データ８３は、｛Ｓｉ｝ｉ＝１，・・・，９から形成され、時系列データ８２から範囲限定された部分時系列データ８４は、｛Ｒｉ｝ｉ＝１，・・・，６から形成される。【０１４２】
ここで、ユーザは、更に、部分時系列データ８３の点群｛Ｓｉ｝ｉ＝１，・・・，９から中心的な参照点８５をクエリとして抽出する。参照点８５は、部分時系列データ８３を最も良く代表する点であり、例えば全ての点の平均でも良いし、平均に一番近い点でも良いし、最大・最小値の平均（この例ではＳ１とＳ９の平均）等でも良い。【０１４３】
次に、その類似性検出装置は、参照点８５と、部分時系列データ８３及び部分時系列データ８４の各点が複数のテーブルセット７５の各々に属する複数のテーブルにおいて同じエントリに登録される確率（衝突確率）を計算し、複数の指向パラメータ７４に対応する複数の衝突確率分布を算出する。その複数の衝突確率分布は、それぞれ、参照点８５から部分時系列データ８３と部分時系列データ８４とに属する各データまでの距離の関数を示している。【０１４４】
図１７は、複数の指向パラメータのうちの第１指向パラメータに対応する衝突確率等値線を示している。その衝突確率等値線８６は、ｘ軸方向に長軸をもちｙ軸方向に短軸を有している。図１８は、その複数の指向パラメータのうちの第２指向パラメータに対応する衝突確率等値線を示している。その衝突確率等値線８７は、ｘ軸方向に長軸をもちｙ軸方向に短軸を有している。【０１４５】
図１９は、衝突確率分布を示している。その衝突確率分布８８は、部分時系列データ８３と部分時系列データ８４とに属する各データが参照点８５とその第１指向パラメータに基づいて算出されたテーブルで同じエントリに登録される衝突確率を示している。【０１４６】
図２０は、他の衝突確率分布を示している。その衝突確率分布８９は、部分時系列データ８３と部分時系列データ８４とに属する各データが参照点８５とその第２指向パラメータに基づいて算出されたテーブルで同じエントリに登録される衝突確率を示している。【０１４７】
これらの値は、各指向性パラメータの全テーブル数Ｋに対して、実際に両者が衝突していた（同じエントリに登録されていた）数Ｌを測定し、Ｌ／Ｋで衝突確率を計算することで近似される。衝突確率分布８８と衝突確率分布８９とは、時系列データの各点と参照点８５の衝突確率が、両者の場所の位置関係と指向性パラメータの示す方向や強度によって異なる値を取ることを示している。衝突確率分布８８と衝突確率分布８９とは、この衝突確率分布は、比較する二つの部分時系列データが近いほど同じ形をとるため、この形の違いを比較することで任意の二つの部分時系列データの類似性を評価することが可能である。【０１４８】
図２１は、特徴分布を示している。その特徴分布９０は、衝突確率分布８８と衝突確率分布８９とでの各部分時系列データの衝突確率の差を示し、各部分時系列データの特徴分布９０の形は、類似度を部分時系列データの類似度として評価されることができる。この類似度の計算には、滑らかに補間した関数間の内積を計算する方法、もしくは、Ｅａｒｔｈ  Ｍｏｖｅｒ’ｓ  Ｄｉｓｔａｎｃｅのような距離評価尺度を使う方法等が考えられるが、これに限るものではなく、関数の形（ある距離が与えられた時の関数値）の類似度が定量的に評価できるものであれば良い。【０１４９】
上記の手法によって、クエリで指定された時系列データに対して、指定された検索範囲に限定した時に、一番類似性の高い時系列データを抽出することが可能である。具体的には、クエリで指定された部分時系列データから参照点を計算し、複数のテーブルセット７５に属する全てのテーブルにおける参照点と衝突するデータの中で検索範囲内のもののみを抽出（本例では時間が指定された時間範囲のものを抽出）し、各時系列データに対応する衝突確率分布を作成し、クエリで指定された部分時系列データの衝突確率分布との類似性を評価すれば良い。【０１５０】
ここで、本例では検索範囲の指定を連続した一つの区間としたが、一般に複数の区間で行うことも、それぞれの区間で同様の手法を適用し、各区間における類似性を合わせて評価することで容易に実現可能である。【０１５１】
次に本実施例における効果を説明する。本実施例によれば、実際のクエリと範囲の入力に対して、検索対象の全ての時系列データの中から最も類似する時系列データの抽出処理を大幅に高速化することが可能である。【０１５２】
なぜなら、通常の手法では、検索範囲のみを取り出した全ての部分時系列データとクエリの部分時系列データの比較をオンラインで行わなくてはいけないため、検索対象データ数が増加すると計算時間も増加し、応答速度が遅くなってしまう。【０１５３】
しかし、本実施例によれば、検索対象の時系列データは予めオフラインでテーブルに登録しておくことが可能であり、オンライン処理で実際に評価が必要なのは、参照点と衝突するデータによって構成される時系列データ及びその対応する衝突確率分布のみであるからである。特に検索対象時系列データの数が膨大の時に、対象データ数の大幅な削減が期待できる。【０１５４】
なお、本実施例では、時刻をパラメータとして扱ったが、例えば、時刻自体を適当に定数倍したり、時刻に適当な変換を施したりして時系列データの値と比較できる形で座標値の一つとして取り組んで検索を行うことも可能である。
【実施例３】
【０１５５】
次に本発明の第三の実施例について詳細に説明する。第三の実施例では、本発明による類似性検出装置は、図２２に示されているように、移動体管理システム１００に適用されている。【０１５６】
移動体管理システム１００は、ネットワーク１０３を介して、複数のコンピュータが互いに双方向に情報を伝送することができるように接続されている。ネットワーク１０３としては、インターネット、携帯電話網等が例示される。その複数のコンピュータは、移動体管理装置１０１と複数の移動体端末１０２−１〜１０２−３とを含んでいる。複数の移動体端末１０２−１〜１０２−３は、それぞれ、ユーザにより携帯され、現在位置情報を取得できるデバイスである。そのデバイスとしては、スマートフォンやＧＰＳロガー等が例示される。【０１５７】
移動体管理装置１０１は、既述の実施の形態における類似性検出装置を備え、複数の移動体端末１０２−１〜１０２−３の移動方向を管理し、似た方向に進んでいる移動体端末をグルーピングする機能を提供する。例えば、移動体管理装置１０１は、複数の移動体端末１０２−１〜１０２−３の各移動体端末に関してその現在位置と適当な時間τだけ前にいた位置のペアを管理する。ここで、簡単のため扱う空間を２次元空間とし、検出したい主たる移動方向をｘ軸方向とし、ｙ軸方向に比べｘ軸方向に適当に指向性を持たせるように強度を設定した指向性パラメータを設定する。強度の例として例えば、ｘ軸方向へはｖτの定数倍とし、ｙ軸方向は例えばｘ軸方向の強度の０．１倍等とすることで、ｘ軸方向の強度は検出したい速度上限を規定し、ｙ軸方向は方向のぶれの許容範囲を規定することができる。【０１５８】
複数の移動体端末１０２−１〜１０２−３は、ある時刻ｔにそれぞれ位置１０１０，位置１０２０，位置１０３０に存在し、時刻ｔ＋τにそれぞれ位置１０１１，位置１０２１，位置１０３１に移動したとする。複数の移動体端末１０２−１〜１０２−３は、ＧＰＳによって現在位置を取得し、定期的にネットワーク１０３を通して移動体管理装置１０１に位置情報をアップロードする。【０１５９】
移動体管理装置１０１は、既述の実施の形態における類似性検出装置と同様にして、図２３に示されているように、複数の指向性パラメータ１１１に対応する複数のテーブルセット１１２を作成する。移動体管理装置１０１は、複数のテーブルセット１１２を用いて複数の移動体端末１０２−１〜１０２−３の位置を管理し、位置１０１０，位置１０１１，位置１０２０，位置１０２１，位置１０３０，位置１０３１に対して各テーブルのキーを計算し、そのキーに対応するバリューに登録する。移動体管理装置１０１は、このテーブルセットを用いて、複数の移動体端末１０２−１〜１０２−３のうちのｘ軸方向に進む移動体端末をグループ化し、そのグループの特性に関する情報を含む移動体グループ情報１０５を出力する。【０１６０】
次に、移動体管理装置１０１がこの移動体グループ情報１０５を作成する手法を説明する。もし、移動体端末がｘ軸方向に想定速度程度の速度で移動していれば、時刻ｔと時刻ｔ＋τにおける位置座標は、同じキーを持つ可能性が高いが、直交するｙ軸方向に移動している移動体端末は、異なるキーを持つ可能性が高いため、両者を区別することができる。【０１６１】
本実施例では、移動体端末１０２−１と移動体端末１０２−２の位置情報である位置１０１０，位置１０１１，位置１０２０，位置１０２１は、同じエントリに登録され、移動体端末１０２−３の位置情報である位置１０３０及び位置１０３１は異なるエントリに登録される可能性が高い。そのため、ｘ軸方向に同じような速度で移動している移動体端末１０２−１及び移動体端末１０２−２を同じグループとしてグルーピングすることが可能となる。【０１６２】
本例では、１種類の指向性パラメータのみの場合を示したが、一般には、複数の指向性パラメータを指定することで、複数の関心方向や、複数の移動速度上限を設定することが可能であり、様々な移動体端末のグルーピングポリシーを作成することが可能である。【０１６３】
また、ある移動体端末に注目し、その移動体端末が登録されているテーブルエントリをモニターすることで、この移動体端末と並走する他の移動体端末を検出することもできる。例えば、検索対象移動体端末の入力に対して、過去もしくは現在に、この検索対象移動体端末と同じグループに属する移動体端末を並走移動体端末として出力することができる。【０１６４】
その際に、必要ならばグルーピングポリシーを合わせて設定することで、そのポリシーに合わせてグルーピングを修正することも可能である。例えば、グルーピングポリシーとして、「検索対象移動体端末と過去１０分以上半径１００ｍ以内に存在しながら並走した移動体端末」のように設定すれば、本発明によって出力された移動体端末グループの中から条件を満足させるもののみをフィルタリングして出力すれば良い。【０１６５】
更に、移動体端末の数が大量であった時は、各テーブルの各エントリに登録された移動体端末のうち、時刻ｔと時刻ｔ＋τにおける位置のどちらも同じエントリに登録されているものの数を数え、その数の多い順に適当な数だけエントリに登録された移動体端末の集合を抽出する。【０１６６】
これは、全移動体端末の中から、同じ方向に沿って進む移動体端末をその合計数が多いグループからサンプリングすることを意味する。それらのサンプルされた移動体端末をその移動方向や速度からグルーピングすることで、システム全体の移動体端末移動パターンの主たる傾向（多くの移動体端末がどの方向にどれくらいの速度で移動しているか、等）を取り出して、その移動体端末グループのサイズや方向・速度等の移動体端末グループ情報を作成し、移動体端末の移動状態を分類・表示ことが可能である。【０１６７】
次に、本実施例の効果について述べる。移動体管理システム１００は、基本的に、移動体端末の位置アップデートに対して管理するテーブルを更新し、上記の方法でテーブルから関心の高い移動体端末をサンプリングしてグルーピングを行うため、全ての移動体端末の移動に関する相互関係を計算してグルーピングする必要がない。そのため移動体端末数が増加してもその計算負荷の増加を抑えることができ、計算時間の大幅な削減が望める。【０１６８】
なお、本発明で示した全ての実施の形態及び実施例においては、テーブルのキーの計算方法として、既述の実施の形態におけるキー計算関数Ｌ（ｐ）（ｘ）と基本関数ｆ（ｐ）ｂ（ｘ）とランダムベクトルΦ（ｐ）ｂとを用いたが、指向性を指定するパラメータによって、望む方向・強度に対応する非対称性が導入されたものであればこれに限るものではない。【０１６９】
なお、本発明で示した全ての実施の形態及び実施例では、テーブルにおけるデータの衝突は、厳密に同じエントリに登録されるとして説明したが、バリエーションとしてテーブルのエントリ距離を定義し、近くのエントリ（例えば、キー計算関数Ｌ（ｐ）（ｘ）であらわされるキーの一ビットだけ異なる「隣のエントリ」等）までに登録されているデータは衝突すると衝突範囲を拡大しても良い。【０１７０】
＜備考＞
以上、本発明の実施の形態及び実施例を詳述してきたが、実際には、上記の実施の形態及び実施例に限られるものではなく、本発明の要旨を逸脱しない範囲の変更があっても本発明に含まれる。【０１７１】
＜付記＞
上記の実施の形態及び実施例の一部又は全部は、以下の付記のように記載することも可能である。但し、実際には、以下の記載例に限定されない。【０１７２】
［付記１］
入力装置を介して入力された複数の方向パラメータと複数の強度パラメータとに基づいて複数の乱数情報を算出する乱数発生部と、
前記複数の乱数情報に基づいて複数のキー計算関数を算出する初期化部と、
入力装置を介して入力された複数の検索対象データに基づいて、前記複数のキー計算関数に対応する複数のテーブルを算出し、前記複数のテーブルをテーブル保持装置に記録するデータ登録部と、
前記複数のテーブルを参照して、入力装置を介して入力された検索条件が示すクエリに基づいて候補データリストを算出する検索部と、
前記候補データリストに属する複数の検索データから前記検索条件が示す条件を満足する検索結果データを算出し、前記検索結果データを出力装置に出力するデータ処理部と
を具備し、
前記データ登録部は、前記複数のテーブルのうちの任意のキー計算関数に対応するテーブルを算出する際、複数のキーを複数のデータリストに対応付け、前記複数のデータリストのうちの任意のキーに対応するデータリストに属するデータを前記任意のキー計算関数に代入することにより算出される値が前記任意のキーに等しくなるように該テーブルを算出し、
前記候補データリストは、前記複数のキー計算関数に対応する複数の検索データリストを含み、
前記複数の検索データリストのうちの前記任意のキー計算関数に対応する検索データリストは、前記複数のデータリストのうちの、前記クエリが前記キー計算関数に代入されることにより算出されるクエリ値に対応するデータリストを示す
類似性検出装置。【０１７３】
［付記２］
付記１に記載の類似性検出装置であって、
前記データ登録部は、前記複数の検索対象データに基づいて複数のテーブルセットを更に算出し、
前記検索部は、前記複数のテーブルセットのうちの前記検索条件が示すテーブルセットが前記複数のテーブルを示すときに、前記複数のテーブルを参照して前記候補データリストを算出する
類似性検出装置。【０１７４】
［付記３］
付記１乃至２のいずれかに記載の類似性検出装置であって、
前記複数の方向パラメータは、前記複数の検索対象データのうちの類似する２つの状態変化類似データが前記任意のキー計算関数に代入されることによりそれぞれ算出される２つの値が等しくなるように、又は、前記２つの値の差が所定の値より小さくなるように、設定される
類似性検出装置。【０１７５】
［付記４］
付記１乃至３のいずれかに記載の類似性検出装置であって、
前記複数の検索対象データは、それぞれ画像を示す
類似性検出装置。【０１７６】
［付記５］
付記１乃至４のいずれかに記載の類似性検出装置であって、
前記データ登録部は、前記複数の検索対象データが更新されたときに、前記複数のテーブルを更新する
類似性検出装置。【０１７７】
［付記６］
入力装置を介して入力された複数の方向パラメータと複数の強度パラメータとに基づいて複数の乱数情報を算出するステップと、
前記複数の乱数情報に基づいて複数のキー計算関数を算出するステップと、
入力装置を介して入力された複数の検索対象データに基づいて、前記複数のキー計算関数に対応する複数のテーブルを算出するステップと、
前記複数のテーブルをテーブル保持装置に記録するステップと、
前記複数のテーブルを参照して、入力装置を介して入力された検索条件が示すクエリに基づいて候補データリストを算出するステップと、
前記候補データリストに属する複数の検索データから前記検索条件が示す条件を満足する検索結果データを算出するステップと、
前記検索結果データを出力装置に出力するステップと、
前記複数のテーブルのうちの任意のキー計算関数に対応するテーブルを算出する際、複数のキーを複数のデータリストに対応付け、前記複数のデータリストのうちの任意のキーに対応するデータリストに属するデータを前記任意のキー計算関数に代入することにより算出される値が前記任意のキーに等しくなるように該テーブルを算出するステップと
を具備し、
前記候補データリストは、前記複数のキー計算関数に対応する複数の検索データリストを含み、
前記複数の検索データリストのうちの前記任意のキー計算関数に対応する検索データリストは、前記複数のデータリストのうちの、前記クエリが前記キー計算関数に代入されることにより算出されるクエリ値に対応するデータリストを示す
指向性近傍検出方法。【０１７８】
［付記７］
付記６に記載の指向性近傍検出方法であって、
前記複数の検索対象データに基づいて複数のテーブルセットを更に算出するステップと、
前記複数のテーブルセットのうちの前記検索条件が示すテーブルセットが前記複数のテーブルを示すときに、前記複数のテーブルを参照して前記候補データリストを算出するステップと
を更に具備する
指向性近傍検出方法。【０１７９】
［付記８］
付記６乃至７のいずれかに記載の指向性近傍検出方法であって、
前記複数の方向パラメータは、前記複数の検索対象データのうちの類似する２つの状態変化類似データが前記任意のキー計算関数に代入されることによりそれぞれ算出される２つの値が等しくなるように、又は、前記２つの値の差が所定の値より小さくなるように、設定される
指向性近傍検出方法。【０１８０】
［付記９］
付記６乃至８のいずれかに記載の指向性近傍検出方法であって、
前記複数の検索対象データは、それぞれ画像を示す
指向性近傍検出方法。【０１８１】
［付記１０］
付記６乃至９のいずれかに記載の指向性近傍検出方法であって、
前記複数の検索対象データが更新されたときに、前記複数のテーブルを更新するステップ
を更に具備する
指向性近傍検出方法。【０１８２】
［付記１１］
大量の検索対象データに対して、任意の類似度判定基準で類似するデータを高速に検出する類似性検出装置であり、
前述の類似性検出装置は、前述の検索対象データを登録・管理するための、類似度判定基準を設定するパラメータによって作成される乱数情報と関連付けられたテーブルを保持し、
任意の参照点からの近傍検索要求に対して、前述のテーブルを利用し、前述の設定された類似度判定基準によって類似性判断を行い、近傍と判断されるデータを出力する
ことを特徴とする類似性検出装置。【０１８３】
［付記１２］
付記１１に記載の類似性検出装置において、複数の異なる類似度判定基準を有し、それぞれの類似度判定基準と関連付けられた複数のテーブルを有し、検索対象データを全てのテーブルで並列に管理する
ことを特徴とする類似性検出装置。【０１８４】
［付記１３］
付記１１に記載の類似度判定基準として、興味の方向と、その方向の重要度パラメータの組の集合とする
ことを特徴とする類似性検出装置。【０１８５】
［付記１４］
付記１１に記載の検索対象データとして、任意の２点の距離がユークリッド空間上の距離として定義されている
ことを特徴とする類似性検出装置。【０１８６】
［付記１５］
付記１２に記載の類似性検出装置において、検索においてその検索中心とともに検索類似度判定基準を入力し、複数のテーブルにおける近傍検出結果と、各テーブルに指定された類似度判定基準パラメータと検索類似度判定基準との関連性とを用いて出力する近傍を決定する
ことを特徴とする類似性検出装置。【０１８７】
［付記１６］
付記１１又は付記１２に記載の検索対象データとして、予めその値が静的に固定されたデータだけでなく、動的にその値を更新するデータであり、値の更新に合わせて前述のテーブルの登録状態を更新する
ことを特徴とする類似性検出装置。【０１８８】
［付記１７］
付記１１又は付記１２に記載の類似性検出装置として、前述のテーブルを用いた類似性判断結果を利用して、各データの状態変化が類似するものをグルーピングする
ことを特徴とする類似性検出装置。【０１８９】
［付記１８］
付記１１に記載のテーブルは、キーとバリューのペアで構成され、ある任意のデータの登録に当たって、前記乱数情報を用いてデータを登録すべきキーを計算し、対応するバリューに当たるデータのリストに追加登録することでデータを管理する
ことを特徴とする類似性検出装置。【０１９０】
［付記１９］
付記１１に記載の類似性判断として、同一もしくは差異の小さいキーを持つデータ同士を類似性が高いと扱う
ことを特徴とする類似性検出装置。【０１９１】
なお、本出願は、日本出願番号２０１１−２１９５４７に基づく優先権を主張するものであり、日本出願番号２０１１−２１９５４７における開示内容は引用により本出願に組み込まれる。
【図１】
2013051619.tif 000005
【図２】
2013051619.tif 000006
【図３】
2013051619.tif 000007
【図４】
2013051619.tif 000008
【図５】
2013051619.tif 000009
【図６】
2013051619.tif 000010
【図７】
2013051619.tif 000011
【図８】
2013051619.tif 000012
【図９】
2013051619.tif 000013
【図１０】
2013051619.tif 000014
【図１１】
2013051619.tif 000015
【図１２】
2013051619.tif 000016
【図１３】
2013051619.tif 000017
【図１４】
2013051619.tif 000018
【図１５】
2013051619.tif 000019
【図１６】
2013051619.tif 000020
【図１７】
2013051619.tif 000021
【図１８】
2013051619.tif 000022
【図１９】
2013051619.tif 000023
【図２０】
2013051619.tif 000024
【図２１】
2013051619.tif 000025
【図２２】
2013051619.tif 000026
【図２３】
2013051619.tif 000027
【国際調査報告】
2013051619.tif 000028
2013051619.tif 000029
2013051619.tif 000030
2013051619.tif 000031