"コンピュータが、画像に係るデータからそのデータの特徴を表す特徴ベクトルを抽出する工程と、抽出された特徴ベクトルを前記データと共にデータベースに登録する登録工程とを備え、前記データベースは、検索質問として画像に係るデータが与えられたとき、そのデータからクエリベクトルを抽出し、クエリベクトルから最も近いと推測される特徴ベクトルの探索を行うために用いられ、前記登録工程は、各特徴ベクトルを複数のビンの何れか一つに分類して登録するためのハッシュテーブルを、k個を一組の単位としてL組k,Lは2以上の整数生成し、各特徴ベクトルをそれらのハッシュテーブルにそれぞれ登録した後に、i登録されたある特徴ベクトルを選んでその特徴ベクトルと同じビンである登録ビンに分類された他の特徴ベクトルを特定し、ii各組ごとに、その組のk個の登録ビンのいずれにも登録されている他の特徴ベクトルの集合をその組のバケットとし、iii全L個のバケットのうち所定個以上のバケットに入っている特徴ベクトルを得、iv得られた特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録し、所定数の特徴ベクトルについて前記i~ivによる追加登録を実行した後、第1組を除く各組のハッシュテーブルを削除することを特徴とするデータベースの登録方法。前記探索は、クエリベクトルにハッシュ関数を適用して、第1組の各ハッシュテーブルについて対応するk個のビンを決定し、それらのビンのいずれにも登録されている特徴ベクトルの集合を求め、前記クエリベクトルをその集合に属する各特徴ベクトルと照合する請求項1に記載の方法。前記登録工程は、追加登録を行うために選択する特徴ベクトルを、一様乱数を用いて決定する請求項1または2に記載の方法。前記登録工程は、追加登録を行おうとする特徴ベクトルが、第1組のバケットに既に登録されているときは、その特徴ベクトルのさらなる追加登録を行わない請求項1~3のいずれか一つに記載の方法。前記登録工程は、予め定められたkおよびLの値に基づいて処理を行い、登録すべき特徴ベクトルのうち予め定められた割合の数だけ、追加登録を行う特徴ベクトルを選択し、予め定められた個数以上のバケットに入った特徴ベクトルを追加登録する請求項1~4のいずれか一つに記載の方法。前記データベースは、各特徴ベクトルのベクトルデータと各特徴ベクトルの識別子とが対応付けられた対応表および各ハッシュテーブルを含み、各ハッシュテーブルは、各ビンに登録される各特徴ベクトルを対応する識別子を用いて表す請求項1~5のいずれか一つに記載の方法。前記探索は、クエリベクトルと各特徴ベクトルとの距離を計算し、計算された距離に基づいてクエリベクトルから最も近いと推測される特徴ベクトルを決定する請求項1~6のいずれか一つに記載の方法。画像に係るデータからそのデータの特徴を表す特徴ベクトルを抽出する処理部と、抽出された特徴ベクトルを前記データと共にデータベースに登録する登録部とを備え、前記データベースは、検索質問として画像に係るデータが与えられたとき、そのデータからクエリベクトルを抽出し、クエリベクトルから最も近いと推測される特徴ベクトルの探索を行う探索装置に用いられ、前記登録部は、各特徴ベクトルを複数のビンの何れか一つに分類して登録するためのハッシュテーブルを、k個を一組の単位としてL組k,Lは2以上の整数生成し、各特徴ベクトルをそれらのハッシュテーブルにそれぞれ登録した後に、i登録されたある特徴ベクトルを選んでその特徴ベクトルと同じビンである登録ビンに分類された他の特徴ベクトルを特定し、ii各組ごとに、その組のk個の登録ビンのいずれにも登録されている他の特徴ベクトルの集合をその組のバケットとし、iii全L個のバケットのうち所定個以上のバケットに入っている特徴ベクトルを得、iv得られた特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録し、所定数の特徴ベクトルについて前記i~ivによる追加登録を実行した後、第1組を除く各組のハッシュテーブルを削除することを特徴とするデータベースの登録装置。近似最近傍探索では、精度最近傍データが正しく求まる確率、計算時間、メモリ使用量にトレードオフの関係があると考えられる。そのため、ある一定の精度を実現するために必要な計算時間とメモリ使用量が問題となる。この発明は、以上のような事情を考慮してなされたものであって、近似最近傍探索の一手法であるLSHに基づいて、同一精度を実現するために必要な計算時間とメモリ使用量を従来よりも削減できる手法を提供するものである。この発明は、コンピュータが、画像に係るデータからそのデータの特徴を表す特徴ベクトルを抽出する工程と、抽出された特徴ベクトルを前記データと共にデータベースに登録する登録工程とを備え、前記データベースは、検索質問として画像に係るデータが与えられたとき、そのデータからクエリベクトルを抽出し、クエリベクトルから最も近いと推測される特徴ベクトルの探索を行うために用いられ、前記登録工程は、各特徴ベクトルを複数のビンの何れか一つに分類して登録するためのハッシュテーブルを、k個を一組の単位としてL組k,Lは2以上の整数生成し、各特徴ベクトルをそれらのハッシュテーブルにそれぞれ登録した後に、i登録されたある特徴ベクトルを選んでその特徴ベクトルと同じビンである登録ビンに分類された他の特徴ベクトルを特定し、ii各組ごとに、その組のk個の登録ビンのいずれにも登録されている他の特徴ベクトルの集合をその組のバケットとし、iii全L個のバケットのうち所定個以上のバケットに入っている特徴ベクトルを得、iv得られた特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録し、所定数の特徴ベクトルについて前記i~ivによる追加登録を実行した後、第1組を除く各組のハッシュテーブルを削除することを特徴とするデータベースの登録方法を提供する。また、異なる観点から、この発明は、画像に係るデータからそのデータの特徴を表す特徴ベクトルを抽出する処理部と、抽出された特徴ベクトルを前記データと共にデータベースに登録する登録部とを備え、前記データベースは、検索質問として画像に係るデータが与えられたとき、そのデータからクエリベクトルを抽出し、クエリベクトルから最も近いと推測される特徴ベクトルの探索を行う探索装置に用いられ、前記登録部は、各特徴ベクトルを複数のビンの何れか一つに分類して登録するためのハッシュテーブルを、k個を一組の単位としてL組k,Lは2以上の整数生成し、各特徴ベクトルをそれらのハッシュテーブルにそれぞれ登録した後に、i登録されたある特徴ベクトルを選んでその特徴ベクトルと同じビンである登録ビンに分類された他の特徴ベクトルを特定し、ii各組ごとに、その組のk個の登録ビンのいずれにも登録されている他の特徴ベクトルの集合をその組のバケットとし、iii全L個のバケットのうち所定個以上のバケットに入っている特徴ベクトルを得、iv得られた特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録し、所定数の特徴ベクトルについて前記i~ivによる追加登録を実行した後、第1組を除く各組のハッシュテーブルを削除することを特徴とするデータベースの登録装置を提供する。この発明による登録方法は、所定個以上のバケットに入っている特徴ベクトルを第1組のハッシュテーブルの各登録ビンにそれぞれ追加登録した後、第1組を除く各組のハッシュテーブルを削除するので、近似最近傍探索の一手法であるLSHに基づいて、同一精度を実現するために必要な計算時間とメモリ使用量を従来よりも削減できる。即ち、第1組を除くL-1組のハッシュテーブルを格納するメモリを削減でき、かつ、第1組を除くL-1組のハッシュテーブルの探索に要する時間を削減できる。なお、この発明の近似最近傍探索に係る手法は、従来のLSHを用いた近似最近傍探索に代えて適用できるだけでなく、他の手法による近似最近傍探索に代えて適用することができる。この発明の登録装置についても、前記登録方法と同様の作用効果を奏する。このように計算リソースとしての計算時間やメモリ使用量を削減する場合、最近傍探索を用いる識別器で行われているように、データベースに登録されるデータ数の削減を考えるのが一般的と思われる例えば、和田俊和、空間分割を用いた識別と非線形写像の学習1空間分割による最近傍識別の高速化,情報処理,vol46,no8,pp912918,Aug2005参照。この発明によれば、逆にデータベースに登録されているデータを重複登録し、データベースに登録されるデータ数を増加させることによってこれを実現する。この発明の手法は一見逆説的であるが、従来手法であるLSHに対して18の計算時間と90のメモリ使用量で同等の精度を実現できることを実験で確認した。さらに、この要因は、前記非特許文献1に示されているLSHの探索効率の基準ρを用いて説明することができる。この発明において、登録すべきデータからは1つの特徴ベクトルが抽出されてもよいし複数の特徴ベクトルが抽出されてもよい。データから特徴ベクトルを抽出する手法としては、周知のものが適用できる。例えば、後述する実験例では、LBP特徴の抽出手法を用いている。ただし、これに限定されるものでなく、例えば、局所特徴量として周知のSIFTや他の手法を用いることができる。また、この発明において、クエリベクトルは各特徴ベクトルの抽出と同様の手法を用いて抽出する。この発明において、一つのバケットはk個のハッシュテーブルを用いて特定される。そして、クエリベクトルに最も近いと推測される特徴ベクトルを、クエリベクトルに対応する第1組のバケットに登録された各特徴ベクトルの中から決定する。この発明の登録方法によれば、登録に際してk×L個のハッシュテーブルを一時的に生成するが、最終的には第1組に該当するk個のハッシュテーブルに特徴ベクトルの追加登録を行った後、第1組を除く各組のハッシュテーブルを削除する。よって、探索は、第1組のk個のハッシュテーブルを用いる。以下、この発明の好ましい態様について説明する。前記探索は、クエリベクトルにハッシュ関数を適用して、第1組の各ハッシュテーブルについて対応するk個のビンを決定し、それらのビンのいずれにも登録されている特徴ベクトルの集合を求め、前記クエリベクトルをその集合に属する各特徴ベクトルと照合してもよい。このようにすれば、特徴ベクトルの追加登録がなされた第1組のハッシュテーブルのみを用い、削除された第2~第L組のハッシュテーブルを用いないで探索を行うことができる。また、前記登録工程は、追加登録を行うために選択する特徴ベクトルを、一様乱数を用いて決定してもよい。登録時に各バケットに入る特徴ベクトルの分布と複数回の探索時に各バケットに対応するクエリベクトルの分布が同一だと仮定すると、追加登録を行うために選択する特徴ベクトルを一様乱数に基づいて選択すれば特徴ベクトルの分布が密なバケットは多数対応し、粗なバケットはあまり対応しない。よって、多くのクエリベクトルが入力されることが期待されるバケットで追加登録が多く実行されるようにできる。さらにまた、前記登録工程は、追加登録を行おうとする特徴ベクトルが、第1組のバケットに既に登録されているときは、その特徴ベクトルのさらなる追加登録を行わないようにしてもよい。このようにすれば、同一の特徴ベクトルが重複して登録されることがないので、探索の際に重複した距離計算を行って計算時間を無駄に費やすことを回避できる。前記登録工程は、予め定められたkおよびLの値に基づいて処理を行い、登録すべき特徴ベクトルのうち予め定められた割合の数だけ、追加登録を行う特徴ベクトルを選択し、予め定められた個数以上のバケットに入った特徴ベクトルを追加登録するようにしてもよい。これらの値は、実験例においてk,L,β,tで表されており、適当な値を用いることによって真の最近傍点が探索される確率を高められる。よって、経験的にあるいは解析によってそれらの好適な値を予め定めておくことができる。また、前記データベースは、各特徴ベクトルのベクトルデータと各特徴ベクトルの識別子とが対応付けられた対応表および各ハッシュテーブルを含み、各ハッシュテーブルは、各ビンに登録される各特徴ベクトルを対応する識別子を用いて表してもよい。このようにすれば、各ハッシュテーブルにベクトルデータを登録する場合に比べ識別子を登録するだけでよいので、各ハッシュ表のメモリ使用量を削減できる。さらにまた、前記探索は、クエリベクトルと各特徴ベクトルとの距離を計算し、計算された距離に基づいてクエリベクトルから最も近いと推測される特徴ベクトルを決定してもよい。このようにすれば、ベクトルの距離計算によってクエリベクトルから最も近いと推測される特徴ベクトルを決定することができる。ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。≪基礎となる従来のLSHLocalitySensitiveHashingの説明≫この発明の詳細な説明を述べる前に、その基礎となる従来のLSHについてまず説明する。ここでは、ベクトルデータを対象としたpstableLSH前記非特許文献1参照について述べる。LSHによる近似最近傍探索は、次の2ステップで実現される。1クエリとの距離を計算すべきデータ、即ち、距離計算対象を選択する。2前記1の距離計算対象に対してクエリとの距離を計算し、これに基づいて最近傍データを決定する。ここで2に近似処理は含まれていないことに注意しておきたい。つまり、1で求める距離計算対象に真の最近傍データが含まれていれば必ず探索は成功する。以下では、LSHにおいて精度を決定する1の処理、すなわち距離計算対象の絞り込みがどのように実現されているかを説明する。LSHによる距離計算対象の絞り込み最初に次式で与えられるLSHで使用されるハッシュ関数hについて述べる。ここで引数vにはデータpあるいはクエリqを与える。aはデータを射影するd次元ベクトルであり、d次元正規分布に従って定められる。wはハッシュ幅であり、ビンの幅を決めるためのパラメータである。なお、式1は本稿において重要でない項bを省いている。本来のハッシュ関数は次式で与えられる。ここでbjiは区間[0w]から一様乱数により定められた実数である。LSHが式1のハッシュ関数を用いて距離計算対象を絞り込む様子を図示したのが図1である。星はクエリqで、丸はデータpを表す。まず、図1aは、1つのハッシュ関数のみを用いて距離計算対象を決定する様子を示している。結果を先に述べると、図中の灰色地の部分に存在するデータが距離計算対象である。このようにLSHでは式1のハッシュ関数を用いて、クエリと同じハッシュ値インデックスを持つデータのみを距離計算対象とする。その計算には前述のベクトルaが使用される。幾何的な説明をすれば、ベクトルaにデータやクエリを射影して、等間隔に区切られたビンのどれに属すかでハッシュ値が決定される。クエリと同じビンに入ったデータは同じハッシュ値を持つので距離計算対象となる。このことを改めて定義すると、hhを満たす全てのデータpを距離計算対象とするとなる。なお、厳密には、ハッシュ関数を用いてある参照用データキーに対応する値をすばやく参照するため複数のビンにデータを分類し登録するデータ構造をハッシュテーブルと呼び、狭義のハッシュ関数はあるキーに対応するビンを示す値ハッシュ値を与える関数を指す。しかし、この明細書ではデータ構造と関数は一体不可分のものと考えて区別していない。狭義のハッシュ関数を指す場合の他、前記データ構造を示す場合にハッシュ関数あるいはハッシュ関数群の語を用いている。なお、異なるハッシュテーブルは異なる狭義のハッシュ関数を用いてデータを登録する。さて、次は図1bである。注意して図1aを見ると、距離計算対象にはクエリから遠い点も含まれていることがわかる。この状態は距離計算対象を削減するという観点から言えば効率が悪い。そこで、図1bのようにハッシュ関数を複数個k個用いて距離計算対象を更に絞り込む。ここで、これらk個のハッシュ関数から成るハッシュ関数群を次式のように定義する。複数のハッシュ関数は添字で区別する。図1中のベクトルaに添字が付いてajiとなっているのはそのためである。1番目の添え字jはバケットの番号を表す。2番目の添字iはハッシュ関数を表す。このとき、各ハッシュ関数の距離計算対象の積集合をバケットと呼び、クエリのあるバケット図1bの灰色地領域内のデータを距離計算対象とする。ここで改めて図1aと図1bを見てみると、実はどちらの図においても真の最近傍データは距離計算対象に含まれていないことに気付く。そこで真の最近傍データが距離計算対象に含まれる確率を上げるために図1cに示すようにバケットを複数L個用いることにする。そして、各バケットの距離計算対象の和集合を最終的な距離計算対象とする。図1cでは、2つの灰色地領域のいずれかに含まれるデータが距離計算対象になる。ここで、データベースの構造について簡単に触れておく。データベースSは、具体的には複数のハッシュテーブルハッシュ関数を用いたデータ構造の群、即ちハッシュ関数群で構成されている。データベースSにデータを登録する場合、そのデータのID、データから抽出した特徴ベクトルのベクトルデータおよびベクトルIDを対応付けた対応表11をメモリに格納する。ハッシュテーブルのビンには、ベクトルIDを格納する。登録すべきハッシュのビンは、式1を用いて計算する。なお、衝突が起こる場合はリスト構造で連結する。図9は、従来のLSHを適用した物体認識に係るデータベースの構造を示す説明図である。図9の例では、k個のハッシュ関数からなるハッシュ関数群giをL個用いて近似最近傍探索を行う。この場合、各基底のベクトルに対応するL×k個のハッシュテーブルを一時的にメモリ上に確保する。ただし、最終的には、コピー先ハッシュ関数群に該当するk個のハッシュテーブルを残し、他のハッシュテーブルをメモリから削除する。図9を図1と対応させて説明する、図1aのようにハッシュ関数が1つの場合、データベースは1つのハッシュテーブルh11を有する。図1bのようにハッシュ関数が2つの場合、データベースは2つのハッシュテーブルh11、h12からなるハッシュ関数群g1を有する。図1cのようにバケットが2つの場合、データベースは2つのハッシュ関数群g1およびg2を有する。バケット数LとLSHの性能の関係LSHの性能は、ハッシュ関数で使用するwの他に、2つのパラメータ、即ち、ハッシュ関数の数kおよびバケット数Lによって決まる。このうちバケット数Lについて、精度、計算時間、メモリ使用量との関係を考える。i精度:バケット数Lの増加に伴って距離計算対象が単調に増加する。そのため、精度は単調に増加する。ii計算量:バケット数Lの増加に伴い、参照するハッシュテーブル数が単調に増加し、また距離計算対象も単調に増加する。そのため、計算量は単調に増加する。iiiメモリ使用量:LSHではハッシュテーブルを構築する際にメモリを使用する。バケット数Lの増加に伴って必要なハッシュテーブル数が単調に増加するため、メモリ使用量も単調に増加する。局所性に鋭敏なハッシュ関数と探索効率局所性に鋭敏なハッシュ関数の探索効率は、非特許文献1に示されている。後述する分析の基盤とするため、ここで紹介する。式1のハッシュ関数は局所性に鋭敏なハッシュ関数と呼ばれる。局所性に鋭敏なハッシュ関数とは、近いベクトル同士は同じハッシュ値を取る確率が高く、遠いベクトル同士は同じハッシュ値を取る確率が低いという性質を持つハッシュ関数である。数式を用いて具体的に書けば次のようになる。また、図2は以下の記述を図示したものである。ここでBq,rはクエリqから半径r以内にある点の集合を表す。したがって式3は、クエリqから距離r1以内の点は確率p1以上でクエリと同じハッシュ値を持ち、クエリqから距離r2以上の点は確率1-p2以上でクエリと別のハッシュ値を持つ。ここでr1<r2かつp1>p2を満たすとする。局所性に鋭敏なハッシュ関数を用いるLSHの探索効率は、次式で与えられる基準ρを用いて記述される。ρは、最近傍の点がクエリqから距離r1以内にある確率p1が大きければ小さくなり、かつ、最近傍の点がクエリqから距離r2以上にある確率p2が小さければ小さくなる。よって、ρの値は小さいほどよい。非特許文献1によると、必要なメモリ使用量はOで、計算時間のほとんどはO回の距離計算で占められる。ここで、OMあるいはOMρは、問題を解くために必要なおおよその計算量の表記方法であって、例えば、OMはMが定まったときの計算量がα1Mα2以下で収まることを表す。ただし、α1,α2は定数である。また、例えば、OM3はα1M3α2M2α3Mα4以下で収まることを表す。ただしα1,α2,α3,α4は定数である。また、dはベクトルデータの次元数であり、nは扱うベクトルデータの数である。このとき、O回のハッシュ関数の評価が必要である。≪この発明に係る最近傍探索の手法≫この発明は、近似最近傍探索の手法において、データベースにデータを重複登録することで計算時間とメモリ使用量を削減する手法を提案する。図3にこの発明の手法の概要を示す。まず、図3aでは大き目のバケット数Lを持つLSHを構築する。そして図3bのように、1つのバケットコピー先バケットに残りのバケットコピー元バケットの情報をコピーし、図3cのようにコピー元バケットを削除する。これにより、バケット数が大きいときの性能を少数のバケットのみで実現できる。以下、この発明の手法の処理の詳細を、図4を参照しながら述べる。最初に前節のコピー元バケットとコピー先バケットの代わりに、コピー元ハッシュ関数群とコピー先ハッシュ関数群を作成する。どちらのLSHにも同じデータが登録されているが、ハッシュ関数やバケットが異なる。そして、手順1:コピー先ハッシュ関数群に登録されているデータを1つ選ぶ。説明の都合上、このデータをYと呼ぶ。次に手順2:Yをクエリに見立ててコピー元ハッシュ関数群で探索し、手順3:コピー元ハッシュ関数群でYと同じバケットに入った各データについて、同じバケットに入った回数を数える。その後、手順4:同じバケットに入った回数が閾値t以上のデータのみを選択して、コピー先ハッシュ関数群のYが属していたバケットに追加登録する。ただし、既に登録済みの場合は追加登録の対象とはしない。この処理を、Yとするデータを変えながら一定数のデータに対して行う。全データのうち、この処理に用いるデータの割合をβで表す0≦β≦1。最後にコピー元ハッシュ関数群を破棄し、コピー先ハッシュ関数群を通常のLSHの代わりに用いる。即ち、コピー先ハッシュ関数群のハッシュテーブルのみを残し、コピー元ハッシュ関数群のハッシュテーブルのあったメモリ領域を開放してデータベースを構築する。なお、LSHにはバケットに登録するという概念はなく、データベース内の各ハッシュテーブルのビンに登録された距離計算対象の積集合を求めることによりバケットが決まる。よって、データのバケットへの追加登録は、具体的には当該バケットを構成する全てのハッシュ関数にデータを登録する。データの追加登録は、クエリとしての物体の画像が与えられたときその画像に対応するクエリベクトルが多く発生するバケットで実行するのが効果的である。データの分布とクエリの分布が同一だと仮定すると、Yとするデータを一様乱数に基づいて選択すればデータの分布が密なバケットは多数選ばれ、粗なバケットはあまり選ばれないため、前述のようにクエリが多く発生するバケットでデータの追加登録が多く実行される。そのため、本稿ではデータの分布とクエリの分布が同一だと仮定し、Yとするデータを一様乱数に基づいて選択する。なお、この実施形態では、データの重複登録によってメモリ使用量が大幅に増加しないように実装した。具体的には、距離計算に用いるベクトルデータを保持しておくテーブルをハッシュテーブルとは別に用意して、各ハッシュ値を持つデータの番号のみをハッシュテーブルに保持した。これにより、重複登録によって増加するメモリ使用量はデータの番号を表す分のみとなる。≪実験例≫従来のLSHとこの発明による近似最近傍探索手法の結果を比較し、この発明の有効性を確かめる実験を行った。実験にはMultiPIEFacedatabaseRGrossIMatthewsJCohnTKanadeandSBakerMultipieProc8thIEEEIntlConfonAutomaticFaceandGestureRecognition2008参照に含まれる754200枚の画像に顔検出TMitaTKanekoBStengerandOHoriDiscriminativefeaturecooccurrenceselectionforobjectdetectionIEEETransPAMIpp12571269July2008参照を適用し、得られた316089枚の画像に正規化TKozakayaandOYamaguchiFacerecognitionbyprojectionbased3dnormalizationandshadingsubspaceorthogonalizationProc7thIntConfonAutomaticFaceandGestureRecognitionpp1631682006参照を施して、928次元のLBP特徴TAhonenAHadidandMPietikainenFacedescriptionwithlocalbinarypatternsApplicationtofacerecognitionIEEETransPAMIvol28no12pp20372041Dec2006参照を抽出し、さらに主成分分析によって100次元に圧縮した。これらの特徴ベクトルからランダムに10000をデータベース登録用に選び、別の10000をクエリ用に選んだ。事前に全探索で最近傍データを求めておき、それぞれの近似最近傍探索手法で求めた近似最近傍データが一致した割合を精度とした。計算機はOpteron6174を用いた。追加登録に用いるデータ数に関するパラメータβの値として0001,001,01を用いた。これらはそれぞれ追加登録に10個、100個、1000個のデータを用いることを意味する。図5に精度と処理時間の関係を、図6に精度とメモリ使用量の関係を表したグラフを示す。図5および図6に係る実験で、距離計算対象を絞り込むために用いるハッシュ関数の数に係るパラメータはk1=k2=1、ハッシュ幅に係るパラメータはw1=w2=1000で、各グラフともに共通である。また、表1に精度、計算時間、メモリ使用量の比較結果を抜粋する。表1に係る実験は、パラメータとして、k1=k2=1,w1=w2=1000を用いた。コピー先ハッシュ関数群のパラメータはw1,k1,L1のように添字1をつけて表し、コピー元ハッシュ関数群のパラメータはw2,k2,L2のように添字2をつけて表している。表1のパラメータtは、クエリに見立てたデータYと同じバケットに入った回数が何回以上のものを登録するかの閾値である。図5および図6から、この発明の手法は従来手法であるLSHと比べて、同一の処理時間のときやメモリ使用量のときの精度が著しく向上していることがわかる。そのため、同等の精度で比べると、処理時間もメモリ使用量も減少している事が分かる。表1から、β01L220t1のときに精度999、計算時間069ms、メモリ使用量164MBを達成している。LSHにおいてL20のときは精度999、計算時間391ms、メモリ使用量183MBであるので、これらを比べると、計算時間が18に、メモリ使用量は90に削減されたことがわかる。これは、LSHと同等の精度を達成するのに必要なハッシュ関数群の数Lが小さくてすむ事に起因していると考えられる。L2とtを変化させたときの性能を比べると、L2が大きいときのほうが性能がよく、tが大きいときは性能が悪かった。≪分析≫この発明の手法によるρの変化前節でこの発明の手法の実験的な有効性を確認した。本節では、前述したLSHの探索効率の基準ρ式4参照がこの発明の手法ではLSHに比べて小さくなることを示し、解析的にこの発明の手法の有効性を示す。LSHは局所性に鋭敏なハッシュ関数を用いるので、図4の手順2のように注目データの近傍点をコピー元ハッシュ関数群で探索すると、注目データに近い点ほど高い確率で探索され、遠い点ほど低い確率で探索される。そのため、コピー先ハッシュ関数群ではクエリと同じビンに属するデータが増加する。すなわち、クエリqから距離r1以内の点がクエリと同じハッシュ値を持つ確率p1と、クエリqから距離r2以上の点がクエリと同じハッシュ値を持つ確率p2は共に増大する。ただし、注目データに近い領域ではより多くのデータが探索されるため、p1はp2より大きくなる。この結果、ρが減少する。コピー元ハッシュ関数群のバケット数L2と閾値tの関係図4の手順3では探索回数が閾値t以上のデータのみをデータベースに追加登録する。このときに用いる閾値を上手に調整できれば、近傍点として選ばれる確率が高い点を選択的に追加し、ρの減少をさらに促すことができる。本節ではどのような閾値が望ましいのかを考察する。ここではコピー元ハッシュ関数群のL2個のバケットを探索して、あるデータYがy回みつかったと仮定する。この事象が起こる確率Pyは次式の二項分布で与えられる。ここでである。確率pは注目データからデータYまでの距離の関数であり、両者の距離が近いほど大きくなる。図7は式5をプロットしたもので、縦軸は、コピー元ハッシュ関数群でy回探索される確率Pyを表している。この式に値を入れて計算してみると、大きな確率pを持つYに近い点例えばp05と小さな確率pを持つYから遠い点p03では分布が異なり、近い点のほうが探索される回数yが多いことがわかる。また、データベースに追加登録をするか否かを決める探索回数の閾値tとデータが選択される確率の関係について考えてみると、閾値tをt1としたときよりも、p05のときの期待値05L2としたときすなわち、図7aに示すL210の場合はt5,図7bに示すL220のときはt10のほうがYから近い点と遠い点の確率差は大きいことから、適切に閾値を設定することが必要であること、そしてその値は最近傍点が探索される確率を基準に定められる可能性があることがわかる。次に、コピー元ハッシュ関数群のバケット数L2がこの発明の手法の性能に及ぼす影響を考える。閾値tを先程と同様にp05のときの期待値05L2としたとき、図8aよりも図8bのほうがYから近い点と遠い点の確率差は大きい。したがって、コピー元ハッシュ関数群のバケット数L2を大きくすれば、性能が向上する場合があると考えられる。これは実験結果とよく一致する。前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。"