"特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、前記クエリコンテンツについて、クエリ特徴ベクトル毎に、1つ以上のハッシュ関数を用いて、1つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、前記クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、前記クエリハッシュ識別値に対応する全ての前記リファレンスコンテンツ識別値を、前記距離が短い昇順にソートする距離ソート手段と、ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、抽出された前記リファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段とを有することを特徴とする検索装置。前記リファレンス情報蓄積手段は、前記リファレンス特徴ベクトルに代えて、当該リファレンス特徴ベクトルに対するリファレンス符号を蓄積しており、前記ハッシュ化手段は、多数の前記リファレンス特徴ベクトル毎に、1つ以上のハッシュ関数を用いて、1つ以上の一意のリファレンスハッシュ識別値を更に導出し、前記リファレンス特徴ベクトルを、リファレンス符号に符号化し、前記リファレンス情報蓄積手段へ蓄積する符号化手段を更に有し、前記距離算出手段は、前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス符号と、前記クエリ特徴ベクトルとの間の距離を算出することを特徴とする請求項1に記載の検索装置。前記類似検索手段は、前記クエリコンテンツに含まれる複数のクエリ特徴ベクトル毎に導出された複数のリファレンスコンテンツ識別値を、当該リファレンスコンテンツ識別値毎に投票し、その投票数に応じたリファレンスコンテンツ識別値を抽出することを特徴とする請求項1又は2に記載の検索装置。前記リファレンス情報蓄積手段は、前記リファレンスコンテンツ毎に、前記リファレンスハッシュ識別値の頻度のLpノルムを蓄積し、前記類似検索手段は、前記リファレンスコンテンツ毎の得票数を、対応するリファレンスコンテンツのLpノルムで正規化した値を、類似度として算出することを特徴とする請求項3に記載の検索装置。前記符号化手段は、前記リファレンス特徴ベクトル及び前記クエリ特徴ベクトルに対して射影変換を行い、変換後の各次元の値を閾値で二値化することによって、バイナリ列のリファレンス符号及びクエリ符号を生成し、前記距離算出手段は、前記リファレンス符号及びクエリ符号のハミング距離を算出することを特徴とする請求項4に記載の検索装置。前記符号化手段は、前記ハッシュ識別値に対応する代表ベクトルを蓄積しており、前記リファレンス特徴ベクトルと、当該リファレンス特徴ベクトルのリファレンスハッシュ識別値に対応する代表ベクトルとの間のリファレンス差分ベクトルを算出し、そのリファレンス差分ベクトルをリファレンス符号に符号化することを特徴とする請求項4に記載の検索装置。前記代表ベクトルは、当該ハッシュ識別値を持つ多数の特徴ベクトルの平均ベクトル又は中央値ベクトルから算出されることを特徴とする請求項6に記載の検索装置。前記符号化手段は、直積量子化のためのコードブックを更に有し、前記リファレンス差分ベクトルを、前記コードブックを用いて直積量子化によってリファレンス符号に符号化し、前記クエリ特徴ベクトルと、前記クエリハッシュ識別値に対応する代表ベクトルとの間のクエリ差分ベクトルを算出するものであり、前記距離算出手段は、前記リファレンス符号とクエリ差分ベクトルとのLp距離を算出することを特徴とする請求項7に記載の検索装置。前記ハッシュ化手段は、ベクトル量子化用のコードブックを更に有し、前記ハッシュ関数はベクトル量子化を行うことでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出することを特徴とする請求項5又は8に記載の検索装置。前記ハッシュ化手段は、前記リファレンス特徴ベクトル及びクエリ特徴ベクトルと、同次元の既定のベクトルとの内積の値を、所定閾値で離散化することでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出することを特徴とする請求項5又は8に記載の検索装置。前記ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであることを特徴とする請求項9又は10に記載の検索装置。特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索するように、コンピュータを機能させるプログラムであって、リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、前記クエリコンテンツについて、クエリ特徴ベクトル毎に、1つ以上のハッシュ関数を用いて、1つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、前記リファレンス情報蓄積手段を用いて、前記クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、前記クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、前記クエリハッシュ識別値に対応する全ての前記リファレンスコンテンツ識別値を、前記距離が短い昇順にソートする距離ソート手段と、ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、抽出された前記リファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段としてコンピュータを機能させることを特徴とする検索プログラム。しかしながら、前述した非特許文献2及び3に記載された技術によれば、全ての量子化IDについて、同一の所定閾値によって類似度に貢献するか否かを判定しているために、量子化ID毎の特徴ベクトルの密度については全く考慮されていない。このため、ある量子化IDでは、過剰に特徴ベクトルが類似度に貢献し、一方で、別の量子化IDでは、類似度に貢献する特徴ベクトルが少なくなるといった問題が生じる。そこで、本発明によれば、高次元の特徴ベクトルを検索する際に、量子化ID毎の特徴ベクトルの密度を考慮することによって、量子化ID同士の間の類似度の決定における不公平性を緩和することができる検索装置及びプログラムを提供することを目的とする。本発明によれば、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索する検索装置であって、リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、クエリコンテンツについて、クエリ特徴ベクトル毎に、1つ以上のハッシュ関数を用いて、1つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、リファレンス情報蓄積手段を用いて、クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、クエリハッシュ識別値に対応する全てのリファレンスコンテンツ識別値を、距離が短い昇順にソートする距離ソート手段と、ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、抽出されたリファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段とを有することを特徴とする。本発明の検索装置における他の実施形態によれば、リファレンス情報蓄積手段は、リファレンス特徴ベクトルに代えて、当該リファレンス特徴ベクトルに対するリファレンス符号を蓄積しており、ハッシュ化手段は、多数のリファレンス特徴ベクトル毎に、1つ以上のハッシュ関数を用いて、1つ以上の一意のリファレンスハッシュ識別値を更に導出し、リファレンス特徴ベクトルを、リファレンス符号に符号化し、リファレンス情報蓄積手段へ蓄積する符号化手段を更に有し、距離算出手段は、リファレンス情報蓄積手段を用いて、クエリハッシュ識別値に対応する各リファレンス符号と、クエリ特徴ベクトルとの間の距離を算出することも好ましい。本発明の検索装置における他の実施形態によれば、類似検索手段は、クエリコンテンツに含まれる複数のクエリ特徴ベクトル毎に導出された複数のリファレンスコンテンツ識別値を、当該リファレンスコンテンツ識別値毎に投票し、その投票数に応じたリファレンスコンテンツ識別値を抽出することも好ましい。本発明の検索装置における他の実施形態によれば、リファレンス情報蓄積手段は、リファレンスコンテンツ毎に、リファレンスハッシュ識別値の頻度のLpノルムを蓄積し、類似検索手段は、リファレンスコンテンツ毎の得票数を、対応するリファレンスコンテンツのLpノルムで正規化した値を、類似度として算出することも好ましい。本発明の検索装置における他の実施形態によれば、符号化手段は、リファレンス特徴ベクトル及びクエリ特徴ベクトルに対して射影変換を行い、変換後の各次元の値を閾値で二値化することによって、バイナリ列のリファレンス符号及びクエリ符号を生成し、距離算出手段は、リファレンス符号及びクエリ符号のハミング距離を算出することも好ましい。本発明の検索装置における他の実施形態によれば、符号化手段は、ハッシュ識別値に対応する代表ベクトルを蓄積しており、リファレンス特徴ベクトルと、当該リファレンス特徴ベクトルのリファレンスハッシュ識別値に対応する代表ベクトルとの間のリファレンス差分ベクトルを算出し、そのリファレンス差分ベクトルをリファレンス符号に符号化することも好ましい。本発明の検索装置における他の実施形態によれば、代表ベクトルは、当該ハッシュ識別値を持つ多数の特徴ベクトルの平均ベクトル又は中央値ベクトルから算出されることも好ましい。本発明の検索装置における他の実施形態によれば、符号化手段は、直積量子化のためのコードブックを更に有し、リファレンス差分ベクトルを、コードブックを用いて直積量子化によってリファレンス符号に符号化し、クエリ特徴ベクトルと、クエリハッシュ識別値に対応する代表ベクトルとの間のクエリ差分ベクトルを算出するものであり、距離算出手段は、リファレンス符号とクエリ差分ベクトルとのLp距離を算出することも好ましい。本発明の検索装置における他の実施形態によれば、ハッシュ化手段は、ベクトル量子化用のコードブックを更に有し、ハッシュ関数はベクトル量子化を行うことでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出することも好ましい。本発明の検索装置における他の実施形態によれば、ハッシュ化手段は、リファレンス特徴ベクトル及びクエリ特徴ベクトルと、同次元の既定のベクトルとの内積の値を、所定閾値で離散化することでリファレンスハッシュ識別値及びクエリハッシュ識別値を算出することも好ましい。本発明の検索装置における他の実施形態によれば、ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルであることも好ましい。本発明によれば、特徴ベクトルの集合で表されるリファレンスコンテンツの集合から、特徴ベクトルの集合で表されるクエリコンテンツに類似したリファレンスコンテンツを検索するように、コンピュータを機能させるプログラムであって、リファレンスハッシュ識別値毎に、リファレンスコンテンツ識別値と、リファレンス特徴ベクトルとの組み合わせを、複数蓄積したリファレンス情報蓄積手段と、クエリコンテンツについて、クエリ特徴ベクトル毎に、1つ以上のハッシュ関数を用いて、1つ以上の一意のクエリハッシュ識別値を導出するハッシュ化手段と、リファレンス情報蓄積手段を用いて、クエリハッシュ識別値に対応する各リファレンス特徴ベクトルと、クエリ特徴ベクトルとの間の距離を算出する距離算出手段と、クエリハッシュ識別値に対応する全てのリファレンスコンテンツ識別値を、距離が短い昇順にソートする距離ソート手段と、ソートされたリファレンスコンテンツ識別値の中で、上位閾値割合に含まれるリファレンスコンテンツ識別値のみを抽出するリファレンスコンテンツ識別値抽出手段と、抽出されたリファレンスコンテンツ識別値に対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する類似検索手段としてコンピュータを機能させることを特徴とする。本発明の検索装置及びプログラムによれば、高次元の特徴ベクトルを検索する際に、量子化ID毎の特徴ベクトルの密度を考慮することによって、量子化ID同士の間の類似度の決定における不公平性を緩和することができる。以下では、本発明の実施の形態について、図面を用いて詳細に説明する。本発明の検索装置及びプログラムによれば、多数のリファレンスコンテンツ検索対象のコンテンツの中から、クエリコンテンツ検索キーのコンテンツに最も類似するリファレンスコンテンツを検索する。検索のために、マルチメディアコンテンツから、特徴ベクトルの集合を抽出する。即ち、特徴ベクトルの集合の1つが、1つのマルチメディアコンテンツに対応する。具体的には、リファレンスコンテンツは、複数のリファレンス特徴ベクトルの集合からなり、同様に、クエリコンテンツも、複数のクエリ特徴ベクトルの集合からなる。リファレンス特徴ベクトル及びクエリ特徴ベクトルは、同じ次元数のベクトルである。尚、マルチメディアコンテンツが画像である場合、その特徴ベクトルは、画像の局所特徴領域から抽出された局所特徴ベクトルである。図1は、リファレンス特徴ベクトルの集合に対するクラスタリングを表す説明図である。図1aによれば、多数のリファレンス特徴ベクトルが、例えばN個のクラスタFnn=1~Nにクラスタリングされている。クラスタリングには、例えばkmeans又はkmeansのようなアルゴリズムが用いられる。各クラスタ内には、多数のリファレンス特徴ベクトルが含まれている。クラスタ内にクエリ特徴ベクトルが含まれる場合、そのクエリ特徴ベクトルから所定閾値の距離範囲に属するリファレンス特徴ベクトルが、候補として導出される。図1によれば、以下のように表される。×:リファレンス特徴ベクトル:クラスタにおける代表ベクトル平均ベクトル又は中央値ベクトル黒丸●:クエリ特徴ベクトル波線○:クエリ特徴ベクトルから所定閾値の距離範囲例えば、クラスタF1にクエリ特徴ベクトルaが含まれ、クラスタF3にクエリ特徴ベクトルbが含まれるとする。従来技術によれば、クエリ特徴ベクトルから、所定閾値の距離範囲に属するリファレンス特徴ベクトルの数によって類似度を算出している。しかしながら、クラスタのセル範囲によっては、以下のように分かれる。クラスタのセル範囲が小さい場合、特徴ベクトルの分布密度が高い。この場合、クエリ特徴ベクトルから、所定閾値範囲に属するリファレンス特徴ベクトルの数も多く、類似度が高いと判定される。クラスタのセル範囲が大きい場合、特徴ベクトルの分布密度が低い。この場合、クエリ特徴ベクトルから、所定閾値範囲に属するリファレンス特徴ベクトルの数も少なく、類似度も低いと判定される。これに対し、図1bに基づく本発明によれば、クラスタ内のリファレンス特徴ベクトルの中で、上位閾値割合Pに含まれるリファレンス特徴ベクトルのみを抽出する。抽出されたリファレンス特徴ベクトルについてのみ、クエリ特徴ベクトルから所定閾値範囲に属する数が多いほど、類似度が高いと判定される。即ち、本発明によれば、クラスタのセル範囲リファレンス特徴ベクトルの分布に応じて、判定対象となるリファレンス特徴ベクトルが異なる。以下では、クエリコンテンツ及びリファレンスコンテンツについて、類似検索のための比較対象が異なる2通りの実施形態について説明する。[第1の実施形態]クエリコンテンツのクエリ特徴ベクトルと、リファレンスコンテンツのリファレンス特徴ベクトルとを比較して、類似度を判定する。[第2の実施形態]クエリコンテンツのクエリ特徴ベクトルにおけるクエリ符号又はクエリ差分ベクトルと、リファレンスコンテンツのリファレンス特徴ベクトルにおけるリファレンス符号とを比較して、類似度を判定する。[第1の実施形態]図2は、本発明における検索装置の第1の機能構成図である。図3は、本発明におけるデータ構造を表す第1の説明図である。図2によれば、検索装置1は、リファレンス情報蓄積部100と、特徴ベクトル集合抽出部111と、ハッシュ化部112と、距離算出部113と、距離ソート部114と、リファレンスコンテンツID抽出部115と、類似検索部116とを有する。これら機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。検索装置1は、多数のリファレンスコンテンツを予め入力し、リファレンス情報蓄積部100に、リファレンスコンテンツに関する情報を記憶する。また、検索装置1は、検索の際に、検索キーとなるクエリコンテンツを入力し、リファレンス情報蓄積部100を用いて、クエリコンテンツに最も類似するリファレンスコンテンツを検索する。特徴ベクトル集合抽出部111は、マルチメディアコンテンツから、特徴ベクトルの集合を抽出する。ここでは、リファレンスコンテンツから、複数のリファレンス特徴ベクトルの集合が抽出され、同様に、クエリコンテンツから、複数のクエリ特徴ベクトルの集合が抽出される図3の111参照。例えば、SIFTアルゴリズムによれば、1枚の画像からは、128次元D=128の特徴ベクトルの集合が抽出される例えば非特許文献4参照。SIFTとは、スケールスペースを用いて特徴的な局所領域を解析し、そのスケール変化及び回転に不変となる特徴ベクトルを記述する技術である。特徴ベクトルf:f=f1,f2,,fD抽出されたリファレンス特徴ベクトルは、ハッシュ化部112及びリファレンス情報蓄積部100へ出力される。また、抽出されたクエリ特徴ベクトルは、ハッシュ化部112及び距離算出部113へ出力される。ハッシュ化部112は、リファレンスコンテンツについて、リファレンス特徴ベクトル毎に、1つ以上のハッシュ関数を用いて、1つ以上の一意のリファレンスハッシュID識別値を導出する。同様に、クエリコンテンツについても、クエリ特徴ベクトル毎に、1つ以上のハッシュ関数を用いて、1つ以上の一意のクエリハッシュIDを導出する図3の112参照。図4は、ハッシュ化部の機能構成を表す説明図である。ハッシュ化部112は、以下の2つの処理のいずれか一方を用いる。尚、リファレンス特徴ベクトル及びクエリ特徴ベクトルには、同じハッシュ化処理が実行される。第1のハッシュ処理ハッシュ化部112は、ベクトル量子化用のコードブックを有し、特徴ベクトルに対してベクトル量子化を実行する。これによって、リファレンスハッシュID及びクエリハッシュIDを算出する。ここで、コードブックとは、特徴ベクトルfを量子化するために、ハッシュIDn=1~Nと、代表ベクトルfnとを対応付けたものである。ハッシュIDn:代表ベクトルfn1:f1=f11,f12,,f1D2:f2=f21,f22,,f2D3:f3=f31,f32,,f3DN:fN=fN1,fN2,,fNDコードブックは、以下のステップを実行することによって生成される例えば図1参照。S1リファレンス特徴ベクトルの集合を、N個のクラスタにクラスタリングする。S2次に、クラスタ毎に、代表ベクトルを導出する平均ベクトル又は中央値ベクトル。S3各代表ベクトルに、一意のハッシュIDn=1~Nを割り当てたコードブックを生成する。第1のハッシュ処理によれば、入力された特徴ベクトルfとの距離が最も小さくなる代表ベクトルfnを算出し、特徴ベクトルfに、識別値IDnを割り当てる。n=qf=argminnf-fn2登録ベクトルfの量子化関数qfは、f-fn2が最小となるnを導出q:RDN量子化を意味するfn:代表ベクトルこのとき、特徴ベクトルに対して、最も距離が小さくなる1つのIDnを割り当てるのではなく、距離が小さくなる代表ベクトルにおける上位いくつかの複数のIDを割り当ててもよい。また、異なるコードブックを複数保持しておき、それぞれのコードブックで個別にIDを割り当ててもよい。これらの処理によって、D次元の特徴ベクトルの集合f1~fKそれぞれに、1つ以上のハッシュIDが割り当てられる。第2のハッシュ処理ハッシュ化部112は、リファレンス特徴ベクトル及びクエリ特徴ベクトルと、同次元の既定のベクトルとの内積の値を、所定閾値で離散化することによって、リファレンスハッシュID及びクエリハッシュIDを算出する。尚、ハッシュ化部112では、近似最近傍探索アルゴリズムの1つであるLSHで用いられるハッシュ関数を用いることもできる。LSHによれば、類似するデータ同士のハッシュIDは一致し、非類似のデータ同士のハッシュIDは異なる可能性が高くなるように、ハッシュIDを出力する。リファレンス特徴ベクトルをハッシュ化したリファレンスハッシュIDは、リファレンス情報蓄積部100へ出力される。また、クエリ特徴ベクトルをハッシュ化したクエリハッシュIDは、距離算出部113へ出力される。リファレンス情報蓄積部100は、リファレンスハッシュID毎に、リファレンスコンテンツIDと、リファレンス特徴ベクトルとの組み合わせを、複数蓄積する図3の100参照。即ち、リファレンスハッシュID毎に、リファレンスコンテンツID及びリファレンス特徴ベクトルがリスト化される。再び図2へ戻って、距離算出部113は、リファレンス情報蓄積部100がリファレンス特徴ベクトルを蓄積している場合、クエリ特徴ベクトルにおけるクエリハッシュIDikに対応するリファレンス特徴ベクトルのリストを参照する。そして、各リファレンス特徴ベクトルと、クエリ特徴ベクトルとの間の距離を算出する図3の113参照。算出された距離の情報は、距離ソート部114へ出力される。距離ソート部114は、クエリハッシュIDに対応する全てのリファレンスコンテンツIDを、距離が短い昇順にソートする。リファレンスコンテンツID及び距離のペア毎に、ソートされる。リファレンスコンテンツID抽出部115は、ソートされたリファレンスコンテンツID全体の中で、上位閾値割合Pに含まれるリファレンスコンテンツID群のみを抽出する図3の114参照。類似検索部116は、クエリコンテンツクエリ特徴ベクトルの集合とリファレンスコンテンツリファレンス特徴ベクトルの集合との間の類似度を判定する。リファレンスコンテンツID抽出部115によって抽出されたリファレンスコンテンツIDに対応するリファレンス特徴ベクトルを含む複数のリファレンスコンテンツの中から、最も類似するリファレンスコンテンツを検索する。ここで、類似検索部116は、クエリコンテンツに含まれる複数のクエリ特徴ベクトル毎に導出された複数のリファレンスコンテンツIDを、当該リファレンスコンテンツID毎に投票し、その投票数に応じたリファレンスコンテンツIDを抽出する。図5は、リファレンスコンテンツIDの投票を表すグラフである。最初に、リファレンスコンテンツID抽出部115によって抽出されたリファレンスコンテンツID群について、クエリ特徴ベクトルのクエリハッシュID毎に、各リファレンスコンテンツIDの個数をカウントする図5a参照。例えば、1つのクエリコンテンツについて、クリエ特徴ベクトル毎にクエリハッシュID1~3が導出されたとする。そのクエリハッシュID毎に、リファレンスコンテンツIDが抽出される。クリエハッシュIDリファレンスコンテンツID15,621,4,531,5ここで、リファレンスコンテンツIDの出現頻度は、以下のように表される。リファレンスコンテンツID出現頻度1220304153投票数の局所最大61次に、リファレンスコンテンツID毎の総個数を、正規化項で正規化する。ここで、正規化項は、以下のように算出される。リファレンス情報蓄積部100は、ハッシュIDがID1~4をとる場合、リファレンスコンテンツ毎に、各ハッシュIDの出現頻度を蓄積する図5b参照。例えば、リファレンスコンテンツID1における、リファレンスハッシュIDの出現頻度は、以下のようになる。[リファレンスコンテンツID1の場合]リファレンスハッシュID出現頻度11233041そして、リファレンスハッシュID毎の出現頻度に応じて、以下のように2種類の正規化項を算出する。以下では、リファレンスハッシュID1についてのみ記述する。リファレンスハッシュID1のL1ノルム1301=5リファレンスハッシュID1のL2ノルムの場合√=√=√11最終的に、クエリコンテンツに対するリファレンスコンテンツの類似度は、以下のように表される図5c参照。リファレンスコンテンツIDL1ノルム類似度L2ノルム類似度12/52/√1120/90/√930/110/√1141/81/√853/93/√961/81/√8このように、類似検索部116は、リファレンスコンテンツ毎の得票数を、対応するリファレンスコンテンツのLpノルムで正規化した値を、類似度として算出する。そして、類似度が最も高いリファレンスコンテンツIDを、検索結果として出力する。[第2の実施形態]図6は、本発明における検索装置の第2の機能構成図である。図7は、本発明におけるデータ構造を表す第2の説明図である。前述した第1の実施形態によれば、リファレンス情報蓄積部100は、リファレンスハッシュID毎に、リファレンスコンテンツIDと、リファレンス特徴ベクトルとの組み合わせを、複数蓄積する。これに対し、第2の実施形態によれば、リファレンス情報蓄積部100は、リファレンスハッシュID毎に、リファレンスコンテンツIDと、当該リファレンス特徴ベクトルに対するリファレンス符号との組み合わせを、複数蓄積する。第2の蓄積情報は、第1の蓄積情報のリファレンス特徴ベクトルに代えて、リファレンス符号を蓄積する。図6によれば、図2と比較して、リファレンス特徴ベクトル及びクエリ特徴ベクトルを、リファレンス符号及びクエリ符号若しくはクエリ差分ベクトルに符号化する符号化部117を更に有する。図7によれば、リファレンス情報蓄積部100は、リファレンスコンテンツID毎に、リファレンス符号を記憶する図7の100参照。また、距離算出部113は、リファレンス符号と、クエリ符号又はクエリ差分ベクトルとの間の距離を算出する図7の113参照。それらの点以外は、前述した図3と全く同様である。図8は、本発明における符号化部の機能構成図である。符号化部117は、大きく2通りの符号化処理の中で、いずれか一方の処理が実行される。尚、リファレンス特徴ベクトル及びクエリ特徴ベクトルには、同じ符号化処理が実行される。第1の符号化処理符号化部117は、特徴ベクトル集合抽出部111から出力されたリファレンス特徴ベクトル及びクエリ特徴ベクトルを入力する。次に、各特徴ベクトルfkについて、割り当てられたハッシュIDikに対応する代表ベクトルgikからの差分ベクトルrkを算出するrk=fk-gik。そして、差分ベクトルrkに対してランダムな直交射影によって射影変換を実行する。次に、変換後の各次元の値を、閾値で二値化することによって、バイナリ列のリファレンス符号及びクエリ符号を生成する。尚、直積量子化の場合には、差分ベクトルrkを複数の部分ベクトルに分割し、それぞれを個別のコードブックで量子化し、量子化IDの列を符号ckとする。リファレンス符号は、リファレンス情報蓄積部100へ出力され、クエリ符号は、距離算出部113へ出力される。このような符号化処理に対して、距離算出部113は、リファレンス符号及びクエリ符号のハミング距離を算出する例えば非特許文献2参照。第2の符号化処理符号化部117は、ハッシュIDに対応する代表ベクトルを蓄積する。代表ベクトルとは、当該ハッシュIDを持つ多数の特徴ベクトルの平均ベクトル又は中央値ベクトルから算出されるものであってもよい。そして、符号化部117は、リファレンス特徴ベクトルと、当該リファレンス特徴ベクトルのリファレンスハッシュIDに対応する代表ベクトルとの間のリファレンス差分ベクトルを算出し、そのリファレンス差分ベクトルをリファレンス符号に符号化する。符号化部117は、直積量子化のためのコードブックを更に有する。そして、リファレンス差分ベクトルを、コードブックを用いて直積量子化によってリファレンス符号に符号化する例えば非特許文献3参照。また、符号化部117は、クエリ特徴ベクトルと、クエリハッシュIDに対応する代表ベクトルとの間のクエリ差分ベクトルを算出する。リファレンス符号は、リファレンス情報蓄積部100へ出力され、クエリ差分ベクトルは、距離算出部113へ出力される。このような符号化処理に対して、距離算出部113は、リファレンス符号とクエリ差分ベクトルとのLp距離を算出する例えば非特許文献4及び5参照。第1の符号化処理及び第2の符号化処理の両方とも、予め大量のリファレンス特徴ベクトルから、ハッシュ化部112によって各ハッシュIDが割り当てられるリファレンス特徴ベクトルの平均ベクトルを算出しておく。本発明の検索装置及びプログラムによれば、高次元の特徴ベクトルを検索する際に、量子化ID毎の特徴ベクトルの密度を考慮することによって、量子化ID同士の間の類似度の決定における不公平性を緩和することができる。前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。"