検索対象である登録データと、当該登録データの誤差を示す誤差情報とを対応付けて記憶する記憶部と、検索要求に係るクエリデータと前記登録データとの距離から前記誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データを前記記憶部から検索する検索部と、を有することを特徴とする情報処理装置。前記記憶部は、さらに、予め定められた参照ポイントと各登録データとの距離を記憶し前記検索部は、前記記憶部が記憶した参照ポイントと各登録データとの距離を用いて、前記参照ポイントからの距離が、前記クエリデータと前記参照ポイントとの距離から前記近傍範囲に応じた距離と前記誤差情報の最大値とを減じた値よりも大きく、前記クエリデータと前記参照ポイントとの距離から前記近傍範囲に応じた距離と前記誤差情報の最大値とを加算した値よりも小さい登録データを検索するインデックス検索部と、前記インデックス検索部によって検索された登録データのうち、前記クエリデータとの距離から前記誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部と、を有することを特徴とする請求項1に記載の情報処理装置。前記記憶部は、前記登録データを登録する際に入力される複数個のデータから得られる特徴量の平均、又は、前記複数個のデータから得られる特徴量の分散、又は、前記登録データを取得する装置の精度、又は、前記登録データを取得する装置の設置状況から推定される生体データの質のいずれかを用いて算出される前記誤差情報を記憶することを特徴とする請求項1または2に記載の情報処理装置。検索対象である登録データともに、予め定められた参照ポイントと各登録データとの距離と、前記参照ポイントと各登録データとの内積値を記憶する記憶部と、前記記憶部が記憶した参照ポイントと各登録データとの距離を用いて、前記参照ポイントからの距離が、検索要求に係るクエリデータと前記参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと前記参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索する近傍候補検索部と、前記近傍候補検索部によって検索された登録データのうち、前記クエリデータと前記参照ポイントとの距離と、前記登録データと前記参照ポイントとの距離との差が所定の近傍範囲内にある登録データを抽出する第1枝刈部と、前記第1枝刈部によって抽出された登録データのうち、前記記憶部に記憶された内積値が、前記参照ポイントと前記クエリデータの近傍範囲となる任意のベクトルとの内積値の範囲内にある登録データを抽出する第2枝刈部と、前記第2枝刈り部によって抽出された登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部とを有することを特徴とする情報処理装置。前記第2枝刈り部は、前記第1枝刈り部によって抽出された登録データのうち、前記記憶部に記憶された内積値が、前記参照ポイントを前記クエリデータと前記登録データとを含む平面に対して平行に回転させた参照ポイントと前記クエリデータの近傍範囲となる任意のベクトルとの内積値の範囲内にある登録データを抽出することを特徴とする請求項4に記載の情報処理装置。前記記憶部に記憶された登録データのうち、任意の2つの登録データからの距離の差が最大となる位置に前記参照ポイントを設定することを特徴とする請求項4または5に記載の情報処理装置。前記記憶部に記憶された登録データのうち、任意の2つの登録データからの内積の差が最大となる位置に前記参照ポイントを設定することを特徴とする請求項4または5に記載の情報処理装置。予め定められた複数の基準参照ポイントのうち、検索対象である登録データに最も近い基準参照ポイントを選択する第1選択部と、予め定められた複数の補助参照ポイントから、前記登録データの近傍に位置する補助参照ポイントを選択する第2選択部と、前記登録データと、該登録データと前記第1選択部によって選択された基準参照ポイントとの距離と、該登録データと前記第2選択部によって選択された補助参照ポイントとの距離とを記憶する記憶部と、検索要求に係るクエリデータの近傍に位置する補助参照ポイントを選択する第3選択部と、前記記憶部が記憶した前記登録データと前記基準参照ポイントとの距離を用いて、検索要求に係るクエリデータと該基準参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと該基準参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索する近傍候補検索部と、前記記憶部が記憶した登録データと前記第2選択部によって選択された補助参照ポイントとの距離を用いて、前記近傍候補検索部によって検索された登録データのうち、前記第2選択部および前記第3選択部が選択した補助参照ポイントとクエリデータとの距離と、前記第2選択部および前記第3選択部が選択した補助参照ポイントと登録データとの距離との差が所定の近傍範囲内にある登録データを抽出する枝刈り部と前記枝刈り部によって抽出された登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部とを有することを特徴とする情報処理装置。前記記憶部は、さらに、前記補助参照ポイントごとに当該補助参照ポイントと前記基準参照ポイントとの距離を記憶し前記第2選択部は、前記記憶部が記憶した前記補助参照ポイントと前記基準参照ポイントとの距離を用いて、前記基準参照ポイントからの距離が、前記登録データと前記基準参照ポイントとの距離から前記近傍範囲に応じた距離を減じた値よりも大きく、前記登録データと前記参基準照ポイントとの距離から前記近傍範囲に応じた距離を加算した値よりも小さい補助参照ポイントを選択し、前記第3選択部は、前記記憶部が記憶した該登録データと前記第1選択部によって選択された基準参照ポイントとの距離を用いて、前記基準参照ポイントからの距離が、前記クエリデータと前記基準参照ポイントとの距離から前記近傍範囲に応じた距離を減じた値よりも大きく、前記クエリデータと前記基準参照ポイントとの距離から前記近傍範囲に応じた距離を加算した値よりも小さい登録データを選択することを特徴とする請求項8に記載の情報処理装置。前記記憶部は、さらに、各補助参照ポイントのハッシュ値を記憶し、前記第2選択部は、前記記憶部が記憶する各補助参照ポイントのハッシュ値を用いて、前記登録データのハッシュ値と一致するハッシュ値を有する補助参照ポイントを選択し、前記第3選択部は、前記記憶部が記憶した補助参照ポイントのハッシュ値を用いて、前記クエリデータのハッシュ値と一致するハッシュ値を有する補助参照ポイントを選択することを特徴とする請求項8に記載の情報処理装置。検索要求に係るクエリデータを生成する生成装置と、前記生成装置が生成したクエリデータを取得した場合には、検索対象である登録データから前記クエリデータに類似する登録データを検索する情報処理装置と、を有する情報処理システムであって、前記情報処理装置は、前記登録データと、当該登録データの誤差を示す誤差情報とを対応付けて記憶する記憶部と、前記クエリデータと前記登録データとの距離から前記誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データを前記記憶部から検索する検索部と、を有することを特徴とする情報処理システム。検索要求に係るクエリデータを生成する生成装置と、前記生成装置が生成したクエリデータを取得した場合には、検索対象である登録データから前記クエリデータに類似する登録データを検索する情報処理装置と、を有する情報処理システムであって、前記情報処理装置は、前記登録データともに、予め定められた参照ポイントと各登録データとの距離と、前記参照ポイントと各登録データとの内積値を記憶する記憶部と、前記記憶部が記憶した参照ポイントと各登録データとの距離を用いて、前記参照ポイントからの距離が、前記クエリデータと前記参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと前記参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索する近傍候補検索部と、前記近傍候補検索部によって検索された登録データのうち、前記クエリデータと前記参照ポイントとの距離と、前記登録データと前記参照ポイントとの距離との差が所定の近傍範囲内にある登録データを抽出する第1枝刈部と、前記第1枝刈部によって抽出された登録データのうち、前記記憶部に記憶された内積値が、前記参照ポイントと前記クエリデータの近傍範囲となる任意のベクトルとの内積値の範囲内にある登録データを抽出する第2枝刈部と、前記第2枝刈り部によって抽出された登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部とを有することを特徴とする情報処理システム。検索要求に係るクエリデータを生成する生成装置と、前記生成装置が生成したクエリデータを取得した場合には、検索対象である登録データから前記クエリデータに類似する登録データを検索する情報処理装置と、を有する情報処理システムであって、前記情報処理装置は、予め定められた複数の基準参照ポイントのうち、前記登録データに最も近い基準参照ポイントを選択する第1選択部と、予め定められた複数の補助参照ポイントから、前記登録データの近傍に位置する補助参照ポイントを選択する第2選択部と、前記登録データと、該登録データと前記第1選択部によって選択された基準参照ポイントとの距離と、該登録データと前記第2選択部によって選択された補助参照ポイントとの距離とを記憶する記憶部と、検索要求に係るクエリデータの近傍に位置する補助参照ポイントを選択する第3選択部と、前記記憶部が記憶した前記登録データと前記基準参照ポイントとの距離を用いて、検索要求に係るクエリデータと該基準参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと該基準参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索する近傍候補検索部と、前記記憶部が記憶した登録データと前記第2選択部によって選択された補助参照ポイントとの距離を用いて、前記近傍候補検索部によって検索された登録データのうち、前記第2選択部および前記第3選択部が選択した補助参照ポイントとクエリデータとの距離と、前記第2選択部および前記第3選択部が選択した補助参照ポイントと登録データとの距離との差が所定の近傍範囲内にある登録データを抽出する枝刈り部と前記枝刈り部によって抽出された登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部とを有することを特徴とする情報処理システム。検索対象である登録データから検索要求に係るクエリデータと類似する登録データを検索する情報処理装置が実行する検索方法であって、検索対象である登録データと、当該登録データの誤差を示す誤差情報とを対応付けて記憶し検索要求に係るクエリデータと前記登録データとの距離から前記誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データを検索することを特徴とする検索方法。検索対象である登録データから検索要求に係るクエリデータと類似する登録データを検索する情報処理装置が実行する検索方法であって、検索対象である登録データともに、予め定められた参照ポイントと各登録データとの距離と、前記参照ポイントと各登録データとの内積値を記憶し、前記記憶した参照ポイントと各登録データとの距離を用いて、前記参照ポイントからの距離が、検索要求に係るクエリデータと前記参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと前記参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索し、前記検索した登録データのうち、前記クエリデータと前記参照ポイントとの距離と、前記登録データと前記参照ポイントとの距離との差が所定の近傍範囲内にある登録データを抽出し、前記抽出した登録データのうち、前記記憶した内積値が、前記参照ポイントと前記クエリデータの近傍範囲となる任意のベクトルとの内積値の範囲内にある登録データを抽出し、前記抽出した登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定することを特徴とする検索方法。予め定められた複数の基準参照ポイントのうち、検索対象である登録データに最も近い基準参照ポイントを選択し、予め定められた複数の補助参照ポイントから、前記登録データの近傍に位置する補助参照ポイントを選択し、前記登録データと、該登録データと前記選択した基準参照ポイントとの距離と、該登録データと前記選択した補助参照ポイントとの距離とを記憶し、検索要求に係るクエリデータの近傍に位置する補助参照ポイントを選択し、前記記憶した前記登録データと前記基準参照ポイントとの距離を用いて、検索要求に係るクエリデータと該基準参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと該基準参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索し、前記記憶した登録データと前記選択した補助参照ポイントとの距離を用いて、前記検索した登録データのうち、前記選択した補助参照ポイントとクエリデータとの距離と、前記選択した補助参照ポイントと登録データとの距離との差が所定の近傍範囲内にある登録データを抽出し前記抽出した登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定することを特徴とする検索方法。しかしながら、上述した近傍検索を行う技術では、登録データを多次元空間内の1つの点とし、データベースに登録された各データとクエリデータとの距離のみに基づいて、クエリデータの近傍検索を行う。このため、データベースに登録されたデータごとに異なる誤差が存在する場合には、適切な近傍検索を行う事ができないという問題があった。例えば、指紋や静脈などの生体データは、取得時の状況によって変化するため、同一人物の生体データであっても、クエリデータとデータベースに登録されたデータとが完全に一致することは稀である。また、個人差や生体データの取得環境等によってデータベースに登録されるデータとクエリデータとにはバラつきが生じる。このため、情報処理装置は、バラつきが大きい生体データをクエリデータとした際に、データとクエリデータとの距離のみに基づく近傍検索を実行した場合には、検索結果に含めるべきデータの検索漏れを発生させてしまう場合がある。図22は、従来の近傍検索を説明するための図1である。例えば、図22に示す例では、情報処理装置は、図22中Aに示すクエリデータから図22中Bの範囲に含まれるデータを近傍範囲のデータとする。ここで、情報処理装置は、図22中Cが検索結果に含めるべきデータであっても、データのバラつきが大きく、入力されたクエリデータが図22中Cに示すデータから遠い場合には、検索結果に含めるべきデータの検索漏れを生じさせてしまう。また、図23は、従来の近傍検索を説明するための図2である。例えば、図23に示すように、情報処理装置は、データの検索漏れを防ぐため、図23中Aに示すクエリデータの近傍となる範囲を図23中Bに示すように広く設定した場合には、バラつきが少ないデータを必要以上に検索結果に含めてしまう。この結果、情報処理装置は、クエリデータとの距離を算出するデータの数を多くしてしまう結果、近傍検索に要する計算コストを大きくしてしまう。開示の技術は、上述した問題に鑑みてなされたものであり、検索漏れを防ぐことができる。1つの側面では、利用者から指定されたクエリデータに類似するデータを検索する情報処理装置である。このような情報処理装置は、検索対象である登録データと、登録データの誤差を示す誤差情報とを対応付けて記憶するデータベースを有する。そして、情報処理装置は、検索要求に係るクエリデータと登録データとの距離から誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データをデータベースから検索する。1つの側面では、検索漏れを防ぐことができる。以下に添付図面を参照して本願に係る情報処理装置、情報処理システムおよび検索方法について説明する。以下の実施例1では、図を用いて、利用者から入力された生体データに基づいて、利用者の認証を行う情報処理システムについて説明する、図1は、実施例1に係る情報処理システムを説明するための図である。図1に示す例では、情報処理システム1は、認証サーバ3と情報処理装置10を有する。また情報処理システム1は、ネットワークを介して、利用者の生体データを取得するクライアント装置2と接続されている。情報処理システム1は、利用者から取得された生体データと同一人物の生体データがデータベースに存在するかを判別する1:N認証と呼ばれる生体認証を実行する情報処理システムである。情報処理システム1は、ネットワークを介して、利用者から取得された生体データをクライアント装置2から取得する。ここで、クライアント装置2は、利用者の生体データとして、指紋、静脈の画像データ、虹彩等の生体データを取得し、取得した生体データを暗号化した後に、ネットワークを介して、暗号化した生体データを情報処理システム1に送信する。情報処理システム1が有する情報処理装置10は、生体データを記憶するデータベースを有し、復号化した生体データと類似するデータをデータベースから検索する。この際、情報処理装置10は、近傍検索の技術を用いて、効率良く類似するデータを検索する。その後、認証サーバ3は、情報処理装置10が検索したデータとクライアント装置2が取得した生体データとのマッチングを実行し、利用者の認証を実行する。その後、情報処理システム1は、利用者の認証結果を暗号化し、ネットワークを介して、クライアント装置2へ暗号化した認証結果を送信する。ここで、認証サーバ3が実行する生体データのマッチング方法としては、指紋や静脈の認証のために様々な特徴量を使用する方法が知られている。例えば、認証サーバ3は、特許文献7~9に例示する生体データ画像中の小領域における隆線の方向や長さ、勾配、隆線の終端や分岐などの特徴的な点の密度や座標や周波数成分などを用いた手法を採用することができる。また、認証サーバ3は、これら生体データ画像中の特徴を示す数値をベクトル化したものを特徴量ベクトルとして用いることができる。特許文献7特許第2815045号画像特徴抽出装置、画像特徴解析装置、および画像照合システム特許文献8特開2006277407照合方法および照合装置特許文献9特開2007249339生体認証方法及び生体認証装置次に、図2を用いて、情報処理装置10について説明する。図2は、実施例1に係る情報処理装置を説明するための図である。図2に示す例では、情報処理装置10は、データ登録処理部20と検索処理部30を有する。データ登録処理部20は、データベース21、参照ポイント情報記憶部22、最大誤差情報記憶部23、インデックス記憶部24、距離算出部25、インデックス登録部26を有する。また、検索処理部30は、インデックス検索範囲算出部31、インデックス検索部32、近傍データ確定部33を有する。データベース21は、利用者の生体データである登録データを記憶する。また、データベース21は、各登録データの誤差を示す誤差パラメータを登録データごとに記憶する。以下、新規利用者の生体データを新たに登録する例を用いて、データベース21に生体データと誤差パラメータとを登録する処理について説明する。例えば、新規利用者は、新たに登録するデータとして、同時期に取得した複数の生体データを情報処理装置10に入力する。情報処理装置10は、入力された複数の生体データから得られる特徴量の平均や分散などの統計量を用いて、入力された生体データの特徴を示す特徴量ベクトルおよび誤差パラメータを算出する。その後、情報処理装置10は、算出した特徴量ベクトルを登録データとし、図2中Bに示すように、データベース21に格納する。また、情報処理装置10は、算出した誤差パラメータを算出した特徴量ベクトル、すなわち登録データと対応付けて、データベース21に格納する。ここで、誤差パラメータは各データのバラつき度合いを表すものであり、データの登録時に与えられる。例えば、生体認証システムを考えた場合、生体データの登録の際には複数回の生体データの採取を行うのが一般的であるため、複数個の生体データから得られる特徴量の平均や分散などの統計量を用いて特徴量ベクトルや誤差パラメータを与えることができる。また、登録データ採取時のデバイスの精度や設置状況などから推測できる生体データの質から誤差パラメータを設定することとしてもよい。また、生体データは、データを登録してから年月が経過するとクエリデータとして取得する生体データが変化することも考えられるため、登録からの年月に応じて誤差パラメータを変化させるようにしてもよい。参照ポイント情報記憶部22は、参照ポイントの位置を示す情報を記憶する。例えば、参照ポイント情報記憶部22は、図2中Aに示すように、あらかじめ設定された多次元空間内における複数の参照ポイントo1~oMの位置を示す情報を受信した場合には、受信した参照ポイントの位置を示す情報を記憶する。ここでデータベース21は、生体データの特徴量を示す特徴量ベクトルを登録データとして記憶する。そこで、参照ポイント情報記憶部22は、データベース21が採用する特徴量ベクトルの次元数と同じ次元数の任意のベクトルを参照ポイント情報として記憶する。最大誤差情報記憶部23は、各参照ポイントと対応付けられた登録データに係る誤差パラメータのうち、最も大きい値を有する誤差パラメータを参照ポイントと対応付けて記憶する。また、最大誤差情報記憶部23は、参照ポイントと対応付けられた登録データのうち、参照ポイントから最も遠方に位置する登録データと参照ポイントとの距離を各参照ポイントと対応付けて記憶する。例えば、参照ポイントoiに複数の登録データp1~pxが対応付けられており、各登録データp1~pxの誤差パラメータがε1~εXであり、誤差パラメータがε1~εXのうち、最大の値を有する誤差パラメータをεimaxとする。また、登録データp1~pxのうち、参照ポイントolから最も遠方にある登録データまでの距離がrimaxであるとする。このような場合には、最大誤差情報記憶部22は、oiとεimaxとrimaxとを対応付けて記憶する。以下の説明においては、各登録データと対応付けられた参照ポイントを対応参照ポイントとして説明する。インデックス記憶部24は、検索処理部30がクエリデータの近傍候補となるデータをデータベース21から検索するために利用するインデックスを記憶する。具体的には、インデックス記憶部24は、参照ポイントごとに、後述するインデックス登録部26によって算出されるキー値と、キー値と対応する登録データと、登録データの誤差パラメータとを対応付けて記憶する。以下、図3を用いて、インデックス記憶部24が記憶するインデックスについて説明する。図3は、実施例1に関するインデックスの一例を説明するための図である。図3に示すように、インデックスは、Tree型のインデックスであり、図3中Aに示すように、インデックス登録部26によって算出されたキー値を階層的に有する。また、図3中Bに示すように、対応するキー値と対応付けて、登録データと登録データの誤差パラメータとを有する。つまり、インデックスは、インデックス登録部26によって登録データごとに算出されるキー値を階層的に有し、各キー値と対応するデータとして登録データと誤差パラメータとを記憶する。図2に戻って、距離算出部25は、入力された登録データと参照ポイントとの距離を算出し、算出した距離をインデックス登録部26に通知する。具体的には、距離算出部25は、図2中Bに示すように、登録データがデータベース21に格納される際に、登録データと参照ポイント情報記憶部22に格納されている各参照ポイントとの距離を算出する。そして、距離算出部25は、算出した距離のうち、最も近い距離、つまり、対応参照ポイントと登録データとの距離を、図2中Cに示すように、インデックス登録部26に通知する。また、距離算出部25は、対応参照ポイントと登録データと登録データの誤差パラメータとをインデックス登録部26に通知する。インデックス登録部26は、距離算出部25が算出した距離に基づいて、対応参照ポイントごとに異なる範囲のキー値を生成する。そして、インデックス登録部26は、図2中Dに示すように、インデックス記憶部24が記憶するインデックスに、生成したキー値と対応するデータとして登録データと登録データの誤差パラメータとを追加する。また、インデックス登録部26は、図2中Eに示すように、対応参照ポイントと対応付けられた登録データの誤差パラメータのうち、最も大きい値を有する誤差パラメータを対応参照ポイントと対応付けて最大誤差情報記憶部23に格納する。また、インデックス登録部26は、対応参照ポイントと対応付けられた各登録データとの距離のうち、最も大きい値を有する距離を対応参照ポイントと対応付けて最大誤差情報記憶部23に格納する。このように、データ登録処理部20は、登録データと誤差パラメータとを記憶する。また、データ登録処理部20は、登録データと誤差パラメータとを記憶する際に、対応参照ポイントと登録データとの距離を算出し、算出した距離の値をキー値とするインデックスを作成する。また、データ登録処理部20は、対応参照ポイントと対応付けられる登録データの誤差パラメータのうち、最も大きい誤差パラメータの値と、対応参照ポイントと対応付けられた登録データとの距離のうち、最も大きい距離の値とを対応参照ポイントごとに記憶する。次に、検索処理部30が有する各部について説明する。インデックス検索範囲算出部31は、認証を行う生体データ、つまり、クエリデータを取得した場合には、誤差パラメータを考慮して、取得したクエリデータの近傍候補として検索されるデータのキーの範囲を算出する。そして、インデックス検索範囲算出部31は、算出したキーの範囲をインデックス検索部32に通知する。例えば、インデックス検索範囲算出部31は、図2中Fに示すように、クエリデータを取得する。また、インデックス検索範囲算出部31は、図2中Gに示すように、近傍のデータとみなす近傍範囲を示す情報、つまり、多次元空間内においてクエリデータを中心とした多次元球の半径を取得する。このような場合には、インデックス検索範囲算出部31は、距離算出部25の機能を用いて、各参照ポイントとクエリデータとの距離を算出する。また、インデックス検索範囲算出部31は、各参照ポイントと対応付けて記憶された誤差パラメータの最大値と登録データとの距離の最大値とを最大誤差情報記憶部23から取得する。そして、インデックス検索範囲算出部31は、各参照ポイントについて、算出した各距離から近傍範囲を減じた値が、対応づけて記憶された誤差パラメータの最大値と距離の最大値との和よりも小さいか否かを判別する。そして、インデックス検索範囲算出部31は、算出した各距離から近傍範囲を減じた値が、対応づけて記憶された誤差パラメータの最大値と距離の最大値との和よりも小さいと判別した参照ポイントについて、以下の処理を実行する。すなわち、インデックス検索範囲算出部31は、参照ポイントとクエリデータとの距離と、近傍範囲を示す情報と、参照ポイントと対応づけて記憶された誤差パラメータの最大値とを用いて、クエリデータの近傍候補となる登録データのキー値の範囲を算出する。そして、インデックス検索範囲算出部31は、算出したキー値の範囲を図2中Iに示すように、インデックス検索部32に通知する。インデックス検索部32は、インデックス検索を行い、インデックス検索範囲算出部31が算出したキー値の範囲に含まれるデータ、つまり、クエリデータの近傍候補となるデータを判別する。そして、インデックス検索部32は、判別したクエリデータの近傍候補となるデータを近傍データ確定部33に通知する。例えば、インデックス検索部32は、インデックス検索範囲算出部31からキー値の範囲を取得した場合には、取得したキー値の範囲に含まれる登録データをインデックスから検索する。そして、インデックス検索部32は、図2中Jに示すように、判別した登録データを近傍データ確定部33に通知する。近傍データ確定部33は、クエリデータの近傍候補となる各登録データについて、クエリデータと登録データとの距離から誤差パラメータを減じた値が近傍範囲に含まれるか否かを判別する。そして、近傍データ確定部33は、クエリデータと登録データとの距離から誤差パラメータを減じた値が近傍範囲に含まれるか否かを判別したデータを近傍データとして認証サーバ3に出力する。例えば、近傍データ確定部33は、インデックス検索部32がインデックス記憶部24に記憶されたインデックスから検索したクエリデータの近傍候補となる登録データの通知を受ける。このような場合には、近傍データ確定部33は、通知された各登録データについて、クエリデータと登録データとの距離から誤差パラメータの値を減算した値が近傍範囲の値よりも小さいか否かを判別する。つまり、近傍データ確定部33は、各登録データと誤差パラメータとが示す範囲が、クエリデータの近傍範囲と重複しているか否かを判別する。そして、近傍データ確定部33は、クエリデータと登録データとの距離から誤差パラメータの値を減算した値が近傍範囲の値よりも小さいと判別した場合には、通知された登録データがクエリデータの近傍データであると判別する。その後、近傍データ確定部33は、クエリデータの近傍データであると判別した各登録データを図2中Kに示すように、認証サーバ3に送信する。このように、検索処理部30は、クエリデータと近傍範囲とを取得した場合には、インデックスを用いて、誤差パラメータの最大値を考慮したクエリデータの近傍候補となる登録データを検索する。そして、検索処理部30は、検索した各登録データについて、各登録データと誤差パラメータとが示す範囲が、クエリデータの近傍範囲と重複しているか否かを判別し、重複していると判別した登録データをクエリデータの近傍データであると判別する。このため、検索処理部30は、各登録データの誤差パラメータにバラつきがある場合にも、検索漏れを起こすことなく、近傍検索を行うことができる。つまり、検索処理部30は、誤差パラメータが大きい登録データについては、クエリデータの近傍データであると判別する範囲を広くし、誤差パラメータが小さい登録データについては、クエリデータの近傍データであると判別する範囲を小さくする。このため、検索処理部30は、検索漏れを防ぐと同時に、不要な登録データを近傍データから極力除外することができる。この結果、検索処理部30は、適切な近傍検索を行う事ができる。また、検索処理部30は、近傍データであるか否かを判別する前に、インデックスを用いて、近傍データであるか否かを判別する登録データを限定する。このため、検索処理部30は、クエリデータと登録データとの距離を算出する処理を最小限に押さえるので、計算コストを削減し、かつ、高速で近傍検索を行うことができる。例えば、距離算出部25、インデックス登録部26、インデックス検索範囲算出部31、インデックス検索部32、近傍データ確定部33とは、電子回路である。ここで、電子回路の例として、ASICApplicationSpecificIntegratedCircuitやFPGAFieldProgrammableGateArrayなどの集積回路、またはCPUCentralProcessingUnitやMPUMicroProcessingUnitなどを適用する。また、データベース21、参照ポイント情報記憶部22、最大誤差情報記憶部23、インデックス記憶部24とは、RAMRandomAccessMemory、ROMReadOnlyMemory、フラッシュメモリflashmemoryなどの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。次に、図4~図6および数式を用いて、情報処理装置10が実行する処理の具体例について説明する。なお、以下の説明においては、登録対象データをp、登録対象データに関する誤差パラメータをε、各参照ポイントをo1~om、参照ポイントの数をMと記載する。また、データXとデータYとの多次元空間内における距離を算出する距離関数をdX、Yと記載する。まず、新たなデータを登録データとしてデータベース21に格納する処理について説明する。まず、情報処理装置10は、距離関数を用いて、各参照ポイントと登録対象データとの距離を算出し、登録されるデータpに距離が最も近い参照ポイントを対応参照ポイントojとして選択する。次に、情報処理装置は、以下の式1と、選択したojとを用いて、登録対象データのキー値Kpを算出する。ここで、式1中のCは定数である。Cが十分大きい場合には、参照ポイントojに対応する登録データのキー値は、[j×C、j1×Cの範囲に収まることとなる。なお、[j×C、j1×Cとは、j×C以上j1×C未満の範囲を示す。つまり、情報処理装置10は、各登録データに対して、対応参照ポイントごとに、異なる範囲のキー値を算出することとなる。例えば、情報処理装置10は、C=1000とした場合には、参照ポイントo1に対応する登録データのキー値の範囲を[1000、2000]の範囲に収めることができる。次に、情報処理装置10は、算出したKpの値をキーとして、登録対象データpと誤差パラメータεをインデックス記憶部24が記憶するインデックスとデータベース21とに追加する。ここで、インデックス記憶部24が記憶するインデックスのデータ構造は、範囲検索が行える構造であれば任意の構造を適用することができるが、例えば、B-TreeやB-Treeなどのデータ構造を適用することができる。また、情報処理装置10は、参照ポイントojと対応する登録データと参照ポイントojとの距離が最大の距離rjmaxをojと対応付けて最大誤差情報記憶部23に格納する。また、参照ポイントojと対応する登録データの誤差パラメータのうち、最大の値を有する誤差パラメータをεjmaxとして最大誤差情報記憶部23に格納する。また、情報処理装置10は、登録対象データpをデータベース21に格納するたびに、rjmaxまたはεjmaxが更新されるか否かを判別し、更新される場合には、rjmaxまたはεjmaxを新たな値に更新する。次に、情報処理装置10が入力されたクエリデータと近傍範囲を示す情報とに応じて、近傍データを検索する処理について説明する。以下の説明においては、入力されたクエリデータをq、近傍範囲を示す情報をUとして説明する。まず、情報処理装置10は、全ての参照ポイントoii=1、2、...Mについて以下の式2を満たすか否かを判別し、満たすと判別した場合には、各参照ポイントと対応付けられた登録データがクエリデータの近傍候補になると判別する。次に、情報処理装置10は、式2を満たす参照ポイントoiについて、あらかじめ作成したインデックスから、誤差パラメータを考慮したキーの値が式3で示される範囲の登録データを検索する。つまり、情報処理装置10は、インデックスを利用して式3を満たす範囲のインデックスを検索することで、クエリデータの近傍候補となるデータを検索する。このため、情報処理装置10は、クエリデータの近傍候補となるデータを高速で検索することができる。ここで、図4は、インデックス検索の一例を説明するための図である。図4中Aは参照ポイントoiを示し、図4中Bは、クエリデータを示す。また、図4中Cは、参照ポイントoiからrimaxεimaxの範囲を示す。また、図4中Dは、登録データに係る誤差パラメータが示す誤差の範囲を示す。また、図4中Eは、入力されたUが示す近傍範囲を示し、図4中Fは、クエリデータからUεimaxの範囲を示す。情報処理装置10は、参照ポイントと登録データとの距離から算出される値をキーとしてインデックスに登録している。このため、式3を満たす登録データ、つまり近傍候補となる登録データは、図4に示すドーナツ状の網掛けした範囲に含まれる登録データとなる。次に、情報処理装置10は、インデックス検索によって取得した近傍候補の登録データとクエリデータとの距離を実際に算出し、算出した距離から誤差パラメータに応じた距離を減じた値が近傍範囲に含まれるか否かを判別する。つまり、情報処理装置10は、近傍候補の各登録データとクエリデータとの距離が、以下の式4を満たすか否かを判別する。なお、式4中のvは、インデックス検索によって取得した近傍候補データを示し、εvは、近傍候補データの誤差パラメータである。その後、情報処理装置10は、式4を満たす近傍候補データを近傍データであると判別した場合には、図5中の網掛けをした丸印で示される登録データを近傍データとして認証サーバ3に送信する。なお、図5は、インデックス検索の一例を説明するための図2である。図5中Aは、参照ポイントoiを示し、図5中Bは、クエリデータを示す。また、図4中Cは、式4を満たす登録データを示し、図4中Dは、同図中Cに示す登録データの誤差パラメータが示す誤差の範囲を示す。また、図5中Eは、入力されたUが示す近傍範囲である。次に、図6を用いて、情報処理装置10による近傍データの検索結果について詳細に説明する。図6は、実施例1に係る検索処理の結果の一例を説明するための図である。図6中Aは、参照ポイントを示し、図6中Bは、近傍範囲を示す。また、図6中網がけした丸印は、近傍データとして検索された登録データを示す。情報処理装置10は、式4を満たす登録データを近傍データとした場合には、図6中Cに示すように、近傍範囲に登録データが含まれていなくとも、誤差パラメータが示す範囲が近傍範囲と重複する登録データを近傍データであると判別する。このため、情報処理装置10は、図6中Cに示すような、従来取りこぼしてしまう誤差の大きな登録データを近傍データに含めることができる。[情報処理装置10の処理の流れ]次に、図7を用いて、情報処理装置10が新たなデータを登録する処理の流れの一例について説明する。図7は、実施例1に係る登録処理の流れの一例を説明するためのフローチャートである。図7に示す例では、情報処理装置10は、データベース21に新たに登録するデータと誤差パラメータとを受信したことをトリガとして、処理を開始する。まず、情報処理装置10は、新たに登録する登録対象データと誤差パラメータとをデータベース21に格納するステップS101。次に、情報処理装置10は、登録対象データの対応参照ポイントを算出するステップS102。次に、情報処理装置10は、算出した対応参照ポイントと登録データとの距離に基づいて、登録データのキー値を算出し、算出したキー値と登録対象データと誤差パラメータとをインデックス記憶部24に記憶されたインデックスに登録するステップS103。次に、情報処理装置10は、算出した距離または取得した誤差パラメータが対応参照ポイントと対応付けられた距離の最大値または誤差パラメータの最大値を更新しているか否かを判別するステップS104。そして、情報処理装置10は、対応参照ポイントと対応付けられた距離の最大値または誤差パラメータの最大値を更新していると判別した場合にはステップS104肯定、以下の処理を実行する。すなわち、情報処理装置10は、対応参照ポイントと対応付けられた距離の最大値または誤差パラメータの最大値を更新しステップS105、登録処理を終了する。一方、情報処理装置10は、対応参照ポイントと対応付けられた距離の最大値または誤差パラメータの最大値を更新してないと判別した場合にはステップS104否定、そのまま登録処理を終了する。次に、図8を用いて、情報処理装置10が入力されたクエリデータの近傍データを検索する処理の流れの一例について説明する。図8は、実施例1に係る検索処理の流れの一例を説明するためのフローチャートである。図8に示す例では、情報処理装置10は、クエリデータおよび近傍範囲を示す情報を取得したことをトリガとして、検索処理を開始する。まず、情報処理装置10は、クエリデータおよび近傍範囲を示す情報とを取得するステップS201。このような場合には、情報処理装置10は、取得したクエリデータの近傍候補となる登録データと対応付けられた対応参照ポイントと、近傍候補となる登録データのキー値の範囲とを算出するステップS202。次に、情報処理装置10は、算出したキー値の範囲に含まれる登録データ、つまり近傍候補となる登録データをインデックスから検索するステップS203。次に、情報処理装置10は、インデックスから検索した各登録データについて、クエリデータとの距離を算出し、近傍データの確定を行うステップS204。次に、情報処理装置10は、確定した近傍データのリストを出力しステップS205、処理を終了する。[実施例1の効果]上述したように、情報処理装置10は、検索対象である登録データと各登録データの誤差を示す誤差パラメータとを対応付けて記憶する。そして、情報処理装置10は、クエリデータと登録データとの距離から、誤差パラメータに応じた距離を減じた値が所定の近傍範囲内にある登録データを近傍データとする。このため情報処理装置10は、誤差が大きい登録データの検索漏れを防ぐことができる。また、情報処理装置10は、誤差が小さい登録データを必要以上に検索することがないので、認証サーバ3が実行するマッチング処理の計算コストを少なくすることができる。この結果、情報処理システム1は、適切な認証処理を実行させることができる。また、情報処理装置10は、登録データと対応参照ポイントとの距離と、対応参照ポイントと対応する各登録データとの距離の最大値と、対応参照ポイントと対応する各登録データの誤差パラメータの最大値とをあらかじめインデックスとして記憶する。そして、情報処理装置10は、クエリデータと対応参照ポイントとの距離と対応参照ポイントと対応する各登録データの誤差パラメータの最大値とから算出される値をキーとして、インデックスから近傍候補となる登録データを検索する。その後、情報処理装置10は、検索した近傍候補となる登録データとクエリデータとの距離を算出し、近傍データを確定する。このため、情報処理装置10は、全ての登録データとクエリデータとの距離を算出せずとも、クエリデータの近傍データを確定することができる。すなわち、情報処理装置10は、インデックスを用いて明らかにクエリデータの近傍データから除外できる登録データを除外し、その後、距離を算出することで、近傍データか否かを判別する。このため、情報処理装置10は、クエリデータとの距離を算出する登録データの数を限定することができる。この結果、情報処理装置10は、近傍検索に要する計算コストを削減し、より効率的な近傍検索を行う事ができる。実施例2では、参照ポイントと登録データとの距離以外の情報をインデックスとして記憶することによって、近傍候補をさらに効率良く検索する情報処理装置10aについて説明する。ここで、従来の近傍検索を行う技術では、データベースに登録された各データとクエリデータとの距離のみに基づいて、クエリデータの近傍検索を行う。このため、登録データの数が多くなった場合や、登録データを記憶する際に適用する多次元空間の次元数が多く、距離を算出するための計算コストが高い場合には、近傍検索に要する計算コストが距離計算の回数に等しくなる。つまり、参照ポイントと登録データとの距離をインデックスとして記憶し、三角不等式を用いて近傍候補から登録データの枝刈を行う技術では、多次元空間の次元数が多くなった場合には計算コストが多くなるという問題があった。また、登録データと参照ポイントとの距離のみを用いて登録データの枝刈を行う技術では、参照ポイントからの距離が所定の範囲外の登録データを枝刈する。このため、参照ポイントを中心点とした際に、所定の範囲内にある登録データのうち、クエリデータと反対側に位置する登録データを除外することができない。この結果、近傍データを確定する際の計算コストが多くなるという問題があった。実施例2に開示の技術は、上述した問題に鑑みてなされたものであって、適切に枝刈を行い、近傍データを確定する際の計算コストを削減する。図9は、実施例2に係る情報処理装置を説明するための図である。図9に示す例では、情報処理装置10aは、データ登録処理部20a、検索処理部30aを有する。データ登録処理部20aは、データベース21a、参照ポイント情報記憶部22、インデックス記憶部24a、距離算出部25、インデックス登録部26a、内積算出部27を有する。また、検索処理部30aは、インデックス検索範囲算出部31、インデックス検索部32、候補枝刈り部34、近傍データ確定部33を有する。なお、情報処理装置10aが有する各部のうち、実施例1に係る情報処理装置10が有する各部と同様の処理を実行するものについては、同一の符号を付し、詳細な説明を省略する。また、以下の説明においては、情報処理装置10aは、各登録データの誤差パラメータを考慮せずに、処理を実行するものとする。また、情報処理装置10aは、実施例1に係る情報処理装置10と同様に、生体データのマッチングを行う情報処理システム1aが有する情報処理装置である。データベース21aは、登録データと、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを対応付けて記憶する。インデックス記憶部24aは、登録データと対応参照ポイントとの距離に基づく値をキー値として、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とをインデックスとして記憶する。ここで、図10は、インデックス記憶部24aを説明するための図である。図10に示す例では、インデックス記憶部24aは、実施例1に係るインデックス記憶部24と同様の構成を有するインデックスを記憶する。つまり、図10中Aに示すように、登録データと対応参照ポイントとの距離に基づくキー値を階層的に有し、図10中Bに示すように、登録データと各参照ポイントとの距離および内積値をキー値と対応付けたインデックスを記憶する。図9に戻って、内積算出部27は、登録データと各参照ポイントとの内積値を算出する。例えば、内積算出部27は、図9中Aに示すように、登録データを取得した場合には、取得した登録データと参照ポイント情報記憶部22に格納された各参照ポイントとの内積を算出する。ここで、内積算出部27が算出する内積とは、登録データを示す特徴量ベクトルと各参照ポイントを示す特徴量ベクトルとの内積である。換言すると、内積算出部27は、登録データを多次元空間内のポイントとして示した場合に、同じ多次元空間内に位置する各参照ポイントを終端とするベクトルと、登録データを終端とするベクトルとの内積である。インデックス登録部26aは、距離算出部25が算出した登録データと各参照ポイントとの距離と、内積算出部27が算出した登録データと各参照ポイントとの内積とをインデックス記憶部24aが記憶するインデックスに追加する。例えば、インデックス登録部26aは、距離算出部25が算出した登録データと各参照ポイントとの距離を取得する。また、インデックス登録部26aは、内積算出部27が算出した登録データと各参照ポイントとの内積とを取得する。そして、インデックス登録部26aは、距離算出部25が算出した距離のうち、最も短い距離、すなわち、登録データと登録データの対応参照ポイントとの距離に基づくキー値を算出する。その後、インデックス登録部26aは、算出したキー値と対応付けて、登録データと各参照ポイントとの距離と、内積算出部27が算出した登録データと各参照ポイントとの内積とをインデックスに追加する。また、インデックス登録部26aは、登録データと各参照ポイントとの距離と、内積算出部27が算出した登録データと各参照ポイントとの内積とをデータベース21aに格納する。また、インデックス登録部26は、図示しない経路を用いて、対応参照ポイントと対応付けられた各登録データとの距離のうち、最も大きい値を有する距離を対応参照ポイントと対応付けて参照ポイント情報記憶部22に格納する。インデックス検索範囲算出部31は、実施例1と同様に、図9中Cに示すクエリデータと図9中Dに示す近傍範囲を示す情報を取得した場合には、図9中Eに示すように、距離算出部25を利用してクエリデータと各参照ポイントとの距離を算出する。そして、インデックス検索範囲算出部31は、算出したクエリデータと対応参照ポイントとの距離と、近傍範囲を示す情報とを用いて、インデックス検索を行うキー値の範囲を算出する。そして、インデックス検索範囲算出部31は、図9中Fに示すように、算出したキー値の範囲をインデックス検索部32に通知する。インデックス検索部32は、実施例1と同様に、インデックス記憶部24aが記憶するインデックスから、インデックス検索範囲算出部31から取得したキー値の範囲を検索する。そして、インデックス検索部32は、検索された範囲のキー値と対応付けて記憶された登録データと、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを取得する。その後、インデックス検索部32は、図9中Gに示すように、取得された登録データと、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを候補枝刈り部34に通知する。つまり、インデックス検索部32は、インデックスを検索した結果取得した近傍候補の登録データについて、登録データと、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを候補枝刈り部34に通知する。候補枝刈り部34は、インデックス検索部32から取得した登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを用いて、近傍候補となる登録データの枝刈を行う。詳細には、候補枝刈り部34は、インデックス検索部32から取得した近傍候補となる登録データについて、クエリデータと登録データの対応参照ポイントとの距離から登録データと対応参照ポイントとの距離を減じた値が所定の近傍範囲内にあるか否かを判別する。そして、候補枝刈り部34は、クエリデータと登録データの対応参照ポイントとの距離から登録データと対応参照ポイントとの距離を減じた値が所定の近傍範囲内にない場合には、登録データを近傍候補から除外する。また、候補枝刈り部34は、近傍候補となる登録データについて、登録データと対応参照ポイントとの内積からクエリデータと登録データの対応参照ポイントとの内積を減じた値が、以下の条件を満たすか否かを判別する。つまり、候補枝刈り部34は、長さが近傍範囲と等しい任意のベクトルと登録データの対応参照ポイントとの内積よりも大きいか判別する。そして、候補枝刈り部34は、登録データと対応参照ポイントとの内積からクエリデータと登録データの対応参照ポイントとの内積を減じた値が、任意のベクトルと登録データの対応参照ポイントとの内積よりも大きいと判別した場合には、以下の処理を実行する。すなわち、候補枝刈り部34は、登録データを近傍候補から除外する。さらに、候補枝刈り部34は、参照ポイントを多次元空間内における原点を中心として、多次元空間内においてクエリデータが位置する点と登録データが位置する点とを通る平面と平行な面上を回転させる。この際、候補枝刈り部34は、近傍候補から除外する登録データが最大となる位置まで参照ポイントを回転させる。そして、候補枝刈り部34は、登録データと回転後の参照ポイントとの内積からクエリデータと回転後の参照ポイントとの内積を減じた値が、任意のベクトルと回転後の参照ポイントとの内積よりも大きいと判別した場合には、登録データを近傍候補から除外する。その後、候補枝刈り部34は、図9中Hに示すように、近傍候補から除外されなかった登録データを近傍データ確定部33に通知する。このように、候補枝刈り部34は、距離と内積とに基づいて、インデックスから検索された近接候補の枝刈りを実行する。このため、候補枝刈り部34は、近接データを確定するために、クエリデータとの距離を算出する近接候補の数を減らし、近傍データを確定する際の計算コストを削減する。また、候補枝刈り部34は、あらかじめ算出された距離と内積とに基づいて、枝刈りを実行する。つまり、候補枝刈り部34は、予め算出しておいた距離とクエリデータと参照ポイントの距離を利用して三角不等式によって、登録データとクエリデータ間の距離を計測することなく安全にクエリデータの近傍外のデータを検索候補から除外することができる。また、候補枝刈り部34は、予め算出しておいた内積値とクエリデータと参照ポイントの内積値を利用して、登録データとクエリデータ間の距離や内積値を計測することなく安全にクエリデータの近傍外のデータを検索候補から除外することができる。ここで、距離による枝刈りと内積値による枝刈りでは枝刈り可能なデータが異なるので、候補枝刈り部34は、距離による枝刈りと内積値による枝刈りを併用することで、より効果的に近傍候補となる登録データの枝刈りを実行することができる。この結果、情報処理装置10aは、近傍データを確定する際に必要な距離計算回数を削減でき、近傍検索を効率化することが可能となる。さらに、候補枝刈り部34は、内積値による枝刈りを行う場合には、枝刈りする登録データが最も多い位置まで参照ポイントを回転させ、枝刈りを実行する。このため、候補枝刈り部34は、近傍検索をより効率化することができる。図9に戻って、近傍データ確定部33は、近傍候補に残った登録データを取得した場合は、取得した登録データとクエリデータとの距離を算出し、登録データがクエリデータの近傍データであるか否かを確認する。その後、近傍データ確定部33は、図9中Iに示すように、近傍データであると確認された登録データのリストを、認証サーバ3に出力する。例えば、内積算出部25、候補枝刈り部34とは、電子回路である。ここで、電子回路の例として、ASICApplicationSpecificIntegratedCircuitやFPGAFieldProgrammableGateArrayなどの集積回路、またはCPUCentralProcessingUnitやMPUMicroProcessingUnitなどを適用する。次に、図11~図13および数式を用いて、情報処理装置10aが実行する処理の具体例について説明する。なお、以下の説明においては、実施例1と同様の記号を用いるものとし、さらに、データXとデータYとの内積を<XY>で表すものとする。また、説明を簡単にするために、各登録データの誤差パラメータについては、考慮しないものとする。まず、新たなデータを登録データとしてデータベース21aに格納する処理について説明する。まず、情報処理装置10aは、登録対象データと各参照ポイントoii=1~Mとの距離doipと内積値<oip>とを算出し、登録対象データと最も距離が近い参照ポイントを対象参照ポイントojとして選択する。また、情報処理装置10aは、式1と、選択したojとを用いて、登録対象データのキー値Kpを算出する。次に、情報処理装置10aは、算出したKpの値をキーとし、登録対象データpと、算出した登録対象データと各参照ポイントとの距離と、算出した登録対象データと各参照ポイントとの内積値とをインデックス記憶部24aが記憶するインデックスに追加する。また、情報処理装置10aは、登録対象データpと、算出した登録対象データと各参照ポイントとの距離と、算出した登録対象データと各参照ポイントとの内積値とをデータベース21aに登録する。また、情報処理装置10aは、参照ポイントojと対応する登録データと参照ポイントojとの距離が最大の距離rjmaxをojと対応付けて参照ポイント情報記憶部22に格納する。次に、情報処理装置10aが入力されたクエリデータと近傍範囲を示す情報とに応じて、近傍データを検索する処理について説明する。まず、情報処理装置10aは、各参照ポイントoii=1~Mとクエリデータqとの距離doiqと内積値<oiq>を算出する。また、情報処理装置10aは、以下の式5を用いて、参照ポイントoiと対応付けられた登録データが近傍候補になるか否かを判別する。次に、情報処理装置10aは、式5を満たす参照ポイントoiについて、あらかじめ作成したインデックスから、キーの値が以下の式6で示される範囲の登録データを検索する。ここで、図11は、実施例2に係るインデックス検索の一例を説明するための図1である。図11中Aは、参照ポイントoiを示し、図11中Bはクエリデータを示す。また、図11中Cは、参照ポイントoiからrimaxの範囲を示し、図11中Dは、クエリデータからUの範囲を示す。情報処理装置10aは、対応参照ポイントと登録データとの距離とをキーとして各登録データをインデックスに登録している。このため、式6を満たす登録データ、つまり近傍候補となる登録データは、図11に示すドーナツ状の網掛けした範囲内に存在するデータとなる。次に、情報処理装置10aは、インデックスに登録された登録データと各参照ポイントとの距離と登録データと各参照ポイントとの内積値とを用いて、近傍候補の枝刈りを実行する。まず、情報処理装置10aは、予め算出し、インデックスに登録しておいた登録データと各参照ポイントとの距離を用いた枝刈りを実行する。具体的には、情報処理装置10aは、各参照ポイントoii=1~Mについて、以下の式7を満たす登録データを、近傍候補から除外する。なお、式7を用いた枝刈りにおいては、クエリデータと各参照ポイントとの距離を計測するだけで実行することが可能である。ここで、図12は、実施例2に係るインデックス検索の一例を説明するための図2である。図12中Aは、対応参照ポイントを示し、図12中Bは、クエリデータを示す。また、図12中Cは、対応参照ポイントからrimaxの範囲を示し、図12中Dは、クエリデータからUの範囲を示す。また、図12中Eは、対応参照ポイント以外の参照ポイントを示し、図12中Fは、図12中Eに示す参照ポイントについて、式7の条件にあてはまらない範囲を示す。つまり、情報処理装置10aは、各参照ポイントについて、対応付けられた登録データが式7を満たすか否かを判別する。この結果、各参照ポイントについて対応付けられた登録データが式7を満たさない範囲とは、各参照ポイントを中心とするドーナツ状の範囲が重なり合う部分となるため、近傍候補となる登録データは、図12中網掛けをした範囲に含まれる登録データとなる。次に、情報処理装置10a、各参照ポイントについて、インデックスに登録しておいた登録データと各参照ポイントとの内積値を用いた枝刈りを実行する。具体的には、情報処理装置10aは、以下の式8および式9の条件を満たす登録データを近傍候補から除外する。なお、以下の式におけるuは、長さが近傍範囲Uと等しい任意のベクトルを示す。また、式8、式9を書換えると、以下の式10、式11となる。つまり、情報処理装置10aは、式10および式11の条件を満たす登録データを近傍候補から除外することができる。なお、式11中のθpは、登録データpを示すベクトルと参照ポイントoiを示すベクトルとの間の角度を示し、θqは、クエリデータqを示すベクトルと参照ポイントoiを示すベクトルとの間の角度を示す。また、θuは、任意のベクトルuと参照ポイントoiを示すベクトルとの間の角度を示す。ここで、任意のベクトルuの方向は任意であるため、cosθu=1とした際に、以下の式12が成り立つ場合には、任意のuについて式10および式11が成り立つ。つまり、情報処理装置10aは、式12を満たす登録データについて近傍候補から除外することが可能である。なお、情報処理装置10aは、インデックスに登録された内積<oip>=|oi||p|cosθpから|p|cosθpを容易に算出することができる。また、情報処理装置10aは、|q|cosθqについても、検索処理実行時に各参照ポイントに対して1度だけ算出すればよい。つぎに、情報処理装置10aが参照ポイントを多次元空間内における原点を中心として、クエリデータと登録データとを通る平面と平行な面上をαだけ回転させる処理について説明する。このような場合には、式12中のθpをθp±αとし、θqをθq±αとすればよい。このため、式12は、以下の式13式に変形することができる。つまり、情報処理装置10aは、式13を満たす登録データについては、近傍候補から除外することができる。ここで、式13の左辺が最大となるαを考えるため、式13をαで微分した式を考えると、近傍範囲Uはαの変化によって変化しないと考えられるため、dU/dα=0となる。この結果、式13は、以下の式14に変形することができる。この式14をαについて解くと、以下の式15を得ることができる。つまり、αが式15を満たす場合には、式13の左辺が最大となるので、この式15を満たすαの際に式13の条件を満たす登録データを近傍候補から除外した場合には、最も多くの登録データを近傍候補から除外することができる。ここで、図13は、実施例2に係るインデックス検索の一例を説明するための図3である。図13中Aは、対応参照ポイントを示し、図13中Bはクエリデータを示し、図13中Cは、対応参照データからrimaxの範囲を示す。また、図13中Dは、Uが示す近傍範囲を示す。情報処理装置10aは、登録データと各参照ポイントとの内積値に基づいて枝刈りを実行した場合には、参照ポイントのベクトルに直交するような直線で囲まれる領域となる。このため、情報処理装置10aは、近傍候補を図13中Eで示す網掛けの範囲に含まれる登録データに限定することができる。ここで、近傍候補に対する枝刈りを効率良く行うためには、予め適切な位置に参照ポイントを設定する必要があるが、インデックスを作成する際にどのようなクエリデータが入力されるかを予測することは困難である。しかし、情報処理装置10aが生体認証を行うためのクエリデータと類似する登録データの近傍検索を行う場合には、登録対象データと類似する分布のデータがクエリデータとして入力されると考えることができる。このため、登録対象データの分布を用いて、効果的に枝刈りをおこなうための参照ポイントを定めることができる。例えば、情報処理装置10aは、距離に基づいて枝刈りされる登録データの数を増やすためには、以下の式16を最大化させる参照ポイントの位置を算出し、算出した位置に参照ポイントを設定すればよい。また、情報処理装置10aは、内積値に基づいて枝刈りされる登録データの数を増やすためには、以下の式17を最大化させる参照ポイントの位置を算出し、算出した位置に参照ポイントを設定すればよい。なお、[非特許文献1]は、式16の式を最大化する参照ポイントを登録データから選択する方法を提案している。また、式17についても、参照ポイントをαだけ回転させた場合を考慮して、枝刈りされる登録データの数が増えるように参照ポイントを設定しても良い。また、情報処理装置10aは、登録データのうち、式16と式17、または、式16と式17との重み付和を最大化する登録データを参照ポイントとして選択してもよい。また、情報処理装置10aは、登録データのうち、式16と式17、または、式16と式17との重み付和を最大化させる位置に参照ポイントを設定しても良い。[情報処理装置10aの処理の流れ]次に、図14を用いて、情報処理装置10aが新たなデータを登録する処理の流れの一例について説明する。図14は、実施例2に係る登録処理の流れの一例を説明するためのフローチャートである。図14に示す例では、情報処理装置10aは、データベース21aに登録するデータを受信したことをトリガとして、処理を開始する。まず、情報処理装置10aは、登録対象となるデータをデータベース21aに登録するステップS301。また、情報処理装置10aは、新たな登録データの対応参照ポイントを算出するステップS302。次に情報処理装置10aは、新たな登録データのキー値を算出し、新たな登録データと各参照ポイントとの距離と、新たな登録データの各参照ポイントとの内積値とをキー値と対応付けてインデックスに登録するステップS303。次に、情報処理装置10aは、対応参照ポイントと新たな登録データとの距離が対応参照ポイントと対応付けられた距離の最大値よりも大きいか否かを判別するステップS304。そして、情報処理装置10aは、対応参照ポイントと新たな登録データとの距離が対応参照ポイントと対応付けられた距離の最大値をよりも大きいと判別した場合にはステップS304肯定、以下の処理を実行する。すなわち、情報処理装置10aは、対応参照ポイントと対応付けられた距離の最大値を更新するステップS305。その後、情報処理装置10aは、処理を終了する。一方、情報処理装置10aは、対応参照ポイントと新たな登録データとの距離が対応参照ポイントと対応付けられた距離の最大値をよりも小さいと判別した場合にはステップS304否定、そのまま処理を終了する。次に、図15を用いて、情報処理装置10aが入力されたクエリデータの近傍データを検索する処理の流れの一例について説明する。図15は、実施例2に係る検索処理の流れの一例を説明するためのフローチャートである。図15に示す例では、情報処理装置10aは、クエリデータおよび近傍範囲を示す情報を取得したことをトリガとして、検索処理を開始する。まず、情報処理装置10aは、クエリデータと近傍範囲を示す情報とを取得するステップS401。このような場合には、情報処理装置10aは、取得したクエリデータの近傍候補となる登録データと対応付けられた対応参照ポイントと、近傍候補となる登録データのキー値の範囲とを算出するステップS402。次に、情報処理装置10aは、算出した範囲のキー値を用いて、近傍候補となる登録データをインデックスから検索するステップS403。次に、情報処理装置10aは、検索したインデックスから取得される距離と内積値とを用いて近傍候補の枝刈りを実行するステップS404。つまり、情報処理装置10aは、インデックスから取得された登録データと各参照ポイントとの距離を用いて、近傍候補の枝刈りを実行する。これとともに、情報処理装置10aは、インデックスから取得された登録データと各参照ポイントとの内積値を用いて、近傍候補の枝刈りを実行する。次に、情報処理装置10aは、枝刈りを行った近傍候補に含まれる各登録データについて、クエリデータとの距離を算出し、近傍データを確定するステップS405。そして、情報処理装置10aは、確定した近傍データのリストを認証サーバ3に出力しステップS406、処理を終了する。[実施例2の効果]上述したように、情報処理装置10aは、複数の参照ポイントと登録データとの距離と、複数の参照ポイントと登録データとの内積値とをインデックスとしてあらかじめ記憶する。そして、情報処理装置10aは、インデックスを用いて検索した近傍候補の登録データから、インデックスとして予め記憶した複数の距離と複数の内積値とを用いた枝刈りを行う。具体的には、情報処理装置10aは、距離を用いた枝刈りを行う場合には、各参照ポイントについて、クエリデータから参照ポイントまでの距離と登録データから参照ポイントまでの距離との差が所定の近傍範囲内に収まるか否かを判別する。そして、情報処理装置10aは、クエリデータから参照ポイントまでの距離と登録データから参照ポイントまでの距離との差が所定の近傍範囲内に収まらないと判別した場合には、この登録データを近傍候補から除外する。また、情報処理装置10aは、内積値を用いた枝刈りを行う場合には、各参照ポイントについて、登録データと参照ポイントとの内積値からクエリデータと参照ポイントとの内積値を減じた値が所定の値以内に収まるか否かを判別する。ここで、所定の範囲内とは、近傍範囲と同じ大きさを有する任意のベクトルと参照ポイントとの内積値である。そして、情報処理装置10aは、各参照ポイントについて、登録データと参照ポイントとの内積値からクエリデータと参照ポイントとの内積値を減じた値が所定の値よりも大きいと判別した場合には、この登録データを近傍範囲から除外する。このため、情報処理装置10aは、距離を用いた枝刈りと内積値を用いた枝刈りとを併用した場合には、距離のみを用いた枝刈りよりも多くの登録データを近傍候補から除外することができる。つまり、情報処理装置10aは、従来の距離による三角不等式だけを値要する場合と比較して、より多くの登録データを近傍候補から除外する結果、クエリデータとの距離を算出する回数を削減し、より効率的に近傍検索を行う事ができる。また、情報処理装置10aは、近傍候補から除外される登録データの数が最大となるように、原点を中心として参照データを回転させる。そして、情報処理装置10aは、回転させた参照データを用いて、内積値を用いた枝刈りを実行する。このため、情報処理装置10aは、より多くの登録データを近傍候補から除外することができる。すなわち、情報処理装置10aは、内積値を用いた枝刈りを行った場合には、参照ポイントのベクトルに直交するような直線で囲まれる領域に含まれる登録データを近傍候補から除外する。ここで、原点を中心として参照ポイントを回転させた場合には、参照ポイントのベクトルに直交するような直線で囲まれる領域が移動することとなる。このため、情報処理装置10aは、もっとも効率的に枝刈りを行う事ができる参照データを用いて、内積値を用いた枝刈りを行う事ができる。実施例3では、参照ポイントと登録データとの距離以外の情報をインデックスとして記憶することによって、近傍候補をさらに効率良く検索する情報処理装置10bについて説明する。つまり、従来の近傍検索を行う技術は、インデックスに複数の参照ポイントと登録データとの距離をすべて保存していた。このため、登録データの数が多い場合には、参照ポイントの数が多い場合には、多くのデータをインデックスに登録する必要があるため、インデックスを記憶するための要する記憶容量が多くなるという問題があった。また、参照ポイントの数が多い場合には、クエリデータの近傍データと対応付けられた参照ポイントを検索するため、クエリデータと参照ポイントとの距離を算出する回数が多くなる。この結果、従来の近傍検索を行う技術では、近傍検索を行う際の計算コストが多くなり、適切な近傍検索を行う事ができないという問題があった。実施例3に開示の技術は、上述した問題に鑑みてなされたものであって、近傍検索を実行する際の計算コストを削減する。図16は、実施例3に係る情報処理装置を説明するための図である。図16に示す例では、情報処理装置10bは、データ登録処理部20b、検索処理部30bを有する。また、データ登録処理部20bは、データベース21b、基準参照ポイント情報記憶部22a、補助参照ポイント情報記憶部22b、インデックス記憶部24b、距離算出部25、インデックス登録部26b、登録対応補助参照ポイント決定部29を有する。また、検索処理部30bは、インデックス検索範囲算出部31、近傍データ確定部33、インデックス検索部32、対応補助参照ポイント決定部36、候補枝刈り部34aを有する。なお、情報処理装置10bが有する各部のうち、実施例1に係る情報処理装置10、および実施例2に係る情報処理装置10aが有する各部と同様の処理を実行するものについては、同一の符号を付し、詳細な説明を省略する。また、以下の説明においては、情報処理装置10bは、各登録データの誤差パラメータを考慮せずに、処理を実行するものとする。また、情報処理装置10bは、実施例1に係る情報処理装置10と同様に、生体データのマッチングを行う情報処理システム1bが有する情報処理装置である。データベース21bは、登録データと、登録データと対応する補助参照ポイントを示す識別子と、登録データと対応する補助参照ポイントとの距離とを対応付けて記憶する。ここで、補助参照ポイントとは、近傍候補の枝刈りを行うために予め設定される参照ポイントである。基準参照ポイント情報記憶部22aは、予め設定される基準参照ポイントを記憶する。ここで、基準参照ポイントとは、実施例1、2に係る参照ポイントと同義である。つまり、基準参照ポイント情報記憶部22aは、実施例1、2に係る参照ポイント情報記憶部22と同様の情報を記憶する。補助参照ポイント情報記憶部22bは、予め設定される補助参照ポイントを記憶する。具体的には、補助参照ポイント情報記憶部22bには、図16中Aに示すように、予め設定された補助参照ポイントの位置または、特徴量ベクトルを示す情報が格納される。インデックス記憶部24bは、登録データと対応基準参照ポイントとの距離に基づく値をキー値として、以下の情報をインデックスとして記憶する。すなわち、インデックス記憶部24bは、登録データと、登録対応補助参照ポイント決定部29によって選択された対応補助参照ポイントの識別子と、登録データと対応補助参照ポイントとの距離とをインデックスとして記憶する。ここで、図17は、実施例3に関するインデックスの一例を説明するための図である。図17に示す例では、インデックス記憶部24bは、実施例1、2に係るインデックス記憶部24、24aと同様の構成を有するインデックスを記憶する。つまり、図17中Aに示すように、登録データと対応基準参照ポイントとの距離に基づくキー値を階層的に有する。また、インデックス記憶部24bは、図16中Bに示すように、登録データと各対応補助参照ポイントの識別子IDと、登録データと各対応補助参照ポイントとの距離とを対応付けたインデックスを記憶する。図16に戻って、距離算出部25は、実施例1、2に係る距離算出部と同様に、データベース21bに登録する登録対象データを受信した場合には、登録対象データと基準参照ポイント情報記憶部22aに記憶された各基準参照ポイントとの距離を算出する。登録対応補助参照ポイント決定部29は、登録対象データと対応する複数の補助参照ポイントを選択し、選択した複数の補助参照ポイントをインデックス登録部26に通知する。具体的には、登録対応補助参照ポイント決定部29は、図16中Bに示すように、登録データを受信した場合には、補助参照ポイント情報記憶部22bに記憶された補助参照ポイントから受信した登録データと対応する複数の補助参照ポイントを選択する。そして、登録対応補助参照ポイント決定部29は、選択した複数の補助参照ポイントを示す識別子をインデックス登録部26に通知する。また、登録対応補助参照ポイント決定部29は、選択した各補助参照ポイントと登録対象データとの距離を算出し、算出した距離をインデックス登録部26bに通知する。なお、この処理は、登録対応補助参照ポイント決定部29が実行するのではなく、距離算出部25に選択した補助参照ポイントの位置を通知し、登録データと通知した補助参照ポイントとの距離を算出されることによって実現しても良い。ここで、登録対応補助参照ポイント決定部29は、登録データに近いと考えられる複数の補助参照ポイントを対応する補助参照ポイントとして選択する。換言すると、登録対応補助参照ポイント決定部29は、登録データに近い複数の補助参照ポイントを近似的な近傍検索によって選択する。この補助参照ポイントの選択は厳密な近傍検索が要求されるわけではなく、近似的な近傍検索を利用することで、補助参照ポイントの選択を高速で行う事ができる。以下、補助参照ポイントを選択する処理の例として、基準参照ポイントを用いたインデックスを利用して補助参照ポイントを選択する例と、局所性鋭敏型ハッシュLocalitySensitiveHashingLSHを利用して補助参照ポイントを選択する例とを説明する。まず、登録対応補助参照ポイント決定部29が、基準参照ポイントを用いたインデックスを利用した補助参照ポイントを選択する例について説明する。登録対応補助参照ポイント決定部29は、予め、各補助参照ポイントについて、最も近くに存在する基準参照ポイントを選択する。そして、登録対応補助参照ポイント決定部29は、選択した基準参照ポイントと補助参照ポイントとの距離に基づく値をキー値とし、補助参照ポイントを示す識別子を記憶する補助参照ポイントインデックスを作成しておく。そして、登録対応補助参照ポイント決定部29は、登録対象データを受信した場合には、受信した登録対象データと基準参照ポイントとの距離を算出する。そして、登録対応補助参照ポイント決定部29は、補助参照ポイントと基準参照ポイントとの距離と、算出した登録対象データと基準参照ポイントとの距離との差が所定の範囲内に収まる補助参照ポイントを予め作成した補助参照ポイントインデックスを用いて選択する。その後、登録対応補助参照ポイント決定部29は、補助参照ポイントインデックスから選択した補助参照ポイントの識別子を取得し、取得した識別子をインデックス登録部26aに通知する。なお、登録対応補助参照ポイント決定部29は、補助参照ポイントインデックスを補助参照ポイント情報記憶部22bに格納することとしてもよく、また、補助参照ポイントインデックスを後述する対応補助参照ポイント決定部36に通知することとしてもよい。次に、登録対応補助参照ポイント決定部29が、LSHを利用して補助参照ポイントを選択する例について説明する。ここで、LSHを利用して補助参照ポイント選択する処理とは、ハッシュ関数を用いて、近似的な近傍検索を行う処理である。このようなLSHを利用した近傍検索には、以下の非特許文献3に記載された方法を初めとして、様々なバリエーションがある。なお、本実施例では、距離関数にユークリッド距離を考えるが、利用する距離関数に対応したLSHであれば特に限定はしない。非特許文献3MDatarNImmorlicaPIndykandVSMirrokniLocalitySensitiveHashingSchemeBasedonpStableDistributionsProceedingsofthetwentiethannualsymposiumonComputationalgeometrypp253262例えば、登録対応補助参照ポイント決定部29は、一様乱数を項に含むハッシュ関数を用いて、補助参照ポイントのハッシュ値を予め算出し、算出した補助参照ポイントのハッシュ値を格納したハッシュテーブルを作成する。そして、登録対応補助参照ポイント決定部29は、ハッシュテーブルを作成した際に用いたハッシュ関数と同一のハッシュ関数を用いて登録データのハッシュ値を複数作成する。そして、登録対応補助参照ポイント決定部29は、ハッシュテーブルを参照し、登録データから作成した複数のハッシュ値と同じハッシュ値が算出された補助参照ポイントを複数選択する。そして、登録対応補助参照ポイント決定部29は、選択した補助参照ポイントを示す識別子をインデックス登録部26に通知する。なお、登録対応補助参照ポイント決定部29は、作成したハッシュテーブルを対応補助参照ポイント決定部36に送信することとしてもよく、また、ハッシュテーブルを補助参照ポイント情報記憶部22bに格納することとしてもよい。インデックス登録部26bは、距離算出部25が算出した登録対象データと対応基準参照ポイントとの距離を取得する。また、インデックス登録部26bは、登録対応補助参照ポイント決定部29が選択した補助参照ポイント、つまり各対応補助参照ポイントの識別子と、登録データと各補助参照ポイントとの距離とを取得する。そして、インデックス登録部26bは、距離算出部25から取得した距離からキー値を算出し、算出したキー値と対応付けて、登録対応補助参照ポイント決定部29から通知された各補助参照ポイントの識別子および距離とをインデックスに追加する。インデックス検索範囲算出部31は、実施例1、2と同様に、図16中C、Dに示すクエリデータと近傍範囲を示す情報とを取得した場合には、インデックス検索を行うキー値の範囲を算出する。そして、インデックス検索範囲算出部31は、図16中Eに示すように、算出したキー値の範囲をインデックス検索部32に通知する。インデックス検索部32は、実施例1、2と同様に、インデックス検索範囲算出部31からキー値の範囲を取得した場合には、インデックス記憶部24bが記憶するインデックスから、取得したキー値の範囲を検索する。そして、インデックス検索部32は、検索された範囲のキー値と対応付けて記憶された登録データと、各対応補助参照ポイントの識別子と、登録データと各対応補助参照ポイントとの距離とを取得する。その後、インデックス検索部32は、取得した各情報を候補枝刈り部34aに送信する。対応補助参照ポイント決定部36は、クエリデータの近傍にある補助参照ポイントを近似的に検索する。そして、対応補助参照ポイント決定部36は、検索した補助参照ポイントを候補枝刈り部34aに送信する。ここで、対応補助参照ポイント決定部36は、登録対応補助参照ポイント決定部29と同様に、近似的な近傍検索を用いて、クエリデータに近いと考えられる補助参照ポイントを選択する。例えば、対応補助参照ポイント決定部36は、クエリデータと各基準参照ポイントとの距離を算出し、近傍候補となる登録データの対応基準参照ポイントを判定する。そして、対応補助参照ポイント決定部36は、対応基準参照ポイントとクエリデータとの距離をキー値として、登録対応補助参照ポイント決定部29が作成した補助参照ポイントインデックスを検索する。そして、対応補助参照ポイント決定部36は、図16中Fに示すように、補助参照ポイントインデックスを検索し結果取得された補助参照ポイントの識別子を候補枝刈り部34aに通知する。ここで、対応補助参照ポイント決定部36は、LSHを利用した補助参照ポイントを選択しても良い。このような場合には、対応補助参照ポイント決定部36は、登録対応補助参照ポイント29と同様に、クエリデータのハッシュ値を算出する。そして、対応補助参照ポイント決定部36は、算出したハッシュ値と同じハッシュ値が算出された補助参照ポイントを登録対応補助参照ポイント決定部29が作成したハッシュテーブルから選択する。なお、このような場合には、対応補助参照ポイント決定部36は、ハッシュテーブルを登録対応補助参照ポイント決定部29から受信することとしてもよいし、補助参照ポイント情報記憶部22b等に格納されたハッシュテーブルを参照することとしてもよい。候補枝刈り部34aは、インデックス検索部32から近傍候補となる登録データと各対応補助参照ポイントの識別子を取得する。また、候補枝刈り部34aは、対応補助参照ポイント決定部36が選択した補助参照ポイントの識別子を取得する。このような場合には、候補枝刈り部34aは、インデックス検索部32から取得した対応補助参照ポイントの識別子と対応補助参照ポイント決定部36が選択した補助参照ポイントのうち、重複する補助参照ポイントを判別する。そして、候補枝刈り部34aは、判別した補助参照ポイントとクエリデータとの距離と、判別した補助参照ポイントと登録データとの距離との差が、所定の範囲内に収まるか否かを判別する。その後、候補枝刈り部34aは、各距離の差が所定の範囲内に収まらないと判別した場合には、登録データを近傍候補から除外する。その後、候補枝刈り部34aは、図16中Gに示すように、近傍候補から除外されなかった登録データを近傍データ確定部33へ送信する。近傍データ確定部33は、候補枝刈り部34aから受信した近傍候補について、クエリデータとの距離を算出し、近傍データを確定する。そして、近傍データ確定部33は、図16中Hに示すように、確定した近傍データのリストを、認証サーバ3に送信する。このように、情報処理装置10bは、各登録データの近傍と考えられる複数の補助参照ポイントとの距離をインデックスに記憶し、検索処理時にクエリデータに近いと考えられる補助参照ポイントだけを用いて近傍候補の枝刈りを行う。このため、情報処理装置10bは、全参照ポイントとの距離を保存する場合に比べて、メモリ使用量を削減することができる。例えば、全参照ポイントとの距離を保存する方法で保存が必要な距離情報の数は、参照ポイントの数×登録データの数である。一方、実施例3で情報処理装置10bが記憶する距離情報の数は、登録データの数登録データの数×登録データの近傍補助参照ポイントの数となる。ここで、近傍補助参照ポイントの数は、通常、登録データ数に比べて小さいので、距離情報の総数も全参照ポイントとの距離を保存する方法よりも少なくなる。このため、情報処理装置10bは、メモリ使用量を削減する。また、例えば、全参照ポイントとの距離を保存する方法で検索時に必要な参照ポイントとの距離計算回数は、参照ポイントの数である。一方、実施例3で情報処理装置10bが検索時に必要な参照ポイントとの距離計算回数は、基準参照ポイントの数クエリデータの近傍補助参照ポイント数となる。この距離計算回数は、基準参照ポイントと補助参照ポイントを合わせたものよりも小さい。このため、情報処理装置10bは、近傍検索を実行する際の計算コストを削減し、効率的な近傍検索を行うことができる。例えば、登録対応補助参照ポイント決定部29、対応補助参照ポイント決定部36は、電子回路である。ここで、電子回路の例として、ASICApplicationSpecificIntegratedCircuitやFPGAFieldProgrammableGateArrayなどの集積回路、またはCPUCentralProcessingUnitやMPUMicroProcessingUnitなどを適用する。次に数式を用いて、情報処理装置10bが登録対象データpを登録する処理の具体例について説明する。なお、以下の説明においては、実施例1、2と同様の記号を用いるものとする。また、各補助参照ポイントをs1~sNとし、補助参照ポイントの数をNとする。また、説明を簡単にするために、各登録データの誤差パラメータについては、考慮しないものとする。以下の説明では、登録対象データに近いと考えられる補助参照ポイントのID集合をXpと定義する。上述したように、情報処理装置10bがXpを求める処理としては、基準参照ポイントを用いたインデックスを利用する方法とLSHを利用する方法とがある。このため、以下の説明においては、先に基準参照ポイントを用いたインデックスを利用する方法を説明し、次にLSHを利用した方法を説明する。まず、準参照ポイントを用いたインデックスを利用する方法について説明する。まず、情報処理装置10bは、予め各補助参照ポイントについて、最も近くにある基準参照ポイントojを選択する。そして、以下の式18を用いて、補助参照ポイントインデックスのキー値KsSiを生成し、補助参照ポイントインデックスを作成する。なお、式18中のCは定数である。このため、基準参照ポイントojに対応する補助参照ポイントのキー値は[j×C、j1×Cの範囲に収まることとなる。その後、情報処理装置10bは、作成した補助参照ポイントインデックスを用いて、登録対象データpに近いと考えられる補助参照ポイントをNp個検索し、対応補助参照ポイントのIDの集合Xpを得る。つまり、情報処理装置10bは、基準参照ポイントoii=1~Mと登録対象データpとの距離doipを算出する。そして、情報処理装置10bは、以下の式19を満たすdoipを選択する。ここで、式19中のuimaxとは、基準参照ポイントoiと対応付けられた補助参照ポイントと基準参照ポイントoiとの距離のうち、最大の距離を示す。また、tとは、補助参照ポイントを検索する範囲を示す。そして、情報処理装置10bは、選択したdoipに基づいて[doipi×C-Tdoipi×CT]の範囲のキー値と対応付けて記憶された補助参照ポイントを補助参照ポイントインデックスから検索する。ここで、図18中のtを操作することで、検索される補助参照ポイントの個数が変化する。このため、情報相処理装置10bは、検索された補助参照ポイントの数が検索結果の上限であるNp個に達しない場合には、tを大きくすることで、さらに補助参照ポイントを検索することとしてもよい。また、情報処理装置10bは、Np個よりも多くの補助参照ポイントを検索した場合には、検索された補助参照ポイントからNp個の補助参照ポイントをランダムに選択し、選択した補助参照ポイントをXpとすることとしてもよい。また、検索された補助参照ポイントと登録対象データとの距離を計算し、厳密な近傍となる補助参照ポイントを取得してもよい。次に、LSHを利用してがXpを求める処理について説明する。例えば、情報処理装置10bは、以下の式20および式21を用いて、登録対象データpのハッシュ値gjpをL個算出する。ここで、式21中のaは、各座標地が平均0分散1の正規分布に従うランダムベクトルであり、zは範囲が[0、w]となる一様乱数である。情報処理装置10bは、ハッシュ値gjpを算出した場合には、算出したハッシュ値gjpと同一のハッシュ値を有する補助参照ポイントをハッシュテーブルから検索する。ここで、ハッシュテーブルには、式19および式20と同様の式を用いて算出された補助参照ポイントのハッシュ値gjsii=1~M、j=1~Lが格納されているものとする。情報処理装置10bは、このような近似近傍検索によって登録対象データpの近傍となる補助参照ポイントを検索した場合には、高い確率で登録対象データpの近傍となる補助参照ポイントを選択することができる。なお、情報処理装置10bは、LSHを利用した場合には、ハッシュ値が一致するデータを探索するだけなので、距離計算を行う場合に比べて高速に実行することができる。次に、登録対象データをインデックスに登録する処理について説明する。例えば、情報処理装置10bは、登録対象データpと各基準参照ポイントoii=1~Mとの距離doi、pを算出する。そして、情報処理装置10bは、doi、pが最も小さい基準参照ポイントを対応基準参照ポイントojとして選択する。次に、情報処理装置10bは、以下の式22を用いて、登録対象データpのキー値Kpを算出する。次に、情報処理装置10bは、算出したKpをキーとして、登録対象データをインデックスに追加する。以下の説明では、インデックスに登録されたデータの集合をIdataと記載する。次に、情報処理装置10bは、補助参照データインデックス又はLSHを用いて選択した集合Xpに含まれる補助参照ポイントと登録対象データpとの距離{dsip|i∈Xp}をpとともにインデックスに登録する。また、情報処理装置10bは、基準参照ポイントojに対応する登録データのうち基準参照ポイントojとの距離が最大のものの距離をrjmaxとしてインデックスに保存しておく。次に、図18、図19および数式を用いて、情報処理装置10bがクエリデータの近傍データを検索する処理について説明する。まず、情報処理装置10bは、各基準参照ポイントoii=1~Mとクエリデータqとの距離doiqを算出し、oiと対応付けられた登録データが近傍候補になるかを以下の式23を用いて判別する。次に、情報処理装置10bは、基準参照ポイントoiについてキーの値が[doipi×C-Udoipi×CU]の範囲となる登録データをインデックスIdataから検索し、検索した登録データを近傍候補の集合Yとする。このような集合Yは、図18に示す網掛けをした丸印となる。ここで、図18は、実施例3に係る補助参照ポイント選択処理の一例を説明するための図である。図18中Aは基準参照ポイントを示し、図18中Bはクエリデータを示し、図18中Cは、近傍範囲Uを示す。また、図18中網がけした丸印は、近傍候補の集合Yに含まれる登録データであり、Xマークは補助参照ポイントを示す。次に情報処理装置10bは、クエリデータqに近いと考えられる補助参照ポイントの集合Xqを検索する。例えば、情報処理装置10bは、基準参照ポイントを用いたインデックスを利用する場合には、各基準参照ポイントoii=1~Mとクエリデータqの距離doiqを算出し、oiにと対応付けられた補助参照ポイントがqの近傍候補になるかを以下の式24を用いて判別する。ここで、式23中uimaxは、補助参照ポイントインデックスIsubにおいて参照ポイントoiと対応付けられた補助参照ポイントのうち、参照ポイントoiとの距離が最大の補助参照ポイントと参照ポイントoiとの距離である。なお、tは補助参照ポイントについての近傍範囲を示す値であるがt=Uとしてもよい。次に、情報処理装置10bは、補助参照ポイントインデックスIsubからキーの値が[doiqi×C-tdoiqi×Ct]の範囲となる補助参照ポイントを最大Nq個検索する。そして、情報処理装置10bは、検索した補助参照ポイントの集合をXqとする。このような場合には、情報処理装置10bは、図18中のXマークで示す補助参照ポイント、つまり、対応基準参照ポイントを中心としたドーナツ状の範囲に含まれる補助参照ポイントを検索することとなる。なお、情報処理装置10bは、Nq個よりも多くの補助参照ポイントを検索した場合には、検索された補助参照ポイントからNq個の補助参照ポイントをランダムに選択し、選択した補助参照ポイントをNq個とすることとしてもよい。一方、情報処理装置10bは、LSHを用いて補助参照ポイントを検索する場合には、クエリデータqを用いてハッシュ値gjqをL個j=1~L算出する。そして、情報処理装置10bは、算出したハッシュ値gjqと同一のハッシュ値を有する補助参照ポイントをハッシュテーブルから最大Nq個選択し、選択した補助参照ポイントの集合をXqとする。次に、情報処理装置10bが補助参照ポイントを用いて枝刈りを行う処理の一例を説明する。まず、情報処理装置10bは、補助参照ポイント{si|i∈Xq}とクエリデータqとの距離dsiqを算出する。また、情報処理装置10bは、近傍候補の登録データから{si|i∈Xq}との距離が所定の範囲内となる登録データについて、以下の式25を満たすか否かを判別し、満たす場合には、近傍候補から除外する。ここで、図19は、実施例3に係る補助参照ポイントによる枝刈りの一例を説明するための図である。図19に示すAは、対応基準参照ポイント、図19中Bは、クエリデータ、図19中Cは、近傍範囲を示す。情報処理装置10bは、式24を満たす登録データを近傍範囲から除外した場合には、図19中網掛けをした丸印で示す登録データのみを近傍候補とする。このように、情報処理装置10bは、検索された補助参照ポイントと近傍候補として検索された登録データの距離がデータ登録時に保存されていたとすると、図19のように近傍候補のほとんどのデータが式を満たすと容易に判別することができる。このため、情報処理装置10bは、近傍候補の枝刈りを容易に行う事ができる。[情報処理装置10bが実行する処理の流れ]次に、図20を用いて、情報処理装置10bが新たなデータを登録する処理の流れの一例について説明する。図20は、実施例3に係る登録処理の流れの一例を説明するためのフローチャートである。図14に示す例では、情報処理装置10bは、データベース21bに登録するデータを受信したことをトリガとして、処理を開始する。まず、情報処理装置10bは、登録対象データをデータベース21bに登録するステップS501。また、情報処理装置10bは、新たな登録データと対応する補助参照ポイントを算出するステップS502。次に情報処理装置10bは、対応基準参照ポイントを選択するステップS503。次に、情報処理装置10bは、登録対象データのキー値を算出し、インデックスに登録データと対応する補助参照ポイントのIDと補助参照ポイントとの距離とを登録するステップS504。また、情報処理装置10bは、対応基準参照ポイントと新たな登録データとの距離が対応基準参照ポイントと対応付けられた距離の最大値よりも大きいか否かを判別するステップS505。そして、情報処理装置10bは、対応基準参照ポイントと新たな登録データとの距離が対応基準参照ポイントと対応付けられた距離の最大値をよりも大きいと判別した場合にはステップS505肯定、以下の処理を実行する。すなわち、情報処理装置10bは、対応基準参照ポイントと対応付けられた距離の最大値を更新するステップS506。その後、情報処理装置10bは、処理を終了する。一方、情報処理装置10bは、対応基準参照ポイントと新たな登録データとの距離が対応基準参照ポイントと対応付けられた距離の最大値をよりも小さいと判別した場合にはステップS505否定、そのまま処理を終了する。次に、図21を用いて、情報処理装置10bが入力されたクエリデータの近傍データを検索する処理の流れの一例について説明する。図21は、実施例3に係る検索処理の流れの一例を説明するためのフローチャートである。図21に示す例では、情報処理装置10bは、クエリデータおよび近傍範囲を示す情報を取得したことをトリガとして、検索処理を開始する。まず、情報処理装置10bは、クエリデータと近傍範囲を示す情報とを取得するステップS601。このような場合には、情報処理装置10bは、取得したクエリデータの近傍候補となる登録データと対応付けられた対応基準参照ポイントと、近傍候補となる登録データのキー値の範囲とを算出するステップS602。次に、情報処理装置10bは、算出した範囲のキー値を用いて、近傍候補となる登録データをインデックスから検索するステップS603。次に、情報処理装置10bは、クエリデータの近傍となる補助参照ポイントを検索するステップS604。そして、情報処理装置10bは、インデックスから取得される補助参照ポイントと検索した補助参照ポイントとを用いて、近傍候補の枝刈りを実行するステップS605。次に、情報処理装置10bは、枝刈りをした近傍候補に含まれる各登録データについてクエリデータとの距離を算出し、近傍データの確定を行うステップS606。その後、情報処理装置10bは、確定した近傍データのリストを認証サーバ3に出力しステップS607、処理を終了する。[実施例3の効果]上述したように、情報処理装置10bは、近似的な近傍検索を用いて、登録データの近傍にある補助参照ポイントを検索する。そして、情報処理装置10bは、登録データと、検索した補助参照ポイントと、検索した補助参照ポイントと登録データとの距離とを対応付けてインデックスに登録する。また、情報処理装置10bは、クエリデータの近傍候補となる登録データを検索し、検索された登録データと対応付けられた補助参照ポイントと、クエリデータの近傍となる補助参照ポイントとを用いて、近傍候補の枝刈りを行う。つまり、情報処理装置10bは、各登録データの近傍と考えられる複数の補助参照ポイントとの距離をインデックスに記憶し、検索処理時にクエリデータに近いと考えられる補助参照ポイントだけを用いて近傍候補の枝刈りを行う。このため、情報処理装置10bは、全参照ポイントとの距離を保存する場合に比べて、メモリ使用量を削減することができる。また、情報処理装置10bは、近似的な近傍検索を利用して、クエリデータに近い補助参照ポイントを検索するので、高速にクエリデータに近い補助参照ポイントを取得することができる。また、情報処理装置10bは、登録データに近い補助参照ポイントとクエリデータに近い補助参照ポイント、つまり、適切な参照ポイントを選択することで、効率的な近傍候補の枝刈りを行う事ができる。また、情報処理装置10bは、補助参照ポイントの選択にだけ近似的な近傍検索を使用し、近傍データの確定を行う場合には、クエリデータと登録データとの距離を算出するので、最終的な近傍検索結果の厳密性を保証する。これまで本発明の実施例について説明したが実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例4として本発明に含まれる他の実施例を説明する。1情報処理装置10について上述した情報処理装置10は、各登録データごとに誤差パラメータを対応付けてデータベース21に記憶するとともに、インデックスにも登録データと誤差パラメータとを対応付けて登録していた。しかし、実施例はこれに限定されるものではない。すなわち、情報処理装置10は、各登録データごとに対応付けた誤差パラメータを考慮して近傍検索を行った場合には、バラつきが大きな登録データを適切に検索することができる。このため、情報処理装置10は、インデックスを用いた近傍候補の選択を行わずに、誤差パラメータを考慮した線形検索を行うことによってもバラつきが大きな登録データを適切に検索することができる。2情報処理システムについて上述した実施例1~3においては、生体認証を行う認証システムが有する情報処理装置10~10bについて説明した。しかし、実施例はこれに限定されるものではなく、近傍検索が必要となる任意のシステムに対して、情報処理装置10~10bを適用することができる。3枝刈りについて上述した情報処理装置10a、10bは、インデックスに登録された情報を用いて、枝刈りを行っていた。しかし、実施例はこれに限定されるものではなく、他にも一般的に用いられる枝刈りの手法を併用することで、さらに効率的な近傍検索を行うこととしてもよい。4対応参照ポイントの回転について上述した情報処理装置10aは、枝刈りする登録データの数が最も多くなるように原点を中心として対応参照ポイントの回転させていた。しかし、この処理は必須の処理ではないため、行わないこととしてもよい。5登録データについて情報処理装置10は、生体データを登録データとしてデータベース21に記憶するが、生体データは、データを登録してから年月が経過すると、生体情報に変化が生じ、クエリデータとして入力される生体データとの差が大きくなるとも考えられる。このため、情報処理装置10は、登録データが登録されてからの年月に応じて、各登録データの誤差パラメータを補正することとしてもよい。