(57)【特許請求の範囲】
【請求項１】
検索対象である登録データと、当該登録データの誤差を示す誤差情報とを対応付けて記憶する記憶部と、
検索要求に係るクエリデータと前記登録データとの距離から前記誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データを前記記憶部から検索する検索部と、
を有することを特徴とする情報処理装置。
【請求項２】
前記記憶部は、さらに、予め定められた参照ポイントと各登録データとの距離を記憶し
前記検索部は、
前記記憶部が記憶した参照ポイントと各登録データとの距離を用いて、前記参照ポイントからの距離が、前記クエリデータと前記参照ポイントとの距離から前記近傍範囲に応じた距離と前記誤差情報の最大値とを減じた値よりも大きく、前記クエリデータと前記参照ポイントとの距離から前記近傍範囲に応じた距離と前記誤差情報の最大値とを加算した値よりも小さい登録データを検索するインデックス検索部と、
前記インデックス検索部によって検索された登録データのうち、前記クエリデータとの距離から前記誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部と、
を有することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記記憶部は、前記登録データを登録する際に入力される複数個のデータから得られる特徴量の平均、又は、前記複数個のデータから得られる特徴量の分散、又は、前記登録データを取得する装置の精度、又は、前記登録データを取得する装置の設置状況から推定される生体データの質のいずれかを用いて算出される前記誤差情報を記憶することを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
検索対象である登録データともに、予め定められた参照ポイントと各登録データとの距離と、前記参照ポイントと各登録データとの内積値を記憶する記憶部と、
前記記憶部が記憶した参照ポイントと各登録データとの距離を用いて、前記参照ポイントからの距離が、検索要求に係るクエリデータと前記参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと前記参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索する近傍候補検索部と、
前記近傍候補検索部によって検索された登録データのうち、前記クエリデータと前記参照ポイントとの距離と、前記登録データと前記参照ポイントとの距離との差が所定の近傍範囲内にある登録データを抽出する第１枝刈部と、
前記第１枝刈部によって抽出された登録データのうち、前記記憶部に記憶された内積値が、前記参照ポイントと前記クエリデータの近傍範囲となる任意のベクトルとの内積値の範囲内にある登録データを抽出する第２枝刈部と、
前記第２枝刈り部によって抽出された登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部と
を有することを特徴とする情報処理装置。
【請求項５】
前記第２枝刈り部は、前記第１枝刈り部によって抽出された登録データのうち、前記記憶部に記憶された内積値が、前記参照ポイントを前記クエリデータと前記登録データとを含む平面に対して平行に回転させた参照ポイントと前記クエリデータの近傍範囲となる任意のベクトルとの内積値の範囲内にある登録データを抽出することを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記記憶部に記憶された登録データのうち、任意の２つの登録データからの距離の差が最大となる位置に前記参照ポイントを設定することを特徴とする請求項４または５に記載の情報処理装置。
【請求項７】
前記記憶部に記憶された登録データのうち、任意の２つの登録データからの内積の差が最大となる位置に前記参照ポイントを設定することを特徴とする請求項４または５に記載の情報処理装置。
【請求項８】
予め定められた複数の基準参照ポイントのうち、検索対象である登録データに最も近い基準参照ポイントを選択する第１選択部と、
予め定められた複数の補助参照ポイントから、前記登録データの近傍に位置する補助参照ポイントを選択する第２選択部と、
前記登録データと、該登録データと前記第１選択部によって選択された基準参照ポイントとの距離と、該登録データと前記第２選択部によって選択された補助参照ポイントとの距離とを記憶する記憶部と、
検索要求に係るクエリデータの近傍に位置する補助参照ポイントを選択する第３選択部と、
前記記憶部が記憶した前記登録データと前記基準参照ポイントとの距離を用いて、検索要求に係るクエリデータと該基準参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと該基準参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索する近傍候補検索部と、
前記記憶部が記憶した登録データと前記第２選択部によって選択された補助参照ポイントとの距離を用いて、前記近傍候補検索部によって検索された登録データのうち、前記第２選択部および前記第３選択部が選択した補助参照ポイントとクエリデータとの距離と、前記第２選択部および前記第３選択部が選択した補助参照ポイントと登録データとの距離との差が所定の近傍範囲内にある登録データを抽出する枝刈り部と
前記枝刈り部によって抽出された登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部と
を有することを特徴とする情報処理装置。
【請求項９】
前記記憶部は、さらに、前記補助参照ポイントごとに当該補助参照ポイントと前記基準参照ポイントとの距離を記憶し
前記第２選択部は、前記記憶部が記憶した前記補助参照ポイントと前記基準参照ポイントとの距離を用いて、前記基準参照ポイントからの距離が、前記登録データと前記基準参照ポイントとの距離から前記近傍範囲に応じた距離を減じた値よりも大きく、前記登録データと前記参基準照ポイントとの距離から前記近傍範囲に応じた距離を加算した値よりも小さい補助参照ポイントを選択し、
前記第３選択部は、前記記憶部が記憶した該登録データと前記第１選択部によって選択された基準参照ポイントとの距離を用いて、前記基準参照ポイントからの距離が、前記クエリデータと前記基準参照ポイントとの距離から前記近傍範囲に応じた距離を減じた値よりも大きく、前記クエリデータと前記基準参照ポイントとの距離から前記近傍範囲に応じた距離を加算した値よりも小さい登録データを選択する
ことを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
前記記憶部は、さらに、各補助参照ポイントのハッシュ値を記憶し、
前記第２選択部は、前記記憶部が記憶する各補助参照ポイントのハッシュ値を用いて、前記登録データのハッシュ値と一致するハッシュ値を有する補助参照ポイントを選択し、
前記第３選択部は、前記記憶部が記憶した補助参照ポイントのハッシュ値を用いて、前記クエリデータのハッシュ値と一致するハッシュ値を有する補助参照ポイントを選択する
ことを特徴とする請求項８に記載の情報処理装置。
【請求項１１】
検索要求に係るクエリデータを生成する生成装置と、
前記生成装置が生成したクエリデータを取得した場合には、検索対象である登録データから前記クエリデータに類似する登録データを検索する情報処理装置と、
を有する情報処理システムであって、
前記情報処理装置は、
前記登録データと、当該登録データの誤差を示す誤差情報とを対応付けて記憶する記憶部と、
前記クエリデータと前記登録データとの距離から前記誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データを前記記憶部から検索する検索部と、
を有することを特徴とする情報処理システム。
【請求項１２】
検索要求に係るクエリデータを生成する生成装置と、
前記生成装置が生成したクエリデータを取得した場合には、検索対象である登録データから前記クエリデータに類似する登録データを検索する情報処理装置と、
を有する情報処理システムであって、
前記情報処理装置は、
前記登録データともに、予め定められた参照ポイントと各登録データとの距離と、前記参照ポイントと各登録データとの内積値を記憶する記憶部と、
前記記憶部が記憶した参照ポイントと各登録データとの距離を用いて、前記参照ポイントからの距離が、前記クエリデータと前記参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと前記参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索する近傍候補検索部と、
前記近傍候補検索部によって検索された登録データのうち、前記クエリデータと前記参照ポイントとの距離と、前記登録データと前記参照ポイントとの距離との差が所定の近傍範囲内にある登録データを抽出する第１枝刈部と、
前記第１枝刈部によって抽出された登録データのうち、前記記憶部に記憶された内積値が、前記参照ポイントと前記クエリデータの近傍範囲となる任意のベクトルとの内積値の範囲内にある登録データを抽出する第２枝刈部と、
前記第２枝刈り部によって抽出された登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部と
を有することを特徴とする情報処理システム。
【請求項１３】
検索要求に係るクエリデータを生成する生成装置と、
前記生成装置が生成したクエリデータを取得した場合には、検索対象である登録データから前記クエリデータに類似する登録データを検索する情報処理装置と、
を有する情報処理システムであって、
前記情報処理装置は、
予め定められた複数の基準参照ポイントのうち、前記登録データに最も近い基準参照ポイントを選択する第１選択部と、
予め定められた複数の補助参照ポイントから、前記登録データの近傍に位置する補助参照ポイントを選択する第２選択部と、
前記登録データと、該登録データと前記第１選択部によって選択された基準参照ポイントとの距離と、該登録データと前記第２選択部によって選択された補助参照ポイントとの距離とを記憶する記憶部と、
検索要求に係るクエリデータの近傍に位置する補助参照ポイントを選択する第３選択部と、
前記記憶部が記憶した前記登録データと前記基準参照ポイントとの距離を用いて、検索要求に係るクエリデータと該基準参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと該基準参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索する近傍候補検索部と、
前記記憶部が記憶した登録データと前記第２選択部によって選択された補助参照ポイントとの距離を用いて、前記近傍候補検索部によって検索された登録データのうち、前記第２選択部および前記第３選択部が選択した補助参照ポイントとクエリデータとの距離と、前記第２選択部および前記第３選択部が選択した補助参照ポイントと登録データとの距離との差が所定の近傍範囲内にある登録データを抽出する枝刈り部と
前記枝刈り部によって抽出された登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する近傍データ確定部と
を有することを特徴とする情報処理システム。
【請求項１４】
検索対象である登録データから検索要求に係るクエリデータと類似する登録データを検索する情報処理装置が実行する検索方法であって、
検索対象である登録データと、当該登録データの誤差を示す誤差情報とを対応付けて記憶し
検索要求に係るクエリデータと前記登録データとの距離から前記誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データを検索する
ことを特徴とする検索方法。
【請求項１５】
検索対象である登録データから検索要求に係るクエリデータと類似する登録データを検索する情報処理装置が実行する検索方法であって、
検索対象である登録データともに、予め定められた参照ポイントと各登録データとの距離と、前記参照ポイントと各登録データとの内積値を記憶し、
前記記憶した参照ポイントと各登録データとの距離を用いて、前記参照ポイントからの距離が、検索要求に係るクエリデータと前記参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと前記参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索し、
前記検索した登録データのうち、前記クエリデータと前記参照ポイントとの距離と、前記登録データと前記参照ポイントとの距離との差が所定の近傍範囲内にある登録データを抽出し、
前記抽出した登録データのうち、前記記憶した内積値が、前記参照ポイントと前記クエリデータの近傍範囲となる任意のベクトルとの内積値の範囲内にある登録データを抽出し、
前記抽出した登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する
ことを特徴とする検索方法。
【請求項１６】
予め定められた複数の基準参照ポイントのうち、検索対象である登録データに最も近い基準参照ポイントを選択し、
予め定められた複数の補助参照ポイントから、前記登録データの近傍に位置する補助参照ポイントを選択し、
前記登録データと、該登録データと前記選択した基準参照ポイントとの距離と、該登録データと前記選択した補助参照ポイントとの距離とを記憶し、
検索要求に係るクエリデータの近傍に位置する補助参照ポイントを選択し、
前記記憶した前記登録データと前記基準参照ポイントとの距離を用いて、検索要求に係るクエリデータと該基準参照ポイントとの距離から所定の近傍範囲を示す距離を減じた値よりも大きく、前記クエリデータと該基準参照ポイントとの距離に前記近傍範囲を示す距離を加算した値よりも小さい登録データを検索し、
前記記憶した登録データと前記選択した補助参照ポイントとの距離を用いて、前記検索した登録データのうち、前記選択した補助参照ポイントとクエリデータとの距離と、前記選択した補助参照ポイントと登録データとの距離との差が所定の近傍範囲内にある登録データを抽出し
前記抽出した登録データのうち、前記クエリデータとの距離が所定の近傍範囲内にある登録データを前記クエリデータの近傍データであると確定する
ことを特徴とする検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理システムおよび検索方法に関する。
【背景技術】
【０００２】
従来、データベースに登録された複数のデータから、入力されたクエリデータとの類似度や関連の強さが所定の条件を満たすデータを検索する技術が知られている。
【０００３】
このような技術の一例として、各データ間の類似度や関連の強さを多次元空間における距離で示し、クエリデータとの距離が所定の条件を満たすデータを選択する近傍検索の技術が知られている。例えば、このような近傍検索を実行する情報処理装置は、データベースに登録されたデータと入力されたクエリデータとの距離を算出し、算出した距離が所定の範囲内であるデータをクエリデータの近傍のデータとして検索する。
【０００４】
ここで、データベースに多数のデータが登録されている際に、データベースに登録された全てのデータと入力されたクエリデータとの距離を算出する線形検索を情報処理装置が実行した場合には、近傍検索に要する計算コストが高くなる。そこで、データベースに登録されたデータに基づくインデックスをあらかじめ作成し、クエリデータとの距離を算出するデータの数をインデックスを用いて限定することで、近傍検索を実行するための計算コストを削減する技術が知られている。
【０００５】
例えば、このような技術を適用した情報処理装置は、ＫＤ（Ｋ  Ｄｉｍｅｎｓｉｏｎａｌ）−Ｔｒｅｅ、ＳＲ（Ｓｐｈｅｒｅ／Ｒｅｃｔａｎｇｌｅ）−Ｔｒｅｅ、Ｒ−Ｔｒｅｅ等の形式を用いて、多次元空間を階層的に分割する。そして、情報処理装置は、近傍検索の対象となる空間を限定することで、クエリデータとの距離を算出するデータの数を限定し、計算コストを削減する。
【０００６】
また、多次元空間中に参照ポイントを設定し、設定した参照ポイントとデータベースに登録された各データとの距離をあらかじめ算出することで、クエリデータの近傍候補から明らかに除外できるデータを枝刈りする技術が知られている。例えば、このような技術を適用した情報処理装置は、参照ポイントとデータベースに登録された各データとの距離をあらかじめ算出する。また、情報処理装置は、近傍検索を実行する場合には、クエリデータと参照ポイントとの距離を算出する。
【０００７】
そして、情報処理装置は、クエリデータと参照ポイントとの距離、および、参照ポイントと各データとの距離から、三角不等式により近傍候補から明らかに除外できるデータを枝刈する。このため、情報処理装置は、クエリデータとの間の距離を算出するデータの数を限定し、計算コストを削減する。
【０００８】
また、参照ポイントとデータベースに登録されたデータとの距離をインデックスのキーとして、Ｂ＋Ｔｒｅｅのインデックスを生成する技術が知られている。例えば、このような技術を適用した情報処理装置は、データベースにデータを登録する際に、参照ポイントからの距離を元にインデックスのキーを生成し、生成したキーと共にインデックスにデータを登録する。そして、情報処理装置は、近傍検索を実行する際に、インデックスを用いて、クエリデータの近傍範囲のキーを有する登録データを近傍候補として検索することで、クエリデータとの間の距離を算出するデータの数を限定し、計算コストを削減する。
【０００９】
また、クエリデータの近傍範囲に誤差を容認することで、クエリデータの近傍範囲に位置するデータの検索を高速化する技術が知られている。このような技術を適用した情報処理装置は、クエリデータの近傍に位置するデータを近似的に検索することで、近傍検索に要する計算コストを削減し、近傍検索を高速化する。
【００１０】
上述した近傍検索を実行する情報処理装置は、例えば、クエリデータとして指紋や静脈の形状等の生体データを取得し、取得した生体データが示す人物と同一人物の生体データがデータベースに保存されているかを判別する生体認証を実行する場合がある。このような生体認証を実行する情報処理装置は、クエリデータと類似するデータを近傍検索により絞り込むことで、計算コストが高い生体データのマッチング処理の対象となるデータの数を限定し、計算コストを削減する。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００９−１９９１５１号公報
【特許文献２】特開２００７−０７３０６３号公報
【特許文献３】特開２００４−０４６６１２号公報
【特許文献４】国際公開第２００８／０２６４１４号
【特許文献５】特開２００５−３２２１６１号公報
【特許文献６】特開２０１０−２２４９０３号公報
【非特許文献】
【００１２】
【非特許文献１】B.  Bustos,  G.  Navarro,  and  E.  Chaves:  Pivot  selection  techniques  for  proximity  searching  in  metric  spaces,  Pattern  Recognition  Letters,  Vol.24,  No.14,  pp.2357-2366  (2003)
【非特許文献２】H.  V.  Jagadish,  Beng  Chin  Ooi,  Kian-Lee  Tan,  Cui  Yu  and  Rui  Zhang  iDistance:  An  Adaptive  B+-tree  Based  Indexing  Method  for  Nearest  Neighbor  Search,  ACM  Transactions  on  Data  Base  Systems  (ACM  TODS),  Vol.30,  No.2,  pp.364-397  (2005)
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上述した近傍検索を行う技術では、登録データを多次元空間内の１つの点とし、データベースに登録された各データとクエリデータとの距離のみに基づいて、クエリデータの近傍検索を行う。このため、データベースに登録されたデータごとに異なる誤差が存在する場合には、適切な近傍検索を行う事ができないという問題があった。
【００１４】
例えば、指紋や静脈などの生体データは、取得時の状況によって変化するため、同一人物の生体データであっても、クエリデータとデータベースに登録されたデータとが完全に一致することは稀である。また、個人差や生体データの取得環境等によってデータベースに登録されるデータとクエリデータとにはバラつきが生じる。
【００１５】
このため、情報処理装置は、バラつきが大きい生体データをクエリデータとした際に、データとクエリデータとの距離のみに基づく近傍検索を実行した場合には、検索結果に含めるべきデータの検索漏れを発生させてしまう場合がある。
【００１６】
図２２は、従来の近傍検索を説明するための図（１）である。例えば、図２２に示す例では、情報処理装置は、図２２中（Ａ）に示すクエリデータから図２２中（Ｂ）の範囲に含まれるデータを近傍範囲のデータとする。ここで、情報処理装置は、図２２中（Ｃ）が検索結果に含めるべきデータであっても、データのバラつきが大きく、入力されたクエリデータが図２２中（Ｃ）に示すデータから遠い場合には、検索結果に含めるべきデータの検索漏れを生じさせてしまう。
【００１７】
また、図２３は、従来の近傍検索を説明するための図（２）である。例えば、図２３に示すように、情報処理装置は、データの検索漏れを防ぐため、図２３中（Ａ）に示すクエリデータの近傍となる範囲を図２３中（Ｂ）に示すように広く設定した場合には、バラつきが少ないデータを必要以上に検索結果に含めてしまう。この結果、情報処理装置は、クエリデータとの距離を算出するデータの数を多くしてしまう結果、近傍検索に要する計算コストを大きくしてしまう。
【００１８】
開示の技術は、上述した問題に鑑みてなされたものであり、検索漏れを防ぐことができる。
【課題を解決するための手段】
【００１９】
１つの側面では、利用者から指定されたクエリデータに類似するデータを検索する情報処理装置である。このような情報処理装置は、検索対象である登録データと、登録データの誤差を示す誤差情報とを対応付けて記憶するデータベースを有する。そして、情報処理装置は、検索要求に係るクエリデータと登録データとの距離から誤差情報に応じた距離を減じた値が所定の近傍範囲内にある登録データをデータベースから検索する。
【発明の効果】
【００２０】
１つの側面では、検索漏れを防ぐことができる。
【図面の簡単な説明】
【００２１】
【図１】図１は、実施例１に係る情報処理システムを説明するための図である。
【図２】図２は、実施例１に係る情報処理装置を説明するための図である。
【図３】図３は、実施例１に関するインデックスの一例を説明するための図である。
【図４】図４は、インデックス検索の一例を説明するための図（１）である。
【図５】図５は、インデックス検索の一例を説明するための図（２）である。
【図６】図６は、実施例１に係る検索処理の結果の一例を説明するための図である。
【図７】図７は、実施例１に係る登録処理の流れの一例を説明するためのフローチャートである。
【図８】図８は、実施例１に係る検索処理の流れの一例を説明するためのフローチャートである。
【図９】図９は、実施例２に係る情報処理装置を説明するための図である。
【図１０】図１０は、実施例２に関するインデックスの一例を説明するための図である。
【図１１】図１１は、実施例２に係るインデックス検索の一例を説明するための図（１）である。
【図１２】図１２は、実施例２に係るインデックス検索の一例を説明するための図（２）である。
【図１３】図１３は、実施例２に係るインデックス検索の一例を説明するための図（３）である。
【図１４】図１４は、実施例２に係る登録処理の流れの一例を説明するためのフローチャートである。
【図１５】図１５は、実施例２に係る検索処理の流れの一例を説明するためのフローチャートである。
【図１６】図１６は、実施例３に係る情報処理装置を説明するための図である。
【図１７】図１７は、実施例３に関するインデックスの一例を説明するための図である。
【図１８】図１８は、実施例３に係る補助参照ポイント選択処理の一例を説明するための図である。
【図１９】図１９は、実施例３に係る補助参照ポイントによる枝刈りの一例を説明するための図である。
【図２０】図２０は、実施例３に係る登録処理の流れの一例を説明するためのフローチャートである。
【図２１】図２１は、実施例３に係る検索処理の流れの一例を説明するためのフローチャートである。
【図２２】図２２は、従来の近傍検索を説明するための図（１）である。
【図２３】図２３は、従来の近傍検索を説明するための図（２）である。
【発明を実施するための形態】
【００２２】
以下に添付図面を参照して本願に係る情報処理装置、情報処理システムおよび検索方法について説明する。
【実施例１】
【００２３】
以下の実施例１では、図を用いて、利用者から入力された生体データに基づいて、利用者の認証を行う情報処理システムについて説明する、図１は、実施例１に係る情報処理システムを説明するための図である。図１に示す例では、情報処理システム１は、認証サーバ３と情報処理装置１０を有する。また情報処理システム１は、ネットワークを介して、利用者の生体データを取得するクライアント装置２と接続されている。
【００２４】
情報処理システム１は、利用者から取得された生体データと同一人物の生体データがデータベースに存在するかを判別する１：Ｎ認証と呼ばれる生体認証を実行する情報処理システムである。情報処理システム１は、ネットワークを介して、利用者から取得された生体データをクライアント装置２から取得する。ここで、クライアント装置２は、利用者の生体データとして、指紋、静脈の画像データ、虹彩等の生体データを取得し、取得した生体データを暗号化した後に、ネットワークを介して、暗号化した生体データを情報処理システム１に送信する。
【００２５】
情報処理システム１が有する情報処理装置１０は、生体データを記憶するデータベースを有し、復号化した生体データと類似するデータをデータベースから検索する。この際、情報処理装置１０は、近傍検索の技術を用いて、効率良く類似するデータを検索する。その後、認証サーバ３は、情報処理装置１０が検索したデータとクライアント装置２が取得した生体データとのマッチングを実行し、利用者の認証を実行する。その後、情報処理システム１は、利用者の認証結果を暗号化し、ネットワークを介して、クライアント装置２へ暗号化した認証結果を送信する。
【００２６】
ここで、認証サーバ３が実行する生体データのマッチング方法としては、指紋や静脈の認証のために様々な特徴量を使用する方法が知られている。例えば、認証サーバ３は、特許文献７〜９に例示する生体データ画像中の小領域における隆線の方向や長さ、勾配、隆線の終端や分岐などの特徴的な点の密度や座標や周波数成分などを用いた手法を採用することができる。また、認証サーバ３は、これら生体データ画像中の特徴を示す数値をベクトル化したものを特徴量ベクトルとして用いることができる。
【００２７】
（特許文献  ７  特許第2815045号  画像特徴抽出装置、画像特徴解析装置、および画像照合システム）
【００２８】
（特許文献  ８  特開2006-277407  照合方法および照合装置）
【００２９】
（特許文献  ９  特開2007-249339  生体認証方法及び生体認証装置）
【００３０】
次に、図２を用いて、情報処理装置１０について説明する。図２は、実施例１に係る情報処理装置を説明するための図である。図２に示す例では、情報処理装置１０は、データ登録処理部２０と検索処理部３０を有する。データ登録処理部２０は、データベース２１、参照ポイント情報記憶部２２、最大誤差情報記憶部２３、インデックス記憶部２４、距離算出部２５、インデックス登録部２６を有する。また、検索処理部３０は、インデックス検索範囲算出部３１、インデックス検索部３２、近傍データ確定部３３を有する。
【００３１】
データベース２１は、利用者の生体データである登録データを記憶する。また、データベース２１は、各登録データの誤差を示す誤差パラメータを登録データごとに記憶する。
【００３２】
以下、新規利用者の生体データを新たに登録する例を用いて、データベース２１に生体データと誤差パラメータとを登録する処理について説明する。例えば、新規利用者は、新たに登録するデータとして、同時期に取得した複数の生体データを情報処理装置１０に入力する。
【００３３】
情報処理装置１０は、入力された複数の生体データから得られる特徴量の平均や分散などの統計量を用いて、入力された生体データの特徴を示す特徴量ベクトルおよび誤差パラメータを算出する。その後、情報処理装置１０は、算出した特徴量ベクトルを登録データとし、図２中（Ｂ）に示すように、データベース２１に格納する。また、情報処理装置１０は、算出した誤差パラメータを算出した特徴量ベクトル、すなわち登録データと対応付けて、データベース２１に格納する。
【００３４】
ここで、誤差パラメータは各データのバラつき度合いを表すものであり、データの登録時に与えられる。例えば、生体認証システムを考えた場合、生体データの登録の際には複数回の生体データの採取を行うのが一般的であるため、複数個の生体データから得られる特徴量の平均や分散などの統計量を用いて特徴量ベクトルや誤差パラメータを与えることができる。また、登録データ採取時のデバイスの精度や設置状況などから推測できる生体データの質から誤差パラメータを設定することとしてもよい。また、生体データは、データを登録してから年月が経過するとクエリデータとして取得する生体データが変化することも考えられるため、登録からの年月に応じて誤差パラメータを変化させるようにしてもよい。
【００３５】
参照ポイント情報記憶部２２は、参照ポイントの位置を示す情報を記憶する。例えば、参照ポイント情報記憶部２２は、図２中（Ａ）に示すように、あらかじめ設定された多次元空間内における複数の参照ポイントｏ１〜ｏＭの位置を示す情報を受信した場合には、受信した参照ポイントの位置を示す情報を記憶する。
【００３６】
ここでデータベース２１は、生体データの特徴量を示す特徴量ベクトルを登録データとして記憶する。そこで、参照ポイント情報記憶部２２は、データベース２１が採用する特徴量ベクトルの次元数と同じ次元数の任意のベクトルを参照ポイント情報として記憶する。
【００３７】
最大誤差情報記憶部２３は、各参照ポイントと対応付けられた登録データに係る誤差パラメータのうち、最も大きい値を有する誤差パラメータを参照ポイントと対応付けて記憶する。また、最大誤差情報記憶部２３は、参照ポイントと対応付けられた登録データのうち、参照ポイントから最も遠方に位置する登録データと参照ポイントとの距離を各参照ポイントと対応付けて記憶する。
【００３８】
例えば、参照ポイントｏｉに複数の登録データｐ１〜ｐｘが対応付けられており、各登録データｐ１〜ｐｘの誤差パラメータがε１〜εＸであり、誤差パラメータがε１〜εＸのうち、最大の値を有する誤差パラメータをεｉｍａｘとする。また、登録データｐ１〜ｐｘのうち、参照ポイントｏｌから最も遠方にある登録データまでの距離がｒｉｍａｘであるとする。このような場合には、最大誤差情報記憶部２２は、ｏｉとεｉｍａｘとｒｉｍａｘとを対応付けて記憶する。以下の説明においては、各登録データと対応付けられた参照ポイントを対応参照ポイントとして説明する。
【００３９】
インデックス記憶部２４は、検索処理部３０がクエリデータの近傍候補となるデータをデータベース２１から検索するために利用するインデックスを記憶する。具体的には、インデックス記憶部２４は、参照ポイントごとに、後述するインデックス登録部２６によって算出されるキー値と、キー値と対応する登録データと、登録データの誤差パラメータとを対応付けて記憶する。
【００４０】
以下、図３を用いて、インデックス記憶部２４が記憶するインデックスについて説明する。図３は、実施例１に関するインデックスの一例を説明するための図である。図３に示すように、インデックスは、Ｔｒｅｅ型のインデックスであり、図３中（Ａ）に示すように、インデックス登録部２６によって算出されたキー値を階層的に有する。また、図３中（Ｂ）に示すように、対応するキー値と対応付けて、登録データと登録データの誤差パラメータとを有する。つまり、インデックスは、インデックス登録部２６によって登録データごとに算出されるキー値を階層的に有し、各キー値と対応するデータとして登録データと誤差パラメータとを記憶する。
【００４１】
図２に戻って、距離算出部２５は、入力された登録データと参照ポイントとの距離を算出し、算出した距離をインデックス登録部２６に通知する。具体的には、距離算出部２５は、図２中（Ｂ）に示すように、登録データがデータベース２１に格納される際に、登録データと参照ポイント情報記憶部２２に格納されている各参照ポイントとの距離を算出する。
【００４２】
そして、距離算出部２５は、算出した距離のうち、最も近い距離、つまり、対応参照ポイントと登録データとの距離を、図２中（Ｃ）に示すように、インデックス登録部２６に通知する。また、距離算出部２５は、対応参照ポイントと登録データと登録データの誤差パラメータとをインデックス登録部２６に通知する。
【００４３】
インデックス登録部２６は、距離算出部２５が算出した距離に基づいて、対応参照ポイントごとに異なる範囲のキー値を生成する。そして、インデックス登録部２６は、図２中（Ｄ）に示すように、インデックス記憶部２４が記憶するインデックスに、生成したキー値と対応するデータとして登録データと登録データの誤差パラメータとを追加する。
【００４４】
また、インデックス登録部２６は、図２中（Ｅ）に示すように、対応参照ポイントと対応付けられた登録データの誤差パラメータのうち、最も大きい値を有する誤差パラメータを対応参照ポイントと対応付けて最大誤差情報記憶部２３に格納する。また、インデックス登録部２６は、対応参照ポイントと対応付けられた各登録データとの距離のうち、最も大きい値を有する距離を対応参照ポイントと対応付けて最大誤差情報記憶部２３に格納する。
【００４５】
このように、データ登録処理部２０は、登録データと誤差パラメータとを記憶する。また、データ登録処理部２０は、登録データと誤差パラメータとを記憶する際に、対応参照ポイントと登録データとの距離を算出し、算出した距離の値をキー値とするインデックスを作成する。また、データ登録処理部２０は、対応参照ポイントと対応付けられる登録データの誤差パラメータのうち、最も大きい誤差パラメータの値と、対応参照ポイントと対応付けられた登録データとの距離のうち、最も大きい距離の値とを対応参照ポイントごとに記憶する。
【００４６】
次に、検索処理部３０が有する各部について説明する。インデックス検索範囲算出部３１は、認証を行う生体データ、つまり、クエリデータを取得した場合には、誤差パラメータを考慮して、取得したクエリデータの近傍候補として検索されるデータのキーの範囲を算出する。そして、インデックス検索範囲算出部３１は、算出したキーの範囲をインデックス検索部３２に通知する。
【００４７】
例えば、インデックス検索範囲算出部３１は、図２中（Ｆ）に示すように、クエリデータを取得する。また、インデックス検索範囲算出部３１は、図２中（Ｇ）に示すように、近傍のデータとみなす近傍範囲を示す情報、つまり、多次元空間内においてクエリデータを中心とした多次元球の半径を取得する。
【００４８】
このような場合には、インデックス検索範囲算出部３１は、距離算出部２５の機能を用いて、各参照ポイントとクエリデータとの距離を算出する。また、インデックス検索範囲算出部３１は、各参照ポイントと対応付けて記憶された誤差パラメータの最大値と登録データとの距離の最大値とを最大誤差情報記憶部２３から取得する。
【００４９】
そして、インデックス検索範囲算出部３１は、各参照ポイントについて、算出した各距離から近傍範囲を減じた値が、対応づけて記憶された誤差パラメータの最大値と距離の最大値との和よりも小さいか否かを判別する。そして、インデックス検索範囲算出部３１は、算出した各距離から近傍範囲を減じた値が、対応づけて記憶された誤差パラメータの最大値と距離の最大値との和よりも小さいと判別した参照ポイントについて、以下の処理を実行する。
【００５０】
すなわち、インデックス検索範囲算出部３１は、参照ポイントとクエリデータとの距離と、近傍範囲を示す情報と、参照ポイントと対応づけて記憶された誤差パラメータの最大値とを用いて、クエリデータの近傍候補となる登録データのキー値の範囲を算出する。そして、インデックス検索範囲算出部３１は、算出したキー値の範囲を図２中（Ｉ）に示すように、インデックス検索部３２に通知する。
【００５１】
インデックス検索部３２は、インデックス検索を行い、インデックス検索範囲算出部３１が算出したキー値の範囲に含まれるデータ、つまり、クエリデータの近傍候補となるデータを判別する。そして、インデックス検索部３２は、判別したクエリデータの近傍候補となるデータを近傍データ確定部３３に通知する。
【００５２】
例えば、インデックス検索部３２は、インデックス検索範囲算出部３１からキー値の範囲を取得した場合には、取得したキー値の範囲に含まれる登録データをインデックスから検索する。そして、インデックス検索部３２は、図２中（Ｊ）に示すように、判別した登録データを近傍データ確定部３３に通知する。
【００５３】
近傍データ確定部３３は、クエリデータの近傍候補となる各登録データについて、クエリデータと登録データとの距離から誤差パラメータを減じた値が近傍範囲に含まれるか否かを判別する。そして、近傍データ確定部３３は、クエリデータと登録データとの距離から誤差パラメータを減じた値が近傍範囲に含まれるか否かを判別したデータを近傍データとして認証サーバ３に出力する。
【００５４】
例えば、近傍データ確定部３３は、インデックス検索部３２がインデックス記憶部２４に記憶されたインデックスから検索したクエリデータの近傍候補となる登録データの通知を受ける。このような場合には、近傍データ確定部３３は、通知された各登録データについて、クエリデータと登録データとの距離から誤差パラメータの値を減算した値が近傍範囲の値よりも小さいか否かを判別する。つまり、近傍データ確定部３３は、各登録データと誤差パラメータとが示す範囲が、クエリデータの近傍範囲と重複しているか否かを判別する。
【００５５】
そして、近傍データ確定部３３は、クエリデータと登録データとの距離から誤差パラメータの値を減算した値が近傍範囲の値よりも小さいと判別した場合には、通知された登録データがクエリデータの近傍データであると判別する。その後、近傍データ確定部３３は、クエリデータの近傍データであると判別した各登録データを図２中（Ｋ）に示すように、認証サーバ３に送信する。
【００５６】
このように、検索処理部３０は、クエリデータと近傍範囲とを取得した場合には、インデックスを用いて、誤差パラメータの最大値を考慮したクエリデータの近傍候補となる登録データを検索する。そして、検索処理部３０は、検索した各登録データについて、各登録データと誤差パラメータとが示す範囲が、クエリデータの近傍範囲と重複しているか否かを判別し、重複していると判別した登録データをクエリデータの近傍データであると判別する。
【００５７】
このため、検索処理部３０は、各登録データの誤差パラメータにバラつきがある場合にも、検索漏れを起こすことなく、近傍検索を行うことができる。つまり、検索処理部３０は、誤差パラメータが大きい登録データについては、クエリデータの近傍データであると判別する範囲を広くし、誤差パラメータが小さい登録データについては、クエリデータの近傍データであると判別する範囲を小さくする。このため、検索処理部３０は、検索漏れを防ぐと同時に、不要な登録データを近傍データから極力除外することができる。この結果、検索処理部３０は、適切な近傍検索を行う事ができる。
【００５８】
また、検索処理部３０は、近傍データであるか否かを判別する前に、インデックスを用いて、近傍データであるか否かを判別する登録データを限定する。このため、検索処理部３０は、クエリデータと登録データとの距離を算出する処理を最小限に押さえるので、計算コストを削減し、かつ、高速で近傍検索を行うことができる。
【００５９】
例えば、距離算出部２５、インデックス登録部２６、インデックス検索範囲算出部３１、インデックス検索部３２、近傍データ確定部３３とは、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ  （Field  Programmable  Gate  Array）などの集積回路、またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などを適用する。
【００６０】
また、データベース２１、参照ポイント情報記憶部２２、最大誤差情報記憶部２３、インデックス記憶部２４とは、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ（flash  memory）などの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。
【００６１】
次に、図４〜図６および数式を用いて、情報処理装置１０が実行する処理の具体例について説明する。なお、以下の説明においては、登録対象データを「ｐ」、登録対象データに関する誤差パラメータを「ε」、各参照ポイントを「ｏ１〜ｏｍ」、参照ポイントの数を「Ｍ」と記載する。また、データＸとデータＹとの多次元空間内における距離を算出する距離関数を「ｄ（Ｘ、Ｙ）」と記載する。
【００６２】
まず、新たなデータを登録データとしてデータベース２１に格納する処理について説明する。まず、情報処理装置１０は、距離関数を用いて、各参照ポイントと登録対象データとの距離を算出し、登録されるデータｐに距離が最も近い参照ポイントを対応参照ポイントｏｊとして選択する。次に、情報処理装置は、以下の式（１）と、選択したｏｊとを用いて、登録対象データのキー値Ｋ（ｐ）を算出する。
【００６３】
【数１】
0005601277.tif 000002
【００６４】
ここで、式（１）中のＣは定数である。Ｃが十分大きい場合には、参照ポイントｏｊに対応する登録データのキー値は、［ｊ×Ｃ、（ｊ＋１）×Ｃ）の範囲に収まることとなる。なお、［ｊ×Ｃ、（ｊ＋１）×Ｃ）とは、「ｊ×Ｃ」以上「（ｊ＋１）×Ｃ」未満の範囲を示す。つまり、情報処理装置１０は、各登録データに対して、対応参照ポイントごとに、異なる範囲のキー値を算出することとなる。例えば、情報処理装置１０は、「Ｃ＝１０００」とした場合には、参照ポイントｏ１に対応する登録データのキー値の範囲を［１０００、２０００］の範囲に収めることができる。
【００６５】
次に、情報処理装置１０は、算出したＫ（ｐ）の値をキーとして、登録対象データｐと誤差パラメータεをインデックス記憶部２４が記憶するインデックスとデータベース２１とに追加する。ここで、インデックス記憶部２４が記憶するインデックスのデータ構造は、範囲検索が行える構造であれば任意の構造を適用することができるが、例えば、Ｂ＋−ＴｒｅｅやＢ−Ｔｒｅｅなどのデータ構造を適用することができる。
【００６６】
また、情報処理装置１０は、参照ポイントｏｊと対応する登録データと参照ポイントｏｊとの距離が最大の距離ｒｊｍａｘをｏｊと対応付けて最大誤差情報記憶部２３に格納する。また、参照ポイントｏｊと対応する登録データの誤差パラメータのうち、最大の値を有する誤差パラメータをεｊｍａｘとして最大誤差情報記憶部２３に格納する。また、情報処理装置１０は、登録対象データｐをデータベース２１に格納するたびに、ｒｊｍａｘまたはεｊｍａｘが更新されるか否かを判別し、更新される場合には、ｒｊｍａｘまたはεｊｍａｘを新たな値に更新する。
【００６７】
次に、情報処理装置１０が入力されたクエリデータと近傍範囲を示す情報とに応じて、近傍データを検索する処理について説明する。以下の説明においては、入力されたクエリデータを「ｑ」、近傍範囲を示す情報を「Ｕ」として説明する。まず、情報処理装置１０は、全ての参照ポイントｏｉ（ｉ＝１、２、…Ｍ）について以下の式（２）を満たすか否かを判別し、満たすと判別した場合には、各参照ポイントと対応付けられた登録データがクエリデータの近傍候補になると判別する。
【００６８】
【数２】
0005601277.tif 000003
【００６９】
次に、情報処理装置１０は、式（２）を満たす参照ポイントｏｉについて、あらかじめ作成したインデックスから、誤差パラメータを考慮したキーの値が式（３）で示される範囲の登録データを検索する。
【００７０】
【数３】
0005601277.tif 000004
【００７１】
つまり、情報処理装置１０は、インデックスを利用して式（３）を満たす範囲のインデックスを検索することで、クエリデータの近傍候補となるデータを検索する。このため、情報処理装置１０は、クエリデータの近傍候補となるデータを高速で検索することができる。
【００７２】
ここで、図４は、インデックス検索の一例を説明するための図である。図４中（Ａ）は参照ポイントｏｉを示し、図４中（Ｂ）は、クエリデータを示す。また、図４中（Ｃ）は、参照ポイントｏｉからｒｉｍａｘ＋εｉｍａｘの範囲を示す。また、図４中（Ｄ）は、登録データに係る誤差パラメータが示す誤差の範囲を示す。また、図４中（Ｅ）は、入力されたＵが示す近傍範囲を示し、図４中（Ｆ）は、クエリデータからＵ＋εｉｍａｘの範囲を示す。情報処理装置１０は、参照ポイントと登録データとの距離から算出される値をキーとしてインデックスに登録している。このため、式（３）を満たす登録データ、つまり近傍候補となる登録データは、図４に示すドーナツ状の網掛けした範囲に含まれる登録データとなる。
【００７３】
次に、情報処理装置１０は、インデックス検索によって取得した近傍候補の登録データとクエリデータとの距離を実際に算出し、算出した距離から誤差パラメータに応じた距離を減じた値が近傍範囲に含まれるか否かを判別する。つまり、情報処理装置１０は、近傍候補の各登録データとクエリデータとの距離が、以下の式（４）を満たすか否かを判別する。なお、式（４）中の「ｖ」は、インデックス検索によって取得した近傍候補データを示し、「εｖ」は、近傍候補データの誤差パラメータである。
【００７４】
【数４】
0005601277.tif 000005
【００７５】
その後、情報処理装置１０は、式（４）を満たす近傍候補データを近傍データであると判別した場合には、図５中の網掛けをした丸印で示される登録データを近傍データとして認証サーバ３に送信する。なお、図５は、インデックス検索の一例を説明するための図（２）である。図５中（Ａ）は、参照ポイントｏｉを示し、図５中（Ｂ）は、クエリデータを示す。また、図４中（Ｃ）は、式（４）を満たす登録データを示し、図４中（Ｄ）は、同図中（Ｃ）に示す登録データの誤差パラメータが示す誤差の範囲を示す。また、図５中（Ｅ）は、入力されたＵが示す近傍範囲である。
【００７６】
次に、図６を用いて、情報処理装置１０による近傍データの検索結果について詳細に説明する。図６は、実施例１に係る検索処理の結果の一例を説明するための図である。図６中（Ａ）は、参照ポイントを示し、図６中（Ｂ）は、近傍範囲を示す。また、図６中網がけした丸印は、近傍データとして検索された登録データを示す。
【００７７】
情報処理装置１０は、式（４）を満たす登録データを近傍データとした場合には、図６中（Ｃ）に示すように、近傍範囲に登録データが含まれていなくとも、誤差パラメータが示す範囲が近傍範囲と重複する登録データを近傍データであると判別する。このため、情報処理装置１０は、図６中（Ｃ）に示すような、従来取りこぼしてしまう誤差の大きな登録データを近傍データに含めることができる。
【００７８】
［情報処理装置１０の処理の流れ］
次に、図７を用いて、情報処理装置１０が新たなデータを登録する処理の流れの一例について説明する。図７は、実施例１に係る登録処理の流れの一例を説明するためのフローチャートである。図７に示す例では、情報処理装置１０は、データベース２１に新たに登録するデータと誤差パラメータとを受信したことをトリガとして、処理を開始する。
【００７９】
まず、情報処理装置１０は、新たに登録する登録対象データと誤差パラメータとをデータベース２１に格納する（ステップＳ１０１）。次に、情報処理装置１０は、登録対象データの対応参照ポイントを算出する（ステップＳ１０２）。次に、情報処理装置１０は、算出した対応参照ポイントと登録データとの距離に基づいて、登録データのキー値を算出し、算出したキー値と登録対象データと誤差パラメータとをインデックス記憶部２４に記憶されたインデックスに登録する（ステップＳ１０３）。
【００８０】
次に、情報処理装置１０は、算出した距離または取得した誤差パラメータが対応参照ポイントと対応付けられた距離の最大値または誤差パラメータの最大値を更新しているか否かを判別する（ステップＳ１０４）。そして、情報処理装置１０は、対応参照ポイントと対応付けられた距離の最大値または誤差パラメータの最大値を更新していると判別した場合には（ステップＳ１０４肯定）、以下の処理を実行する。
【００８１】
すなわち、情報処理装置１０は、対応参照ポイントと対応付けられた距離の最大値または誤差パラメータの最大値を更新し（ステップＳ１０５）、登録処理を終了する。一方、情報処理装置１０は、対応参照ポイントと対応付けられた距離の最大値または誤差パラメータの最大値を更新してないと判別した場合には（ステップＳ１０４否定）、そのまま登録処理を終了する。
【００８２】
次に、図８を用いて、情報処理装置１０が入力されたクエリデータの近傍データを検索する処理の流れの一例について説明する。図８は、実施例１に係る検索処理の流れの一例を説明するためのフローチャートである。図８に示す例では、情報処理装置１０は、クエリデータおよび近傍範囲を示す情報を取得したことをトリガとして、検索処理を開始する。
【００８３】
まず、情報処理装置１０は、クエリデータおよび近傍範囲を示す情報とを取得する（ステップＳ２０１）。このような場合には、情報処理装置１０は、取得したクエリデータの近傍候補となる登録データと対応付けられた対応参照ポイントと、近傍候補となる登録データのキー値の範囲とを算出する（ステップＳ２０２）。次に、情報処理装置１０は、算出したキー値の範囲に含まれる登録データ、つまり近傍候補となる登録データをインデックスから検索する（ステップＳ２０３）。
【００８４】
次に、情報処理装置１０は、インデックスから検索した各登録データについて、クエリデータとの距離を算出し、近傍データの確定を行う（ステップＳ２０４）。次に、情報処理装置１０は、確定した近傍データのリストを出力し（ステップＳ２０５）、処理を終了する。
【００８５】
［実施例１の効果］
上述したように、情報処理装置１０は、検索対象である登録データと各登録データの誤差を示す誤差パラメータとを対応付けて記憶する。そして、情報処理装置１０は、クエリデータと登録データとの距離から、誤差パラメータに応じた距離を減じた値が所定の近傍範囲内にある登録データを近傍データとする。このため情報処理装置１０は、誤差が大きい登録データの検索漏れを防ぐことができる。また、情報処理装置１０は、誤差が小さい登録データを必要以上に検索することがないので、認証サーバ３が実行するマッチング処理の計算コストを少なくすることができる。この結果、情報処理システム１は、適切な認証処理を実行させることができる。
【００８６】
また、情報処理装置１０は、登録データと対応参照ポイントとの距離と、対応参照ポイントと対応する各登録データとの距離の最大値と、対応参照ポイントと対応する各登録データの誤差パラメータの最大値とをあらかじめインデックスとして記憶する。そして、情報処理装置１０は、クエリデータと対応参照ポイントとの距離と対応参照ポイントと対応する各登録データの誤差パラメータの最大値とから算出される値をキーとして、インデックスから近傍候補となる登録データを検索する。その後、情報処理装置１０は、検索した近傍候補となる登録データとクエリデータとの距離を算出し、近傍データを確定する。
【００８７】
このため、情報処理装置１０は、全ての登録データとクエリデータとの距離を算出せずとも、クエリデータの近傍データを確定することができる。すなわち、情報処理装置１０は、インデックスを用いて明らかにクエリデータの近傍データから除外できる登録データを除外し、その後、距離を算出することで、近傍データか否かを判別する。このため、情報処理装置１０は、クエリデータとの距離を算出する登録データの数を限定することができる。この結果、情報処理装置１０は、近傍検索に要する計算コストを削減し、より効率的な近傍検索を行う事ができる。
【実施例２】
【００８８】
実施例２では、参照ポイントと登録データとの距離以外の情報をインデックスとして記憶することによって、近傍候補をさらに効率良く検索する情報処理装置１０ａについて説明する。
【００８９】
ここで、従来の近傍検索を行う技術では、データベースに登録された各データとクエリデータとの距離のみに基づいて、クエリデータの近傍検索を行う。このため、登録データの数が多くなった場合や、登録データを記憶する際に適用する多次元空間の次元数が多く、距離を算出するための計算コストが高い場合には、近傍検索に要する計算コストが距離計算の回数に等しくなる。つまり、参照ポイントと登録データとの距離をインデックスとして記憶し、三角不等式を用いて近傍候補から登録データの枝刈を行う技術では、多次元空間の次元数が多くなった場合には計算コストが多くなるという問題があった。
【００９０】
また、登録データと参照ポイントとの距離のみを用いて登録データの枝刈を行う技術では、参照ポイントからの距離が所定の範囲外の登録データを枝刈する。このため、参照ポイントを中心点とした際に、所定の範囲内にある登録データのうち、クエリデータと反対側に位置する登録データを除外することができない。この結果、近傍データを確定する際の計算コストが多くなるという問題があった。
【００９１】
実施例２に開示の技術は、上述した問題に鑑みてなされたものであって、適切に枝刈を行い、近傍データを確定する際の計算コストを削減する。
【００９２】
図９は、実施例２に係る情報処理装置を説明するための図である。図９に示す例では、情報処理装置１０ａは、データ登録処理部２０ａ、検索処理部３０ａを有する。データ登録処理部２０ａは、データベース２１ａ、参照ポイント情報記憶部２２、インデックス記憶部２４ａ、距離算出部２５、インデックス登録部２６ａ、内積算出部２７を有する。また、検索処理部３０ａは、インデックス検索範囲算出部３１、インデックス検索部３２、候補枝刈り部３４、近傍データ確定部３３を有する。
【００９３】
なお、情報処理装置１０ａが有する各部のうち、実施例１に係る情報処理装置１０が有する各部と同様の処理を実行するものについては、同一の符号を付し、詳細な説明を省略する。また、以下の説明においては、情報処理装置１０ａは、各登録データの誤差パラメータを考慮せずに、処理を実行するものとする。また、情報処理装置１０ａは、実施例１に係る情報処理装置１０と同様に、生体データのマッチングを行う情報処理システム１ａが有する情報処理装置である。
【００９４】
データベース２１ａは、登録データと、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを対応付けて記憶する。
【００９５】
インデックス記憶部２４ａは、登録データと対応参照ポイントとの距離に基づく値をキー値として、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とをインデックスとして記憶する。ここで、図１０は、インデックス記憶部２４ａを説明するための図である。図１０に示す例では、インデックス記憶部２４ａは、実施例１に係るインデックス記憶部２４と同様の構成を有するインデックスを記憶する。つまり、図１０中（Ａ）に示すように、登録データと対応参照ポイントとの距離に基づくキー値を階層的に有し、図１０中（Ｂ）に示すように、登録データと各参照ポイントとの距離および内積値をキー値と対応付けたインデックスを記憶する。
【００９６】
図９に戻って、内積算出部２７は、登録データと各参照ポイントとの内積値を算出する。例えば、内積算出部２７は、図９中（Ａ）に示すように、登録データを取得した場合には、取得した登録データと参照ポイント情報記憶部２２に格納された各参照ポイントとの内積を算出する。ここで、内積算出部２７が算出する内積とは、登録データを示す特徴量ベクトルと各参照ポイントを示す特徴量ベクトルとの内積である。換言すると、内積算出部２７は、登録データを多次元空間内のポイントとして示した場合に、同じ多次元空間内に位置する各参照ポイントを終端とするベクトルと、登録データを終端とするベクトルとの内積である。
【００９７】
インデックス登録部２６ａは、距離算出部２５が算出した登録データと各参照ポイントとの距離と、内積算出部２７が算出した登録データと各参照ポイントとの内積とをインデックス記憶部２４ａが記憶するインデックスに追加する。例えば、インデックス登録部２６ａは、距離算出部２５が算出した登録データと各参照ポイントとの距離を取得する。また、インデックス登録部２６ａは、内積算出部２７が算出した登録データと各参照ポイントとの内積とを取得する。
【００９８】
そして、インデックス登録部２６ａは、距離算出部２５が算出した距離のうち、最も短い距離、すなわち、登録データと登録データの対応参照ポイントとの距離に基づくキー値を算出する。その後、インデックス登録部２６ａは、算出したキー値と対応付けて、登録データと各参照ポイントとの距離と、内積算出部２７が算出した登録データと各参照ポイントとの内積とをインデックスに追加する。
【００９９】
また、インデックス登録部２６ａは、登録データと各参照ポイントとの距離と、内積算出部２７が算出した登録データと各参照ポイントとの内積とをデータベース２１ａに格納する。また、インデックス登録部２６は、図示しない経路を用いて、対応参照ポイントと対応付けられた各登録データとの距離のうち、最も大きい値を有する距離を対応参照ポイントと対応付けて参照ポイント情報記憶部２２に格納する。
【０１００】
インデックス検索範囲算出部３１は、実施例１と同様に、図９中（Ｃ）に示すクエリデータと図９中（Ｄ）に示す近傍範囲を示す情報を取得した場合には、図９中（Ｅ）に示すように、距離算出部２５を利用してクエリデータと各参照ポイントとの距離を算出する。そして、インデックス検索範囲算出部３１は、算出したクエリデータと対応参照ポイントとの距離と、近傍範囲を示す情報とを用いて、インデックス検索を行うキー値の範囲を算出する。そして、インデックス検索範囲算出部３１は、図９中（Ｆ）に示すように、算出したキー値の範囲をインデックス検索部３２に通知する。
【０１０１】
インデックス検索部３２は、実施例１と同様に、インデックス記憶部２４ａが記憶するインデックスから、インデックス検索範囲算出部３１から取得したキー値の範囲を検索する。そして、インデックス検索部３２は、検索された範囲のキー値と対応付けて記憶された登録データと、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを取得する。
【０１０２】
その後、インデックス検索部３２は、図９中（Ｇ）に示すように、取得された登録データと、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを候補枝刈り部３４に通知する。つまり、インデックス検索部３２は、インデックスを検索した結果取得した近傍候補の登録データについて、登録データと、登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを候補枝刈り部３４に通知する。
【０１０３】
候補枝刈り部３４は、インデックス検索部３２から取得した登録データと各参照ポイントとの距離と、登録データと各参照ポイントとの内積値とを用いて、近傍候補となる登録データの枝刈を行う。
【０１０４】
詳細には、候補枝刈り部３４は、インデックス検索部３２から取得した近傍候補となる登録データについて、クエリデータと登録データの対応参照ポイントとの距離から登録データと対応参照ポイントとの距離を減じた値が所定の近傍範囲内にあるか否かを判別する。そして、候補枝刈り部３４は、クエリデータと登録データの対応参照ポイントとの距離から登録データと対応参照ポイントとの距離を減じた値が所定の近傍範囲内にない場合には、登録データを近傍候補から除外する。
【０１０５】
また、候補枝刈り部３４は、近傍候補となる登録データについて、登録データと対応参照ポイントとの内積からクエリデータと登録データの対応参照ポイントとの内積を減じた値が、以下の条件を満たすか否かを判別する。つまり、候補枝刈り部３４は、長さが近傍範囲と等しい任意のベクトルと登録データの対応参照ポイントとの内積よりも大きいか判別する。そして、候補枝刈り部３４は、登録データと対応参照ポイントとの内積からクエリデータと登録データの対応参照ポイントとの内積を減じた値が、任意のベクトルと登録データの対応参照ポイントとの内積よりも大きいと判別した場合には、以下の処理を実行する。すなわち、候補枝刈り部３４は、登録データを近傍候補から除外する。
【０１０６】
さらに、候補枝刈り部３４は、参照ポイントを多次元空間内における原点を中心として、多次元空間内においてクエリデータが位置する点と登録データが位置する点とを通る平面と平行な面上を回転させる。この際、候補枝刈り部３４は、近傍候補から除外する登録データが最大となる位置まで参照ポイントを回転させる。そして、候補枝刈り部３４は、登録データと回転後の参照ポイントとの内積からクエリデータと回転後の参照ポイントとの内積を減じた値が、任意のベクトルと回転後の参照ポイントとの内積よりも大きいと判別した場合には、登録データを近傍候補から除外する。その後、候補枝刈り部３４は、図９中（Ｈ）に示すように、近傍候補から除外されなかった登録データを近傍データ確定部３３に通知する。
【０１０７】
このように、候補枝刈り部３４は、距離と内積とに基づいて、インデックスから検索された近接候補の枝刈りを実行する。このため、候補枝刈り部３４は、近接データを確定するために、クエリデータとの距離を算出する近接候補の数を減らし、近傍データを確定する際の計算コストを削減する。また、候補枝刈り部３４は、あらかじめ算出された距離と内積とに基づいて、枝刈りを実行する。
【０１０８】
つまり、候補枝刈り部３４は、予め算出しておいた距離とクエリデータと参照ポイントの距離を利用して三角不等式によって、登録データとクエリデータ間の距離を計測することなく安全にクエリデータの近傍外のデータを検索候補から除外することができる。また、候補枝刈り部３４は、予め算出しておいた内積値とクエリデータと参照ポイントの内積値を利用して、登録データとクエリデータ間の距離や内積値を計測することなく安全にクエリデータの近傍外のデータを検索候補から除外することができる。
【０１０９】
ここで、距離による枝刈りと内積値による枝刈りでは枝刈り可能なデータが異なるので、候補枝刈り部３４は、距離による枝刈りと内積値による枝刈りを併用することで、より効果的に近傍候補となる登録データの枝刈りを実行することができる。この結果、情報処理装置１０ａは、近傍データを確定する際に必要な距離計算回数を削減でき、近傍検索を効率化することが可能となる。
【０１１０】
さらに、候補枝刈り部３４は、内積値による枝刈りを行う場合には、枝刈りする登録データが最も多い位置まで参照ポイントを回転させ、枝刈りを実行する。このため、候補枝刈り部３４は、近傍検索をより効率化することができる。
【０１１１】
図９に戻って、近傍データ確定部３３は、近傍候補に残った登録データを取得した場合は、取得した登録データとクエリデータとの距離を算出し、登録データがクエリデータの近傍データであるか否かを確認する。その後、近傍データ確定部３３は、図９中（Ｉ）に示すように、近傍データであると確認された登録データのリストを、認証サーバ３に出力する。
【０１１２】
例えば、内積算出部２５、候補枝刈り部３４とは、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路、またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などを適用する。
【０１１３】
次に、図１１〜図１３および数式を用いて、情報処理装置１０ａが実行する処理の具体例について説明する。なお、以下の説明においては、実施例１と同様の記号を用いるものとし、さらに、データＸとデータＹとの内積を＜Ｘ,Ｙ＞で表すものとする。また、説明を簡単にするために、各登録データの誤差パラメータについては、考慮しないものとする。
【０１１４】
まず、新たなデータを登録データとしてデータベース２１ａに格納する処理について説明する。まず、情報処理装置１０ａは、登録対象データと各参照ポイント「ｏｉ（ｉ＝１〜Ｍ）」との距離「ｄ（ｏｉ,ｐ）」と内積値「＜ｏｉ,ｐ＞」とを算出し、登録対象データと最も距離が近い参照ポイントを対象参照ポイントｏｊとして選択する。また、情報処理装置１０ａは、式（１）と、選択したｏｊとを用いて、登録対象データのキー値Ｋ（ｐ）を算出する。
【０１１５】
次に、情報処理装置１０ａは、算出したＫ（ｐ）の値をキーとし、登録対象データｐと、算出した登録対象データと各参照ポイントとの距離と、算出した登録対象データと各参照ポイントとの内積値とをインデックス記憶部２４ａが記憶するインデックスに追加する。また、情報処理装置１０ａは、登録対象データｐと、算出した登録対象データと各参照ポイントとの距離と、算出した登録対象データと各参照ポイントとの内積値とをデータベース２１ａに登録する。また、情報処理装置１０ａは、参照ポイントｏｊと対応する登録データと参照ポイントｏｊとの距離が最大の距離ｒｊｍａｘをｏｊと対応付けて参照ポイント情報記憶部２２に格納する。
【０１１６】
次に、情報処理装置１０ａが入力されたクエリデータと近傍範囲を示す情報とに応じて、近傍データを検索する処理について説明する。まず、情報処理装置１０ａは、各参照ポイント「ｏｉ（ｉ＝１〜Ｍ）」とクエリデータｑとの距離「ｄ（ｏｉ,ｑ）」と内積値「＜ｏｉ,ｑ＞」を算出する。また、情報処理装置１０ａは、以下の式（５）を用いて、参照ポイント「ｏｉ」と対応付けられた登録データが近傍候補になるか否かを判別する。
【０１１７】
【数５】
0005601277.tif 000006
【０１１８】
次に、情報処理装置１０ａは、式（５）を満たす参照ポイントｏｉについて、あらかじめ作成したインデックスから、キーの値が以下の式（６）で示される範囲の登録データを検索する。
【０１１９】
【数６】
0005601277.tif 000007
【０１２０】
ここで、図１１は、実施例２に係るインデックス検索の一例を説明するための図（１）である。図１１中（Ａ）は、参照ポイントｏｉを示し、図１１中（Ｂ）はクエリデータを示す。また、図１１中（Ｃ）は、参照ポイントｏｉからｒｉｍａｘの範囲を示し、図１１中（Ｄ）は、クエリデータからＵの範囲を示す。情報処理装置１０ａは、対応参照ポイントと登録データとの距離とをキーとして各登録データをインデックスに登録している。このため、式（６）を満たす登録データ、つまり近傍候補となる登録データは、図１１に示すドーナツ状の網掛けした範囲内に存在するデータとなる。
【０１２１】
次に、情報処理装置１０ａは、インデックスに登録された登録データと各参照ポイントとの距離と登録データと各参照ポイントとの内積値とを用いて、近傍候補の枝刈りを実行する。まず、情報処理装置１０ａは、予め算出し、インデックスに登録しておいた登録データと各参照ポイントとの距離を用いた枝刈りを実行する。具体的には、情報処理装置１０ａは、各参照ポイント「ｏｉ（ｉ＝１〜Ｍ）」について、以下の式（７）を満たす登録データを、近傍候補から除外する。なお、式（７）を用いた枝刈りにおいては、クエリデータと各参照ポイントとの距離を計測するだけで実行することが可能である。
【０１２２】
【数７】
0005601277.tif 000008
【０１２３】
ここで、図１２は、実施例２に係るインデックス検索の一例を説明するための図（２）である。図１２中（Ａ）は、対応参照ポイントを示し、図１２中（Ｂ）は、クエリデータを示す。また、図１２中（Ｃ）は、対応参照ポイントからｒｉｍａｘの範囲を示し、図１２中（Ｄ）は、クエリデータからＵの範囲を示す。また、図１２中（Ｅ）は、対応参照ポイント以外の参照ポイントを示し、図１２中（Ｆ）は、図１２中（Ｅ）に示す参照ポイントについて、式（７）の条件にあてはまらない範囲を示す。
【０１２４】
つまり、情報処理装置１０ａは、各参照ポイントについて、対応付けられた登録データが式（７）を満たすか否かを判別する。この結果、各参照ポイントについて対応付けられた登録データが式（７）を満たさない範囲とは、各参照ポイントを中心とするドーナツ状の範囲が重なり合う部分となるため、近傍候補となる登録データは、図１２中網掛けをした範囲に含まれる登録データとなる。
【０１２５】
次に、情報処理装置１０ａ、各参照ポイントについて、インデックスに登録しておいた登録データと各参照ポイントとの内積値を用いた枝刈りを実行する。具体的には、情報処理装置１０ａは、以下の式（８）および式（９）の条件を満たす登録データを近傍候補から除外する。なお、以下の式における「ｕ」は、長さが近傍範囲Ｕと等しい任意のベクトルを示す。
【０１２６】
【数８】
0005601277.tif 000009
【０１２７】
【数９】
0005601277.tif 000010
【０１２８】
また、式（８）、式（９）を書換えると、以下の式（１０）、式（１１）となる。つまり、情報処理装置１０ａは、式（１０）および式（１１）の条件を満たす登録データを近傍候補から除外することができる。
【０１２９】
【数１０】
0005601277.tif 000011
【０１３０】
【数１１】
0005601277.tif 000012
【０１３１】
なお、式（１１）中のθｐは、登録データｐを示すベクトルと参照ポイントｏｉを示すベクトルとの間の角度を示し、θｑは、クエリデータｑを示すベクトルと参照ポイントｏｉを示すベクトルとの間の角度を示す。また、θｕは、任意のベクトルｕと参照ポイントｏｉを示すベクトルとの間の角度を示す。
【０１３２】
ここで、任意のベクトルｕの方向は任意であるため、「ｃｏｓθｕ＝１」とした際に、以下の式（１２）が成り立つ場合には、任意のｕについて式（１０）および式（１１）が成り立つ。つまり、情報処理装置１０ａは、式（１２）を満たす登録データについて近傍候補から除外することが可能である。
【０１３３】
【数１２】
0005601277.tif 000013
【０１３４】
なお、情報処理装置１０ａは、インデックスに登録された内積「＜ｏｉ,ｐ＞＝｜ｏｉ｜｜ｐ｜ｃｏｓθｐ」から「｜ｐ｜ｃｏｓθｐ」を容易に算出することができる。また、情報処理装置１０ａは、「｜ｑ｜ｃｏｓθｑ」についても、検索処理実行時に各参照ポイントに対して１度だけ算出すればよい。
【０１３５】
つぎに、情報処理装置１０ａが参照ポイントを多次元空間内における原点を中心として、クエリデータと登録データとを通る平面と平行な面上を「α」だけ回転させる処理について説明する。このような場合には、式（１２）中の「θｐ」を「θｐ±α」とし、「θｑ」を「θｑ±α」とすればよい。このため、式（１２）は、以下の式（１３）式に変形することができる。
【０１３６】
【数１３】
0005601277.tif 000014
【０１３７】
つまり、情報処理装置１０ａは、式（１３）を満たす登録データについては、近傍候補から除外することができる。ここで、式（１３）の左辺が最大となる「α」を考えるため、式（１３）を「α」で微分した式を考えると、近傍範囲「Ｕ」は「α」の変化によって変化しないと考えられるため、「ｄＵ／ｄα＝０」となる。この結果、式（１３）は、以下の式（１４）に変形することができる。
【０１３８】
【数１４】
0005601277.tif 000015
【０１３９】
この式（１４）を「α」について解くと、以下の式（１５）を得ることができる。
【０１４０】
【数１５】
0005601277.tif 000016
【０１４１】
つまり、「α」が式（１５）を満たす場合には、式（１３）の左辺が最大となるので、この式（１５）を満たす「α」の際に式（１３）の条件を満たす登録データを近傍候補から除外した場合には、最も多くの登録データを近傍候補から除外することができる。
【０１４２】
ここで、図１３は、実施例２に係るインデックス検索の一例を説明するための図（３）である。図１３中（Ａ）は、対応参照ポイントを示し、図１３中（Ｂ）はクエリデータを示し、図１３中（Ｃ）は、対応参照データからｒｉｍａｘの範囲を示す。また、図１３中（Ｄ）は、Ｕが示す近傍範囲を示す。情報処理装置１０ａは、登録データと各参照ポイントとの内積値に基づいて枝刈りを実行した場合には、参照ポイントのベクトルに直交するような直線で囲まれる領域となる。このため、情報処理装置１０ａは、近傍候補を図１３中（Ｅ）で示す網掛けの範囲に含まれる登録データに限定することができる。
【０１４３】
ここで、近傍候補に対する枝刈りを効率良く行うためには、予め適切な位置に参照ポイントを設定する必要があるが、インデックスを作成する際にどのようなクエリデータが入力されるかを予測することは困難である。しかし、情報処理装置１０ａが生体認証を行うためのクエリデータと類似する登録データの近傍検索を行う場合には、登録対象データと類似する分布のデータがクエリデータとして入力されると考えることができる。このため、登録対象データの分布を用いて、効果的に枝刈りをおこなうための参照ポイントを定めることができる。
【０１４４】
例えば、情報処理装置１０ａは、距離に基づいて枝刈りされる登録データの数を増やすためには、以下の式（１６）を最大化させる参照ポイントの位置を算出し、算出した位置に参照ポイントを設定すればよい。
【０１４５】
【数１６】
0005601277.tif 000017
【０１４６】
また、情報処理装置１０ａは、内積値に基づいて枝刈りされる登録データの数を増やすためには、以下の式（１７）を最大化させる参照ポイントの位置を算出し、算出した位置に参照ポイントを設定すればよい。
【０１４７】
【数１７】
0005601277.tif 000018
【０１４８】
なお、［非特許文献１］は、式（１６）の式を最大化する参照ポイントを登録データから選択する方法を提案している。また、式（１７）についても、参照ポイントを「α」だけ回転させた場合を考慮して、枝刈りされる登録データの数が増えるように参照ポイントを設定しても良い。また、情報処理装置１０ａは、登録データのうち、式（１６）と式（１７）、または、式（１６）と式（１７）との重み付和を最大化する登録データを参照ポイントとして選択してもよい。また、情報処理装置１０ａは、登録データのうち、式（１６）と式（１７）、または、式（１６）と式（１７）との重み付和を最大化させる位置に参照ポイントを設定しても良い。
【０１４９】
［情報処理装置１０ａの処理の流れ］
次に、図１４を用いて、情報処理装置１０ａが新たなデータを登録する処理の流れの一例について説明する。図１４は、実施例２に係る登録処理の流れの一例を説明するためのフローチャートである。図１４に示す例では、情報処理装置１０ａは、データベース２１ａに登録するデータを受信したことをトリガとして、処理を開始する。
【０１５０】
まず、情報処理装置１０ａは、登録対象となるデータをデータベース２１ａに登録する（ステップＳ３０１）。また、情報処理装置１０ａは、新たな登録データの対応参照ポイントを算出する（ステップＳ３０２）。次に情報処理装置１０ａは、新たな登録データのキー値を算出し、新たな登録データと各参照ポイントとの距離と、新たな登録データの各参照ポイントとの内積値とをキー値と対応付けてインデックスに登録する（ステップＳ３０３）。
【０１５１】
次に、情報処理装置１０ａは、対応参照ポイントと新たな登録データとの距離が対応参照ポイントと対応付けられた距離の最大値よりも大きいか否かを判別する（ステップＳ３０４）。そして、情報処理装置１０ａは、対応参照ポイントと新たな登録データとの距離が対応参照ポイントと対応付けられた距離の最大値をよりも大きいと判別した場合には（ステップＳ３０４肯定）、以下の処理を実行する。すなわち、情報処理装置１０ａは、対応参照ポイントと対応付けられた距離の最大値を更新する（ステップＳ３０５）。その後、情報処理装置１０ａは、処理を終了する。
【０１５２】
一方、情報処理装置１０ａは、対応参照ポイントと新たな登録データとの距離が対応参照ポイントと対応付けられた距離の最大値をよりも小さいと判別した場合には（ステップＳ３０４否定）、そのまま処理を終了する。
【０１５３】
次に、図１５を用いて、情報処理装置１０ａが入力されたクエリデータの近傍データを検索する処理の流れの一例について説明する。図１５は、実施例２に係る検索処理の流れの一例を説明するためのフローチャートである。図１５に示す例では、情報処理装置１０ａは、クエリデータおよび近傍範囲を示す情報を取得したことをトリガとして、検索処理を開始する。
【０１５４】
まず、情報処理装置１０ａは、クエリデータと近傍範囲を示す情報とを取得する（ステップＳ４０１）。このような場合には、情報処理装置１０ａは、取得したクエリデータの近傍候補となる登録データと対応付けられた対応参照ポイントと、近傍候補となる登録データのキー値の範囲とを算出する（ステップＳ４０２）。次に、情報処理装置１０ａは、算出した範囲のキー値を用いて、近傍候補となる登録データをインデックスから検索する（ステップＳ４０３）。
【０１５５】
次に、情報処理装置１０ａは、検索したインデックスから取得される距離と内積値とを用いて近傍候補の枝刈りを実行する（ステップＳ４０４）。つまり、情報処理装置１０ａは、インデックスから取得された登録データと各参照ポイントとの距離を用いて、近傍候補の枝刈りを実行する。これとともに、情報処理装置１０ａは、インデックスから取得された登録データと各参照ポイントとの内積値を用いて、近傍候補の枝刈りを実行する。
【０１５６】
次に、情報処理装置１０ａは、枝刈りを行った近傍候補に含まれる各登録データについて、クエリデータとの距離を算出し、近傍データを確定する（ステップＳ４０５）。そして、情報処理装置１０ａは、確定した近傍データのリストを認証サーバ３に出力し（ステップＳ４０６）、処理を終了する。
【０１５７】
［実施例２の効果］
上述したように、情報処理装置１０ａは、複数の参照ポイントと登録データとの距離と、複数の参照ポイントと登録データとの内積値とをインデックスとしてあらかじめ記憶する。そして、情報処理装置１０ａは、インデックスを用いて検索した近傍候補の登録データから、インデックスとして予め記憶した複数の距離と複数の内積値とを用いた枝刈りを行う。
【０１５８】
具体的には、情報処理装置１０ａは、距離を用いた枝刈りを行う場合には、各参照ポイントについて、クエリデータから参照ポイントまでの距離と登録データから参照ポイントまでの距離との差が所定の近傍範囲内に収まるか否かを判別する。そして、情報処理装置１０ａは、クエリデータから参照ポイントまでの距離と登録データから参照ポイントまでの距離との差が所定の近傍範囲内に収まらないと判別した場合には、この登録データを近傍候補から除外する。
【０１５９】
また、情報処理装置１０ａは、内積値を用いた枝刈りを行う場合には、各参照ポイントについて、登録データと参照ポイントとの内積値からクエリデータと参照ポイントとの内積値を減じた値が所定の値以内に収まるか否かを判別する。ここで、所定の範囲内とは、近傍範囲と同じ大きさを有する任意のベクトルと参照ポイントとの内積値である。そして、情報処理装置１０ａは、各参照ポイントについて、登録データと参照ポイントとの内積値からクエリデータと参照ポイントとの内積値を減じた値が所定の値よりも大きいと判別した場合には、この登録データを近傍範囲から除外する。
【０１６０】
このため、情報処理装置１０ａは、距離を用いた枝刈りと内積値を用いた枝刈りとを併用した場合には、距離のみを用いた枝刈りよりも多くの登録データを近傍候補から除外することができる。つまり、情報処理装置１０ａは、従来の距離による三角不等式だけを値要する場合と比較して、より多くの登録データを近傍候補から除外する結果、クエリデータとの距離を算出する回数を削減し、より効率的に近傍検索を行う事ができる。
【０１６１】
また、情報処理装置１０ａは、近傍候補から除外される登録データの数が最大となるように、原点を中心として参照データを回転させる。そして、情報処理装置１０ａは、回転させた参照データを用いて、内積値を用いた枝刈りを実行する。このため、情報処理装置１０ａは、より多くの登録データを近傍候補から除外することができる。
【０１６２】
すなわち、情報処理装置１０ａは、内積値を用いた枝刈りを行った場合には、参照ポイントのベクトルに直交するような直線で囲まれる領域に含まれる登録データを近傍候補から除外する。ここで、原点を中心として参照ポイントを回転させた場合には、参照ポイントのベクトルに直交するような直線で囲まれる領域が移動することとなる。このため、情報処理装置１０ａは、もっとも効率的に枝刈りを行う事ができる参照データを用いて、内積値を用いた枝刈りを行う事ができる。
【実施例３】
【０１６３】
実施例３では、参照ポイントと登録データとの距離以外の情報をインデックスとして記憶することによって、近傍候補をさらに効率良く検索する情報処理装置１０ｂについて説明する。
【０１６４】
つまり、従来の近傍検索を行う技術は、インデックスに複数の参照ポイントと登録データとの距離をすべて保存していた。このため、登録データの数が多い場合には、参照ポイントの数が多い場合には、多くのデータをインデックスに登録する必要があるため、インデックスを記憶するための要する記憶容量が多くなるという問題があった。また、参照ポイントの数が多い場合には、クエリデータの近傍データと対応付けられた参照ポイントを検索するため、クエリデータと参照ポイントとの距離を算出する回数が多くなる。この結果、従来の近傍検索を行う技術では、近傍検索を行う際の計算コストが多くなり、適切な近傍検索を行う事ができないという問題があった。
【０１６５】
実施例３に開示の技術は、上述した問題に鑑みてなされたものであって、近傍検索を実行する際の計算コストを削減する。
【０１６６】
図１６は、実施例３に係る情報処理装置を説明するための図である。図１６に示す例では、情報処理装置１０ｂは、データ登録処理部２０ｂ、検索処理部３０ｂを有する。また、データ登録処理部２０ｂは、データベース２１ｂ、基準参照ポイント情報記憶部２２ａ、補助参照ポイント情報記憶部２２ｂ、インデックス記憶部２４ｂ、距離算出部２５、インデックス登録部２６ｂ、登録対応補助参照ポイント決定部２９を有する。また、検索処理部３０ｂは、インデックス検索範囲算出部３１、近傍データ確定部３３、インデックス検索部３２、対応補助参照ポイント決定部３６、候補枝刈り部３４ａを有する。
【０１６７】
なお、情報処理装置１０ｂが有する各部のうち、実施例１に係る情報処理装置１０、および実施例２に係る情報処理装置１０ａが有する各部と同様の処理を実行するものについては、同一の符号を付し、詳細な説明を省略する。また、以下の説明においては、情報処理装置１０ｂは、各登録データの誤差パラメータを考慮せずに、処理を実行するものとする。また、情報処理装置１０ｂは、実施例１に係る情報処理装置１０と同様に、生体データのマッチングを行う情報処理システム１ｂが有する情報処理装置である。
【０１６８】
データベース２１ｂは、登録データと、登録データと対応する補助参照ポイントを示す識別子と、登録データと対応する補助参照ポイントとの距離とを対応付けて記憶する。ここで、補助参照ポイントとは、近傍候補の枝刈りを行うために予め設定される参照ポイントである。
【０１６９】
基準参照ポイント情報記憶部２２ａは、予め設定される基準参照ポイントを記憶する。ここで、基準参照ポイントとは、実施例１、２に係る参照ポイントと同義である。つまり、基準参照ポイント情報記憶部２２ａは、実施例１、２に係る参照ポイント情報記憶部２２と同様の情報を記憶する。
【０１７０】
補助参照ポイント情報記憶部２２ｂは、予め設定される補助参照ポイントを記憶する。具体的には、補助参照ポイント情報記憶部２２ｂには、図１６中（Ａ）に示すように、予め設定された補助参照ポイントの位置（または、特徴量ベクトル）を示す情報が格納される。
【０１７１】
インデックス記憶部２４ｂは、登録データと対応基準参照ポイントとの距離に基づく値をキー値として、以下の情報をインデックスとして記憶する。すなわち、インデックス記憶部２４ｂは、登録データと、登録対応補助参照ポイント決定部２９によって選択された対応補助参照ポイントの識別子と、登録データと対応補助参照ポイントとの距離とをインデックスとして記憶する。
【０１７２】
ここで、図１７は、実施例３に関するインデックスの一例を説明するための図である。図１７に示す例では、インデックス記憶部２４ｂは、実施例１、２に係るインデックス記憶部２４、２４ａと同様の構成を有するインデックスを記憶する。つまり、図１７中（Ａ）に示すように、登録データと対応基準参照ポイントとの距離に基づくキー値を階層的に有する。また、インデックス記憶部２４ｂは、図１６中（Ｂ）に示すように、登録データと各対応補助参照ポイントの識別子（ＩＤ）と、登録データと各対応補助参照ポイントとの距離とを対応付けたインデックスを記憶する。
【０１７３】
図１６に戻って、距離算出部２５は、実施例１、２に係る距離算出部と同様に、データベース２１ｂに登録する登録対象データを受信した場合には、登録対象データと基準参照ポイント情報記憶部２２ａに記憶された各基準参照ポイントとの距離を算出する。
【０１７４】
登録対応補助参照ポイント決定部２９は、登録対象データと対応する複数の補助参照ポイントを選択し、選択した複数の補助参照ポイントをインデックス登録部２６に通知する。具体的には、登録対応補助参照ポイント決定部２９は、図１６中（Ｂ）に示すように、登録データを受信した場合には、補助参照ポイント情報記憶部２２ｂに記憶された補助参照ポイントから受信した登録データと対応する複数の補助参照ポイントを選択する。そして、登録対応補助参照ポイント決定部２９は、選択した複数の補助参照ポイントを示す識別子をインデックス登録部２６に通知する。
【０１７５】
また、登録対応補助参照ポイント決定部２９は、選択した各補助参照ポイントと登録対象データとの距離を算出し、算出した距離をインデックス登録部２６ｂに通知する。なお、この処理は、登録対応補助参照ポイント決定部２９が実行するのではなく、距離算出部２５に選択した補助参照ポイントの位置を通知し、登録データと通知した補助参照ポイントとの距離を算出されることによって実現しても良い。
【０１７６】
ここで、登録対応補助参照ポイント決定部２９は、登録データに近いと考えられる複数の補助参照ポイントを対応する補助参照ポイントとして選択する。換言すると、登録対応補助参照ポイント決定部２９は、登録データに近い複数の補助参照ポイントを近似的な近傍検索によって選択する。この補助参照ポイントの選択は厳密な近傍検索が要求されるわけではなく、近似的な近傍検索を利用することで、補助参照ポイントの選択を高速で行う事ができる。
【０１７７】
以下、補助参照ポイントを選択する処理の例として、基準参照ポイントを用いたインデックスを利用して補助参照ポイントを選択する例と、局所性鋭敏型ハッシュ（Locality  Sensitive  Hashing;  LSH）を利用して補助参照ポイントを選択する例とを説明する。
【０１７８】
まず、登録対応補助参照ポイント決定部２９が、基準参照ポイントを用いたインデックスを利用した補助参照ポイントを選択する例について説明する。登録対応補助参照ポイント決定部２９は、予め、各補助参照ポイントについて、最も近くに存在する基準参照ポイントを選択する。そして、登録対応補助参照ポイント決定部２９は、選択した基準参照ポイントと補助参照ポイントとの距離に基づく値をキー値とし、補助参照ポイントを示す識別子を記憶する補助参照ポイントインデックスを作成しておく。
【０１７９】
そして、登録対応補助参照ポイント決定部２９は、登録対象データを受信した場合には、受信した登録対象データと基準参照ポイントとの距離を算出する。そして、登録対応補助参照ポイント決定部２９は、補助参照ポイントと基準参照ポイントとの距離と、算出した登録対象データと基準参照ポイントとの距離との差が所定の範囲内に収まる補助参照ポイントを予め作成した補助参照ポイントインデックスを用いて選択する。その後、登録対応補助参照ポイント決定部２９は、補助参照ポイントインデックスから選択した補助参照ポイントの識別子を取得し、取得した識別子をインデックス登録部２６ａに通知する。
【０１８０】
なお、登録対応補助参照ポイント決定部２９は、補助参照ポイントインデックスを補助参照ポイント情報記憶部２２ｂに格納することとしてもよく、また、補助参照ポイントインデックスを後述する対応補助参照ポイント決定部３６に通知することとしてもよい。
【０１８１】
次に、登録対応補助参照ポイント決定部２９が、ＬＳＨを利用して補助参照ポイントを選択する例について説明する。ここで、ＬＳＨを利用して補助参照ポイント選択する処理とは、ハッシュ関数を用いて、近似的な近傍検索を行う処理である。このようなＬＳＨを利用した近傍検索には、以下の非特許文献３に記載された方法を初めとして、様々なバリエーションがある。なお、本実施例では、距離関数にユークリッド距離を考えるが、利用する距離関数に対応したＬＳＨであれば特に限定はしない。
【０１８２】
[非特許文献  ３]  M.  Datar,  N.  Immorlica,  P.  Indyk,  and  V.  S.  Mirrokni:  Locality-Sensitive  Hashing  Scheme  Based  on  p-Stable  Distributions,  Proceedings  of  the  twentieth  annual  symposium  on  Computational  geometry  (SCG  ‘04),  pp.253-262  (2004)
【０１８３】
例えば、登録対応補助参照ポイント決定部２９は、一様乱数を項に含むハッシュ関数を用いて、補助参照ポイントのハッシュ値を予め算出し、算出した補助参照ポイントのハッシュ値を格納したハッシュテーブルを作成する。そして、登録対応補助参照ポイント決定部２９は、ハッシュテーブルを作成した際に用いたハッシュ関数と同一のハッシュ関数を用いて登録データのハッシュ値を複数作成する。
【０１８４】
そして、登録対応補助参照ポイント決定部２９は、ハッシュテーブルを参照し、登録データから作成した複数のハッシュ値と同じハッシュ値が算出された補助参照ポイントを複数選択する。そして、登録対応補助参照ポイント決定部２９は、選択した補助参照ポイントを示す識別子をインデックス登録部２６に通知する。
【０１８５】
なお、登録対応補助参照ポイント決定部２９は、作成したハッシュテーブルを対応補助参照ポイント決定部３６に送信することとしてもよく、また、ハッシュテーブルを補助参照ポイント情報記憶部２２ｂに格納することとしてもよい。
【０１８６】
インデックス登録部２６ｂは、距離算出部２５が算出した登録対象データと対応基準参照ポイントとの距離を取得する。また、インデックス登録部２６ｂは、登録対応補助参照ポイント決定部２９が選択した補助参照ポイント、つまり各対応補助参照ポイントの識別子と、登録データと各補助参照ポイントとの距離とを取得する。そして、インデックス登録部２６ｂは、距離算出部２５から取得した距離からキー値を算出し、算出したキー値と対応付けて、登録対応補助参照ポイント決定部２９から通知された各補助参照ポイントの識別子および距離とをインデックスに追加する。
【０１８７】
インデックス検索範囲算出部３１は、実施例１、２と同様に、図１６中（Ｃ）、（Ｄ）に示すクエリデータと近傍範囲を示す情報とを取得した場合には、インデックス検索を行うキー値の範囲を算出する。そして、インデックス検索範囲算出部３１は、図１６中（Ｅ）に示すように、算出したキー値の範囲をインデックス検索部３２に通知する。
【０１８８】
インデックス検索部３２は、実施例１、２と同様に、インデックス検索範囲算出部３１からキー値の範囲を取得した場合には、インデックス記憶部２４ｂが記憶するインデックスから、取得したキー値の範囲を検索する。そして、インデックス検索部３２は、検索された範囲のキー値と対応付けて記憶された登録データと、各対応補助参照ポイントの識別子と、登録データと各対応補助参照ポイントとの距離とを取得する。その後、インデックス検索部３２は、取得した各情報を候補枝刈り部３４ａに送信する。
【０１８９】
対応補助参照ポイント決定部３６は、クエリデータの近傍にある補助参照ポイントを近似的に検索する。そして、対応補助参照ポイント決定部３６は、検索した補助参照ポイントを候補枝刈り部３４ａに送信する。
【０１９０】
ここで、対応補助参照ポイント決定部３６は、登録対応補助参照ポイント決定部２９と同様に、近似的な近傍検索を用いて、クエリデータに近いと考えられる補助参照ポイントを選択する。例えば、対応補助参照ポイント決定部３６は、クエリデータと各基準参照ポイントとの距離を算出し、近傍候補となる登録データの対応基準参照ポイントを判定する。
【０１９１】
そして、対応補助参照ポイント決定部３６は、対応基準参照ポイントとクエリデータとの距離をキー値として、登録対応補助参照ポイント決定部２９が作成した補助参照ポイントインデックスを検索する。そして、対応補助参照ポイント決定部３６は、図１６中（Ｆ）に示すように、補助参照ポイントインデックスを検索し結果取得された補助参照ポイントの識別子を候補枝刈り部３４ａに通知する。
【０１９２】
ここで、対応補助参照ポイント決定部３６は、ＬＳＨを利用した補助参照ポイントを選択しても良い。このような場合には、対応補助参照ポイント決定部３６は、登録対応補助参照ポイント２９と同様に、クエリデータのハッシュ値を算出する。そして、対応補助参照ポイント決定部３６は、算出したハッシュ値と同じハッシュ値が算出された補助参照ポイントを登録対応補助参照ポイント決定部２９が作成したハッシュテーブルから選択する。なお、このような場合には、対応補助参照ポイント決定部３６は、ハッシュテーブルを登録対応補助参照ポイント決定部２９から受信することとしてもよいし、補助参照ポイント情報記憶部２２ｂ等に格納されたハッシュテーブルを参照することとしてもよい。
【０１９３】
候補枝刈り部３４ａは、インデックス検索部３２から近傍候補となる登録データと各対応補助参照ポイントの識別子を取得する。また、候補枝刈り部３４ａは、対応補助参照ポイント決定部３６が選択した補助参照ポイントの識別子を取得する。このような場合には、候補枝刈り部３４ａは、インデックス検索部３２から取得した対応補助参照ポイントの識別子と対応補助参照ポイント決定部３６が選択した補助参照ポイントのうち、重複する補助参照ポイントを判別する。そして、候補枝刈り部３４ａは、判別した補助参照ポイントとクエリデータとの距離と、判別した補助参照ポイントと登録データとの距離との差が、所定の範囲内に収まるか否かを判別する。その後、候補枝刈り部３４ａは、各距離の差が所定の範囲内に収まらないと判別した場合には、登録データを近傍候補から除外する。
【０１９４】
その後、候補枝刈り部３４ａは、図１６中（Ｇ）に示すように、近傍候補から除外されなかった登録データを近傍データ確定部３３へ送信する。近傍データ確定部３３は、候補枝刈り部３４ａから受信した近傍候補について、クエリデータとの距離を算出し、近傍データを確定する。そして、近傍データ確定部３３は、図１６中（Ｈ）に示すように、確定した近傍データのリストを、認証サーバ３に送信する。
【０１９５】
このように、情報処理装置１０ｂは、各登録データの近傍と考えられる複数の補助参照ポイントとの距離をインデックスに記憶し、検索処理時にクエリデータに近いと考えられる補助参照ポイントだけを用いて近傍候補の枝刈りを行う。このため、情報処理装置１０ｂは、全参照ポイントとの距離を保存する場合に比べて、メモリ使用量を削減することができる。
【０１９６】
例えば、全参照ポイントとの距離を保存する方法で保存が必要な距離情報の数は、「参照ポイントの数×登録データの数」である。一方、実施例３で情報処理装置１０ｂが記憶する距離情報の数は、「登録データの数＋登録データの数×登録データの近傍補助参照ポイントの数」となる。ここで、近傍補助参照ポイントの数は、通常、登録データ数に比べて小さいので、距離情報の総数も全参照ポイントとの距離を保存する方法よりも少なくなる。このため、情報処理装置１０ｂは、メモリ使用量を削減する。
【０１９７】
また、例えば、全参照ポイントとの距離を保存する方法で検索時に必要な参照ポイントとの距離計算回数は、「参照ポイントの数」である。一方、実施例３で情報処理装置１０ｂが検索時に必要な参照ポイントとの距離計算回数は、「基準参照ポイントの数＋クエリデータの近傍補助参照ポイント数」となる。この距離計算回数は、基準参照ポイントと補助参照ポイントを合わせたものよりも小さい。このため、情報処理装置１０ｂは、近傍検索を実行する際の計算コストを削減し、効率的な近傍検索を行うことができる。
【０１９８】
例えば、登録対応補助参照ポイント決定部２９、対応補助参照ポイント決定部３６は、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路、またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などを適用する。
【０１９９】
次に数式を用いて、情報処理装置１０ｂが登録対象データｐを登録する処理の具体例について説明する。なお、以下の説明においては、実施例１、２と同様の記号を用いるものとする。また、各補助参照ポイントを「ｓ１〜ｓＮ」とし、補助参照ポイントの数を「Ｎ」とする。また、説明を簡単にするために、各登録データの誤差パラメータについては、考慮しないものとする。
【０２００】
以下の説明では、登録対象データに近いと考えられる補助参照ポイントのＩＤ集合をＸｐと定義する。上述したように、情報処理装置１０ｂがＸｐを求める処理としては、基準参照ポイントを用いたインデックスを利用する方法とＬＳＨを利用する方法とがある。このため、以下の説明においては、先に基準参照ポイントを用いたインデックスを利用する方法を説明し、次にＬＳＨを利用した方法を説明する。
【０２０１】
まず、準参照ポイントを用いたインデックスを利用する方法について説明する。まず、情報処理装置１０ｂは、予め各補助参照ポイントについて、最も近くにある基準参照ポイントｏｊを選択する。そして、以下の式（１８）を用いて、補助参照ポイントインデックスのキー値Ｋｓ（Ｓｉ）を生成し、補助参照ポイントインデックスを作成する。
【０２０２】
【数１８】
0005601277.tif 000019
【０２０３】
なお、式（１８）中のＣは定数である。このため、基準参照ポイントｏｊに対応する補助参照ポイントのキー値は［ｊ×Ｃ、（ｊ＋１）×Ｃ）の範囲に収まることとなる。
【０２０４】
その後、情報処理装置１０ｂは、作成した補助参照ポイントインデックスを用いて、登録対象データｐに近いと考えられる補助参照ポイントをＮｐ個検索し、対応補助参照ポイントのＩＤの集合Ｘｐを得る。つまり、情報処理装置１０ｂは、基準参照ポイントｏｉ（ｉ＝１〜Ｍ）と登録対象データｐとの距離ｄ（ｏｉ,ｐ）を算出する。そして、情報処理装置１０ｂは、以下の式（１９）を満たすｄ（ｏｉ,ｐ）を選択する。ここで、式（１９）中の「ｕｉｍａｘ」とは、基準参照ポイントｏｉと対応付けられた補助参照ポイントと基準参照ポイントｏｉとの距離のうち、最大の距離を示す。また、「ｔ」とは、補助参照ポイントを検索する範囲を示す。
【０２０５】
【数１９】
0005601277.tif 000020
【０２０６】
そして、情報処理装置１０ｂは、選択したｄ（ｏｉ,ｐ）に基づいて［ｄ（ｏｉ,ｐ）＋ｉ×Ｃ−Ｔ,ｄ（ｏｉ,ｐ）＋ｉ×Ｃ＋Ｔ］の範囲のキー値と対応付けて記憶された補助参照ポイントを補助参照ポイントインデックスから検索する。ここで、図（１８）中の「ｔ」を操作することで、検索される補助参照ポイントの個数が変化する。このため、情報相処理装置１０ｂは、検索された補助参照ポイントの数が検索結果の上限であるＮｐ個に達しない場合には、「ｔ」を大きくすることで、さらに補助参照ポイントを検索することとしてもよい。また、情報処理装置１０ｂは、Ｎｐ個よりも多くの補助参照ポイントを検索した場合には、検索された補助参照ポイントからＮｐ個の補助参照ポイントをランダムに選択し、選択した補助参照ポイントをＸｐとすることとしてもよい。また、検索された補助参照ポイントと登録対象データとの距離を計算し、厳密な近傍となる補助参照ポイントを取得してもよい。
【０２０７】
次に、ＬＳＨを利用してがＸｐを求める処理について説明する。例えば、情報処理装置１０ｂは、以下の式（２０）および式（２１）を用いて、登録対象データｐのハッシュ値ｇｊ（ｐ）をＬ個算出する。
【０２０８】
【数２０】
0005601277.tif 000021
【０２０９】
【数２１】
0005601277.tif 000022
【０２１０】
ここで、式（２１）中の「ａ」は、各座標地が平均０分散１の正規分布に従うランダムベクトルであり、「ｚ」は範囲が［０、ｗ］となる一様乱数である。情報処理装置１０ｂは、ハッシュ値ｇｊ（ｐ）を算出した場合には、算出したハッシュ値ｇｊ（ｐ）と同一のハッシュ値を有する補助参照ポイントをハッシュテーブルから検索する。
【０２１１】
ここで、ハッシュテーブルには、式（１９）および式（２０）と同様の式を用いて算出された補助参照ポイントのハッシュ値ｇｊ（ｓｉ）（ｉ＝１〜Ｍ、ｊ＝１〜Ｌ）が格納されているものとする。情報処理装置１０ｂは、このような近似近傍検索によって登録対象データｐの近傍となる補助参照ポイントを検索した場合には、高い確率で登録対象データｐの近傍となる補助参照ポイントを選択することができる。なお、情報処理装置１０ｂは、ＬＳＨを利用した場合には、ハッシュ値が一致するデータを探索するだけなので、距離計算を行う場合に比べて高速に実行することができる。
【０２１２】
次に、登録対象データをインデックスに登録する処理について説明する。例えば、情報処理装置１０ｂは、登録対象データｐと各基準参照ポイントｏｉ（ｉ＝１〜Ｍ）との距離ｄ（ｏｉ、ｐ）を算出する。そして、情報処理装置１０ｂは、ｄ（ｏｉ、ｐ）が最も小さい基準参照ポイントを対応基準参照ポイントｏｊとして選択する。
【０２１３】
次に、情報処理装置１０ｂは、以下の式（２２）を用いて、登録対象データｐのキー値Ｋ（ｐ）を算出する。
【０２１４】
【数２２】
0005601277.tif 000023
【０２１５】
次に、情報処理装置１０ｂは、算出したＫ（ｐ）をキーとして、登録対象データをインデックスに追加する。以下の説明では、インデックスに登録されたデータの集合を「Ｉｄａｔａ」と記載する。次に、情報処理装置１０ｂは、補助参照データインデックス又はＬＳＨを用いて選択した集合Ｘｐに含まれる補助参照ポイントと登録対象データｐとの距離｛ｄ（ｓｉ,ｐ）｜ｉ∈Ｘｐ｝をｐとともにインデックスに登録する。また、情報処理装置１０ｂは、基準参照ポイントｏｊに対応する登録データのうち基準参照ポイントｏｊとの距離が最大のものの距離をｒｊｍａｘとしてインデックスに保存しておく。
【０２１６】
次に、図１８、図１９および数式を用いて、情報処理装置１０ｂがクエリデータの近傍データを検索する処理について説明する。まず、情報処理装置１０ｂは、各基準参照ポイントｏｉ（ｉ＝１〜Ｍ）とクエリデータｑとの距離ｄ（ｏｉ,ｑ）を算出し、ｏｉと対応付けられた登録データが近傍候補になるかを以下の式（２３）を用いて判別する。
【０２１７】
【数２３】
0005601277.tif 000024
【０２１８】
次に、情報処理装置１０ｂは、基準参照ポイントｏｉについてキーの値が［ｄ（ｏｉ,ｐ）＋ｉ×Ｃ−Ｕ,  ｄ（ｏｉ,ｐ）＋ｉ×Ｃ＋Ｕ］の範囲となる登録データをインデックスＩｄａｔａから検索し、検索した登録データを近傍候補の集合Ｙとする。このような集合Ｙは、図１８に示す網掛けをした丸印となる。ここで、図１８は、実施例３に係る補助参照ポイント選択処理の一例を説明するための図である。図１８中（Ａ）は基準参照ポイントを示し、図１８中（Ｂ）はクエリデータを示し、図１８中（Ｃ）は、近傍範囲Ｕを示す。また、図１８中網がけした丸印は、近傍候補の集合Ｙに含まれる登録データであり、Ｘマークは補助参照ポイントを示す。
【０２１９】
次に情報処理装置１０ｂは、クエリデータｑに近いと考えられる補助参照ポイントの集合Ｘｑを検索する。例えば、情報処理装置１０ｂは、基準参照ポイントを用いたインデックスを利用する場合には、各基準参照ポイントｏｉ（ｉ＝１〜Ｍ）とクエリデータｑの距離ｄ（ｏｉ,ｑ）を算出し、ｏｉにと対応付けられた補助参照ポイントがｑの近傍候補になるかを以下の式（２４）を用いて判別する。
【０２２０】
【数２４】
0005601277.tif 000025
【０２２１】
ここで、式（２３）中「ｕｉｍａｘ」は、補助参照ポイントインデックスＩｓｕｂにおいて参照ポイントｏｉと対応付けられた補助参照ポイントのうち、参照ポイントｏｉとの距離が最大の補助参照ポイントと参照ポイントｏｉとの距離である。なお、ｔは補助参照ポイントについての近傍範囲を示す値であるが「ｔ＝Ｕ」としてもよい。
【０２２２】
次に、情報処理装置１０ｂは、補助参照ポイントインデックスＩｓｕｂからキーの値が［ｄ（ｏｉ,ｑ）＋ｉ×Ｃ−ｔ,  ｄ（ｏｉ,ｑ）＋ｉ×Ｃ＋ｔ］の範囲となる補助参照ポイントを最大Ｎｑ個検索する。そして、情報処理装置１０ｂは、検索した補助参照ポイントの集合をＸｑとする。このような場合には、情報処理装置１０ｂは、図１８中のＸマークで示す補助参照ポイント、つまり、対応基準参照ポイントを中心としたドーナツ状の範囲に含まれる補助参照ポイントを検索することとなる。
【０２２３】
なお、情報処理装置１０ｂは、Ｎｑ個よりも多くの補助参照ポイントを検索した場合には、検索された補助参照ポイントからＮｑ個の補助参照ポイントをランダムに選択し、選択した補助参照ポイントをＮｑ個とすることとしてもよい。
【０２２４】
一方、情報処理装置１０ｂは、ＬＳＨを用いて補助参照ポイントを検索する場合には、クエリデータｑを用いてハッシュ値ｇｊ（ｑ）をＬ個（ｊ＝１〜Ｌ）算出する。そして、情報処理装置１０ｂは、算出したハッシュ値ｇｊ（ｑ）と同一のハッシュ値を有する補助参照ポイントをハッシュテーブルから最大Ｎｑ個選択し、選択した補助参照ポイントの集合をＸｑとする。
【０２２５】
次に、情報処理装置１０ｂが補助参照ポイントを用いて枝刈りを行う処理の一例を説明する。まず、情報処理装置１０ｂは、補助参照ポイント｛ｓｉ｜ｉ∈Ｘｑ｝とクエリデータｑとの距離ｄ（ｓｉ,ｑ）を算出する。また、情報処理装置１０ｂは、近傍候補の登録データから｛ｓｉ｜ｉ∈Ｘｑ｝との距離が所定の範囲内となる登録データについて、以下の式（２５）を満たすか否かを判別し、満たす場合には、近傍候補から除外する。
【０２２６】
【数２５】
0005601277.tif 000026
【０２２７】
ここで、図１９は、実施例３に係る補助参照ポイントによる枝刈りの一例を説明するための図である。図１９に示す（Ａ）は、対応基準参照ポイント、図１９中（Ｂ）は、クエリデータ、図１９中（Ｃ）は、近傍範囲を示す。情報処理装置１０ｂは、式（２４）を満たす登録データを近傍範囲から除外した場合には、図１９中網掛けをした丸印で示す登録データのみを近傍候補とする。このように、情報処理装置１０ｂは、検索された補助参照ポイントと近傍候補として検索された登録データの距離がデータ登録時に保存されていたとすると、図１９のように近傍候補のほとんどのデータが式(２５)を満たすと容易に判別することができる。このため、情報処理装置１０ｂは、近傍候補の枝刈りを容易に行う事ができる。
【０２２８】
［情報処理装置１０ｂが実行する処理の流れ］
次に、図２０を用いて、情報処理装置１０ｂが新たなデータを登録する処理の流れの一例について説明する。図２０は、実施例３に係る登録処理の流れの一例を説明するためのフローチャートである。図１４に示す例では、情報処理装置１０ｂは、データベース２１ｂに登録するデータを受信したことをトリガとして、処理を開始する。
【０２２９】
まず、情報処理装置１０ｂは、登録対象データをデータベース２１ｂに登録する（ステップＳ５０１）。また、情報処理装置１０ｂは、新たな登録データと対応する補助参照ポイントを算出する（ステップＳ５０２）。次に情報処理装置１０ｂは、対応基準参照ポイントを選択する（ステップＳ５０３）。
【０２３０】
次に、情報処理装置１０ｂは、登録対象データのキー値を算出し、インデックスに登録データと対応する補助参照ポイントのＩＤと補助参照ポイントとの距離とを登録する（ステップＳ５０４）。また、情報処理装置１０ｂは、対応基準参照ポイントと新たな登録データとの距離が対応基準参照ポイントと対応付けられた距離の最大値よりも大きいか否かを判別する（ステップＳ５０５）。そして、情報処理装置１０ｂは、対応基準参照ポイントと新たな登録データとの距離が対応基準参照ポイントと対応付けられた距離の最大値をよりも大きいと判別した場合には（ステップＳ５０５肯定）、以下の処理を実行する。すなわち、情報処理装置１０ｂは、対応基準参照ポイントと対応付けられた距離の最大値を更新する（ステップＳ５０６）。その後、情報処理装置１０ｂは、処理を終了する。
【０２３１】
一方、情報処理装置１０ｂは、対応基準参照ポイントと新たな登録データとの距離が対応基準参照ポイントと対応付けられた距離の最大値をよりも小さいと判別した場合には（ステップＳ５０５否定）、そのまま処理を終了する。
【０２３２】
次に、図２１を用いて、情報処理装置１０ｂが入力されたクエリデータの近傍データを検索する処理の流れの一例について説明する。図２１は、実施例３に係る検索処理の流れの一例を説明するためのフローチャートである。図２１に示す例では、情報処理装置１０ｂは、クエリデータおよび近傍範囲を示す情報を取得したことをトリガとして、検索処理を開始する。
【０２３３】
まず、情報処理装置１０ｂは、クエリデータと近傍範囲を示す情報とを取得する（ステップＳ６０１）。このような場合には、情報処理装置１０ｂは、取得したクエリデータの近傍候補となる登録データと対応付けられた対応基準参照ポイントと、近傍候補となる登録データのキー値の範囲とを算出する（ステップＳ６０２）。次に、情報処理装置１０ｂは、算出した範囲のキー値を用いて、近傍候補となる登録データをインデックスから検索する（ステップＳ６０３）。
【０２３４】
次に、情報処理装置１０ｂは、クエリデータの近傍となる補助参照ポイントを検索する（ステップＳ６０４）。そして、情報処理装置１０ｂは、インデックスから取得される補助参照ポイントと検索した補助参照ポイントとを用いて、近傍候補の枝刈りを実行する（ステップＳ６０５）。次に、情報処理装置１０ｂは、枝刈りをした近傍候補に含まれる各登録データについてクエリデータとの距離を算出し、近傍データの確定を行う（ステップＳ６０６）。その後、情報処理装置１０ｂは、確定した近傍データのリストを認証サーバ３に出力し（ステップＳ６０７）、処理を終了する。
【０２３５】
［実施例３の効果］
上述したように、情報処理装置１０ｂは、近似的な近傍検索を用いて、登録データの近傍にある補助参照ポイントを検索する。そして、情報処理装置１０ｂは、登録データと、検索した補助参照ポイントと、検索した補助参照ポイントと登録データとの距離とを対応付けてインデックスに登録する。また、情報処理装置１０ｂは、クエリデータの近傍候補となる登録データを検索し、検索された登録データと対応付けられた補助参照ポイントと、クエリデータの近傍となる補助参照ポイントとを用いて、近傍候補の枝刈りを行う。
【０２３６】
つまり、情報処理装置１０ｂは、各登録データの近傍と考えられる複数の補助参照ポイントとの距離をインデックスに記憶し、検索処理時にクエリデータに近いと考えられる補助参照ポイントだけを用いて近傍候補の枝刈りを行う。このため、情報処理装置１０ｂは、全参照ポイントとの距離を保存する場合に比べて、メモリ使用量を削減することができる。
【０２３７】
また、情報処理装置１０ｂは、近似的な近傍検索を利用して、クエリデータに近い補助参照ポイントを検索するので、高速にクエリデータに近い補助参照ポイントを取得することができる。また、情報処理装置１０ｂは、登録データに近い補助参照ポイントとクエリデータに近い補助参照ポイント、つまり、適切な参照ポイントを選択することで、効率的な近傍候補の枝刈りを行う事ができる。
【０２３８】
また、情報処理装置１０ｂは、補助参照ポイントの選択にだけ近似的な近傍検索を使用し、近傍データの確定を行う場合には、クエリデータと登録データとの距離を算出するので、最終的な近傍検索結果の厳密性を保証する。
【実施例４】
【０２３９】
これまで本発明の実施例について説明したが実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例４として本発明に含まれる他の実施例を説明する。
【０２４０】
（１）情報処理装置１０について
上述した情報処理装置１０は、各登録データごとに誤差パラメータを対応付けてデータベース２１に記憶するとともに、インデックスにも登録データと誤差パラメータとを対応付けて登録していた。しかし、実施例はこれに限定されるものではない。
【０２４１】
すなわち、情報処理装置１０は、各登録データごとに対応付けた誤差パラメータを考慮して近傍検索を行った場合には、バラつきが大きな登録データを適切に検索することができる。このため、情報処理装置１０は、インデックスを用いた近傍候補の選択を行わずに、誤差パラメータを考慮した線形検索を行うことによってもバラつきが大きな登録データを適切に検索することができる。
【０２４２】
（２）情報処理システムについて
上述した実施例１〜３においては、生体認証を行う認証システムが有する情報処理装置１０〜１０ｂについて説明した。しかし、実施例はこれに限定されるものではなく、近傍検索が必要となる任意のシステムに対して、情報処理装置１０〜１０ｂを適用することができる。
【０２４３】
（３）枝刈りについて
上述した情報処理装置１０ａ、１０ｂは、インデックスに登録された情報を用いて、枝刈りを行っていた。しかし、実施例はこれに限定されるものではなく、他にも一般的に用いられる枝刈りの手法を併用することで、さらに効率的な近傍検索を行うこととしてもよい。
【０２４４】
（４）対応参照ポイントの回転について
上述した情報処理装置１０ａは、枝刈りする登録データの数が最も多くなるように原点を中心として対応参照ポイントの回転させていた。しかし、この処理は必須の処理ではないため、行わないこととしてもよい。
【０２４５】
（５）登録データについて
情報処理装置１０は、生体データを登録データとしてデータベース２１に記憶するが、生体データは、データを登録してから年月が経過すると、生体情報に変化が生じ、クエリデータとして入力される生体データとの差が大きくなるとも考えられる。このため、情報処理装置１０は、登録データが登録されてからの年月に応じて、各登録データの誤差パラメータを補正することとしてもよい。
【符号の説明】
【０２４６】
１  情報処理システム
２  クライアント装置
３  認証サーバ
１０  情報処理装置
２０〜２０ｂ  データ登録処理部
２１〜２１ｂ  データベース
２２  参照ポイント情報記憶部
２２ａ  基準参照ポイント情報記憶部
２２ｂ  補助参照ポイント情報記憶部
２３  最大誤差情報記憶部
２４〜２４ｂ  インデックス記憶部
２５  距離算出部
２６  インデックス登録部
２７  内積算出部
２９  登録対応補助参照ポイント決定部
３０〜３０ｂ  検索処理部
３１  インデックス検索範囲算出部
３２  インデックス検索部
３３  近傍データ確定部
３４、３４ａ  候補枝刈り部
３６  対応補助参照ポイント決定部
【図１】
0005601277.tif 000027
【図２】
0005601277.tif 000028
【図３】
0005601277.tif 000029
【図４】
0005601277.tif 000030
【図５】
0005601277.tif 000031
【図６】
0005601277.tif 000032
【図７】
0005601277.tif 000033
【図８】
0005601277.tif 000034
【図９】
0005601277.tif 000035
【図１０】
0005601277.tif 000036
【図１１】
0005601277.tif 000037
【図１２】
0005601277.tif 000038
【図１３】
0005601277.tif 000039
【図１４】
0005601277.tif 000040
【図１５】
0005601277.tif 000041
【図１６】
0005601277.tif 000042
【図１７】
0005601277.tif 000043
【図１８】
0005601277.tif 000044
【図１９】
0005601277.tif 000045
【図２０】
0005601277.tif 000046
【図２１】
0005601277.tif 000047
【図２２】
0005601277.tif 000048
【図２３】
0005601277.tif 000049