(57)【要約】【課題】  ベクトルの次元数が高次元な場合に、クエリのベクトルと大規模なベクトルDBとの近傍探索処理を、GPUデバイスに代表されるメニーコア演算器の並列演算能力の高さに着目し、kNNグラフを用いて高精度かつ高速な探索処理を実現する。【解決手段】  本発明は、kNNグラフ構築時の枝数Nより少ない枝数Mでグラフを探索し、グラフ探索終了後のノードについて、kNNグラフ構築時の枝数の枝ノードとクエリ間の並列距離計算を行い、クエリから最短距離のノードを選択する。【選択図】  図３
2014074959.tif 000002
【特許請求の範囲】
【請求項１】
kNN（k-Nearest Neighbor）グラフ構造を用いてベクトル群の近傍探索を行う近傍探索処理装置であって、
枝数Ｎ本の前記kNNグラフを構築し、グラフ探索開始ノードを現ノードとする事前処理手段と、
前記現ノードの枝Ｎ本のうち、該現ノードから距離が近いＭ本を選択して、該現ノードと該Ｍ本のノードとの距離を計算する距離計算手段と、
前記距離計算手段で得られた距離計算結果から、入力されたクエリから最短距離のノードを選択する最短距離ノード選択手段と、
選択された前記最短距離のノードが前記現ノードと等しくない場合は、該最短距離のノードにホップし、前記距離計算手段及び前記最短距離ノード選択手段を実行するグラフ探索手段と、
前記選択された前記最短距離のノードが等しい場合は、該現ノードから距離が遠いN−M個の枝ノードに対応するベクトルＩＤを選択し、該N−M個の枝ノードに対応するベクトル群と前記クエリのベクトルの並列距離計算を行い、該現ノード及び該N−M個の枝ノードと前記クエリ間の距離のN−M+1個の計算結果より、該クエリから最短距離のノードを選択する最近傍ベクトル抽出手段と、
を有することを特徴とする近傍探索処理装置。
【請求項２】
ベクトル群を格納したベクトル記憶手段と、
GPUデバイスと、
前記ベクトル記憶手段の前記ベクトル群のデータを、前記GPUデバイスに転送する手段と、
を更に有し、
前記最近傍ベクトル抽出手段は、
選択した前記ベクトルＩＤを前記GPUデバイスに転送し、前記N−M個の枝ノードに対応するベクトル群と前記クエリのベクトルの並列距離計算結果を該GPUデバイスから取得する手段を含み、
前記GPUデバイスは、
前記ベクトルＩＤに基づいて前記ベクトル群のデータを参照して、該ベクトルＩＤに対応するベクトル群と前記クエリのベクトルの並列距離計算を行う並列距離計算手段を含む
請求項１記載の近傍探索処理装置。
【請求項３】
メニーコア演算器を更に有し、
前記最近傍ベクトル抽出手段は、
前記選択された前記最短距離のノードが等しい場合は、前記メニーコア演算器に対して
前記現ノードから距離が遠いN−M個の枝ノードに対応するベクトル群と前記クエリベクトルの並列距離計算を指示し、計算結果を取得する並列距離計算指示手段を含み、
前記メニーコア演算器は、
前記現ノードから距離が遠いN−M個の枝ノードに対応するベクトル群と前記クエリベクトルの並列距離計算を行う手段を含む
請求項１記載の近傍探索処理装置。
【請求項４】
kNN（k-Nearest Neighbor）グラフ構造を用いてベクトル群の近傍探索を行う近傍探索処理方法であって、
事前処理手段、距離計算手段、最短距離ノード選択手段、グラフ探索手段、最近傍ベクトル抽出手段を有する装置において、
前記事前処理手段が、枝数Ｎ本の前記kNNグラフを構築し、グラフ探索開始ノードを現ノードとする事前処理ステップと、
前記距離計算手段が、前記現ノードの枝Ｎ本のうち、該現ノードから距離が近いM（N＞M）本を選択して、該現ノードと該Ｍ本のノードとの距離を計算する距離計算ステップと、
前記最短距離ノード選択手段が、前記距離計算ステップで得られた距離計算結果から、入力されたクエリから最短距離のノードを選択する最短距離ノード選択ステップと、
前記グラフ探索手段が、前記最短距離ノード選択ステップで選択された前記最短距離のノードが前記現ノードと等しくない場合は、該最短距離のノードにホップし、前記距離計算ステップ及び前記最短距離ノード選択ステップを行うグラフ探索ステップと、
前記最近傍ベクトル抽出手段が、前記グラフ探索ステップで前記選択された前記最短距離のノードが等しい場合は、該現ノードから距離が遠いN−M個の枝ノードに対応するベクトルＩＤを選択し、該N−M個の枝ノードに対応するベクトル群と前記クエリのベクトルの並列距離計算を行い、該現ノード及び該N−M個の枝ノードと前記クエリ間の距離のN−M+1個の計算結果より、該クエリから最短距離のノードを選択する最近傍ベクトル抽出ステップと、
を行うことを特徴とする近傍探索処理方法。
【請求項５】
ベクトル群を格納したベクトル記憶手段と、
GPUデバイスと、
を更に有する装置において、
前記ベクトル記憶手段のベクトル群のデータを前記GPUデバイスに転送するステップを更に行い、
前記最近傍ベクトル抽出ステップにおいて、
選択した前記ベクトルＩＤを前記GPUデバイスに転送し、
前記GPUデバイスにおいて、
前記ベクトルＩＤに基づいて前記ベクトル群のデータを参照して、該ベクトルＩＤに対応するベクトル群と前記クエリのベクトルの並列距離計算を行う
請求項４記載の近傍探索処理方法。
【請求項６】
メニーコア演算器を更に有する装置において、
前記最近傍ベクトル抽出ステップにおいて、
前記選択された前記最短距離のノードが等しい場合は、前記メニーコア演算器が、前記現ノードから距離が遠いN−M個の枝ノードに対応するベクトル群と前記クエリベクトルの並列距離計算を行う
請求項４記載の近傍探索処理方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載の近傍探索処理装置の各手段として機能させるための近傍探索処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、近傍探索処理装置及び方法及びプログラムに係り、特に、ベクトルの次元数が高次元な場合に、クエリのベクトルと、大規模なベクトルデータベースの近傍探索処理を、GPU(Graphics Processing Unit)デバイスに代表されるメニーコア演算器の並列演算能力の高さに着目し、kNN（k-Nearest Neighbor）グラフを用いて実現するための近傍探索処理装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
ベクトルの次元数が高次元な場合に、クエリのベクトルと大規模なベクトルDBとの近傍探索処理をGPUデバイスに代表されるメニーコア演算器の並列演算能力の高さに着目し、高精度かつ高速な探索処理をkNNグラフを用いて行う方法として以下のような方法がある。ここで、kNNグラフとは、最近傍検索のためのアルゴリズムであり、各ノードが最も近いｋ個のノードと辺で結ぶ。グラフが無向グラフである場合、各ノードの次数はｋである。
【０００３】
[従来技術１]
ホストコンピュータのみで、kNNグラフを用いた近傍探索がある（例えば、非特許文献1参照）。
【０００４】
従来技術1の処理のフローチャートを図1に示す。
【０００５】
当該技術の近傍探索では、kNNグラフを構築した時の枝数をグラフ探索に利用する。クエリは、現ノードとの距離計算とその枝ノード群との距離計算を繰り返して行い（ステップ４〜７）、クエリから最短距離のノードを選択する（ステップ８）。そして、最短距離ノードが、現ノードであれば、そのノード最近傍として出力する（ステップ１０）。一方、最短距離ノードが、現ノード以外であれば、最短距離ノードにホップして（ステップ９）、ホップ先ノードを現ノードにして、グラフ探索を再開する（ステップ４〜９）。
【０００６】
この探索では、枝数をパラメータとして、速度と精度を調整することができるが、速度を重視すると、枝数を減らす必要があるため、精度が低下してしまう問題がある。
【０００７】
[従来技術２]
さらに、kNNグラフをホップする際の条件判定をするために行うベクトル間の距離計算をGPUデイバスで並列化した方法がある。
【０００８】
従来技術２の処理を図2に示す。
【０００９】
この方法は、ホストコンピュータとGPUデバイスを利用して、kNNグラフを用いた近傍探索を行う。当該近傍探索では、kNNグラフを構築したときの枝数をグラフ探索に利用する。クエリは、GPUデバイスにて、現ノードとその枝ノード群との並列距離計算をして、計算結果をホストコンピュータに転送する（ステップ１６）。ホストコンピュータでは、クエリから最短距離のノードを選択してホストコンピュータに転送する（ステップ１７，１８）。そして、ホストコンピュータ側では最短距離ノードが、現ノードであれば、そのノードを最近傍として出力する（ステップ１９，２１）。一方、最短距離ノードが、現ノード以外であれば、最短距離ノードにホップして（ステップ２０）、ホップ先ノードを現ノードにして、グラフ探索を再開する（ステップ１６〜２０）。
【００１０】
このグラフ探索では、枝数をパラメータとして、速度と精度を調整することができるが、速度を重視すると、枝数を減らす必要があるため、精度が低下してしまう。距離計算をGPUデバイスで並列処理を行うことにより、精度向上のために枝数を増やしても距離計算速度を高速化することが可能になる。しかし、ホップする度に現ノードとその枝ノード群のベクトルデータをGPUデバイスに転送する処理が発生するために、転送処理による速度低下が問題となる。
【００１１】
[従来技術３]
また、クエリのベクトルが全ベクトルDBとGPUを用いて並列距離計算する方法がある。これは、GPUを用いたユークリッド距離計算を並列化した全探索が挙げられる。全探索はクエリのベクトルとDB側の距離計算を１つずつ行い、計算結果から最小の値を求めるので、厳密な探索処理が可能となる。さらに、GPUで並列化処理をしているので、CPUの逐次処理に対しては高速な処理が可能となる。
【００１２】
しかし、全探索では、１つずつ距離計算を行っていくため、例えば、GPUを用いて並列処理をしたとしても、従来技術１，２と比較すると処理速度が遅いという問題がある。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Metric-based Shape Retrieval in Large Database(ファイル形式pdf).
【発明の概要】
【発明が解決しようとする課題】
【００１４】
上記のように、大規模な高次元ベクトル群の高速な最近傍探索方法としては、kNNグラフ構築時の枝数で近似最近傍探索処理を用いる技術は存在したが、従来技術1のようにホストのみを用いた探索では、枝数が少ない場合、高速な探索が可能となるが、精度を確保するには枝数を増やす必要があり、そうなると速度が低下するという問題がある。
【００１５】
また、従来技術２のように、距離計算をGPUデバイスで並列化した場合でも、GPUデバイスによる並列距離計算で多数の枝を高速に距離計算でき、精度を上げることができるが、ホップ度にホスト−GPUデバイス間の転送が発生するので、処理速度が低下する。
【００１６】
本発明は、上記の点に鑑みなされたもので、ベクトルの次元数が高次元な場合に、クエリのベクトルと大規模なベクトルDBとの近傍探索処理を、GPUデバイスに代表されるメニーコア演算器の並列演算能力の高さに着目し、kNNグラフを用いて高精度かつ高速な探索処理を実現することが可能な近傍探索処理装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
上記の課題を解決するため、本発明（請求項１）は、kNN（k-Nearest Neighbor）グラフ構造を用いてベクトル群の近傍探索を行う近傍探索処理装置であって、
枝数Ｎ本の前記kNNグラフを構築し、グラフ探索開始ノードを現ノードとする事前処理手段と、
前記現ノードの枝Ｎ本のうち、該現ノードから距離が近いＭ本を選択して、該現ノードと該Ｍ本のノードとの距離を計算する距離計算手段と、
前記距離計算手段で得られた距離計算結果から、入力されたクエリから最短距離のノードを選択する最短距離ノード選択手段と、
選択された前記最短距離のノードが前記現ノードと等しくない場合は、該最短距離のノードにホップし、前記距離計算手段及び前記最短距離ノード選択手段を実行するグラフ探索手段と、
前記選択された前記最短距離のノードが等しい場合は、該現ノードから距離が遠いN−M個の枝ノードに対応するベクトルＩＤを選択し、該N−M個の枝ノードに対応するベクトル群と前記クエリのベクトルの並列距離計算を行い、該現ノード及び該N−M個の枝ノードと前記クエリ間の距離のN−M+1個の計算結果より、該クエリから最短距離のノードを選択する最近傍ベクトル抽出手段と、を有する。
【００１８】
また、本発明（請求項２）は、ベクトル群を格納したベクトル記憶手段と、GPUデバイスと、前記ベクトル記憶手段の前記ベクトル群のデータを、前記GPUデバイスに転送する手段と、を更に有し、
前記最近傍ベクトル抽出手段は、
選択した前記ベクトルＩＤを前記GPUデバイスに転送し、前記N−M個の枝ノードに対応するベクトル群と前記クエリのベクトルの並列距離計算結果を該GPUデバイスから取得する手段を含み、
前記GPUデバイスは、
前記ベクトルＩＤに基づいて前記ベクトル群のデータを参照して、該ベクトルＩＤに対応するベクトル群と前記クエリのベクトルの並列距離計算を行う並列距離計算手段を含む。
【００１９】
また、本発明（請求項３）は、メニーコア演算器を更に有し、
前記最近傍ベクトル抽出手段は、
前記選択された前記最短距離のノードが等しい場合は、前記メニーコア演算器に対して
前記現ノードから距離が遠いN−M個の枝ノードに対応するベクトル群と前記クエリベクトルの並列距離計算を指示し、計算結果を取得する並列距離計算指示手段を含み、
前記メニーコア演算器は、
前記現ノードから距離が遠いN−M個の枝ノードに対応するベクトル群と前記クエリベクトルの並列距離計算を行う手段を含む。
【発明の効果】
【００２０】
上記のように本発明によれば、kNNグラフ構築時に探索用近傍ベクトルと、距離計算用近傍ベクトルを別に設けることで、従来のkNNより高速かつ高精度な近傍探索処理が可能になる。
【００２１】
これにより、処理のコストの大きな大規模な高次元ベクトル群の近傍探索処理でも、kNNグラフを構築し、グラフ探索用の近傍ベクトル数とグラフ探索後の距離計算用の近傍ベクトル数を分けてグラフ探索後に多数のベクトルと距離計算することで、高精度な探索が可能になる。
【００２２】
さらに、グラフ探索後の距離計算にGPUデバイス等のメニーコア演算器を用いて並列化することで高速な探索が可能になる。
【００２３】
上記により、高次元なベクトルを取り扱う物体認識処理システムにおいて、処理時間を短縮することが可能となる。
【図面の簡単な説明】
【００２４】
【図１】従来技術１のフローチャートである。
【図２】従来技術２のフローチャートである。
【図３】本発明の第１の実施の形態におけるホストコンピュータを有する並列化近傍探索処理装置の構成例である。
【図４】本発明の第１の実施の形態における並列化近傍探索処理装置の処理のフローチャートである。
【図５】本発明の第２の実施の形態におけるGPUを有する並列化近傍探索処理装置の構成例である。
【図６】本発明の第２の実施の形態における並列化近傍探索処理装置の処理のフローチャートである。
【図７】本発明の第３の実施の形態におけるメニーコア演算器を有する並列化近傍探索処理装置の構成例である。
【図８】本発明の第３の実施の形態における並列化近傍探索処理装置の処理のフローチャートである。
【図９】本発明の実施例１の現ノードの枝のリストである。
【図１０】本発明の実施例１の現ノードから選択された距離が近い１０本の枝の例である。
【図１１】本発明の実施例１の最近傍ベクトル候補の例である。
【図１２】本発明の実施例２の現ノードの枝のリストである。
【図１３】本発明の実施例２の現ノードから選択された距離が近い８本の枝の例である。
【図１４】本発明の実施例２の最近傍ベクトル候補の例である。
【図１５】従来技術で新の最近傍が見つからない状況の一例（枝数３（Ｎ＝３）でkNNグラフ構築）である。
【図１６】本発明により真の最近傍が探索可能となる例である。
【発明を実施するための形態】
【００２５】
以下、図面と共に本発明の実施の形態を説明する。
【００２６】
[第1の実施の形態]
本実施の形態では、グラフ探索用と距離計算用の近傍ベクトル数を異なる数にする方法について説明する。
【００２７】
図３は、本発明の第１の実施の形態におけるホストコンピュータを有する並列化近傍探索処理装置の構成例である。
【００２８】
並列化近傍探索処理装置１１は、ホストコンピュータ１２を有し、ホストコンピュータ１２は、メインメモリ１３とＣＰＵ１４を有する。なお、ホストコンピュータ１２には、任意の台数の他のデバイスを接続することが可能である。
【００２９】
メインメモリ１３は、外部から入力されるクエリのベクトルデータ及び、CPU１４における計算結果等を保持する。
【００３０】
CPU１４は、枝数Ｎ本のkNNグラフを構築する機能、グラフ探索開始ノードを現ノードとする機能、現ノードの枝Ｎ本から距離が近いＭ本を選択して、該現ノードと該Ｍ本のノードとの距離を計算する機能、距離計算結果から、入力されたクエリから最短距離のノードを選択する機能、選択された最短距離のノードが現ノードと等しいか否かを判定する機能、kNNグラフの探索を行う機能、グラフ探索後に、現ノード及びN−M個の枝ノードとクエリ間の距離のN−M+1個の計算結果より、該クエリから最短距離のノードを選択する機能、最短距離のノードのベクトルID、最短距離ノードとクエリ間の距離を出力する機能を有する。
【００３１】
上記の構成における動作を説明する。
【００３２】
図４は、本発明の第1の実施の形態における並列化近傍探索処理装置の処理のフローチャートである。
【００３３】
以下では、枝数Ｎ本でkNNグラフがホストコンピュータ１２内のメインメモリ１３上に構築されていることを前提とする。
【００３４】
ステップ１０１）  予め、ホストコンピュータ１２のCPU１４は、グラフ探索開始ノードを決定し、メインメモリ１３に格納する。
【００３５】
ステップ１０２）  ホストコンピュータ１２は、外部からのクエリのベクトルデータの入力を受け付け、メインメモリ１３に格納する。
【００３６】
ステップ１０３）  CPU１４は、入力されたベクトルデータに対して、グラフ探索開始ノードを現ノードとする。
【００３７】
ステップ１０４）  CPU１４は、現ノードの枝Ｎ本のうち、現ノードから距離が近い枝Ｍ本（Ｎ＞Ｍ）を選択する。
【００３８】
ステップ１０５）  CPU１４において、クエリが、現ノードとその枝Ｍ本のノード群との距離を計算し、メインメモリ１３に格納する。
【００３９】
ステップ１０６）  メインメモリ１３に格納されている計算結果から、クエリからの最短距離のノードを選択する。
【００４０】
ステップ１０７）  もし、クエリから最短距離のノードが現ノードと等しくないならば、ステップ１０８に移行し、等しい場合はステップ１０９に移行する。
【００４１】
ステップ１０８）  CPU１４は、最短距離の枝ノードにホップし、ステップ１０４に移行して、ホップ先のノードを現ノードとしてグラフ探索する。
【００４２】
ステップ１０９）  CPU１４は、現ノードから距離が遠いＮ−Ｍ個の枝ノードに対応するベクトルＩＤを選択する。
【００４３】
ステップ１１０）  CPU１４は、現ノード及び選択されたＮ−Ｍ個の枝ノードとクエリ間の距離を計算し、メインメモリ１３に格納する。
【００４４】
ステップ１１１）  CPU１４は、メインメモリ１３に格納されている計算結果Ｎ−Ｍ＋１個より、クエリから最短距離にあるノードを選択する。
【００４５】
ステップ１１２）  CPU１４は、メインメモリ１３から最短距離のノードのベクトルＩＤと、最短距離ノードとクエリ間の距離を読み出して出力する。
【００４６】
［第２の実施の形態］
次に、図３の構成に並列距離計算を行うためのGPUデバイスを用いる例について説明する。
【００４７】
図５は、本発明の第２の実施の形態におけるGPUを有する並列化近傍探索処理装置の構成の例を示す。
【００４８】
同図に示す並列化近傍探索処理装置２１は、図３のホストコンピュータ１２に加えて、ベクトルＤＢ２５とGPUデバイス２６を付加した構成である。GPUデバイス２６は、GPUグローバルメモリ２７、GPU２８を有する。
【００４９】
図５に示すCPU２４は、ベクトルDB２５のベクトルデータをGPUデバイス２４に転送する機能、及び、第１の実施の形態における、N−M個の枝ノードに対応するベクトル群とクエリのベクトルの並列距離計算を、GPUデバイス２４に対して指示し、計算結果を取得する機能を有する。その他の機能は第１の実施の形態と同様である。
【００５０】
GPU２８は、CPU２４から並列距離計算の指示を受けると、N−M個の枝ノードに対応するベクトル群とクエリのベクトルの並列距離計算を行い、その結果をCPU２４に返却する機能を有する。
【００５１】
以下に、上記の構成における動作を説明する。
【００５２】
図６は、本発明の第２の実施の形態における並列化近傍探索処理装置の処理のフローチャートである。
【００５３】
以下では、枝数Ｎ本でkNNグラフがホストコンピュータ２２のメインメモリ２３に構築されていることを前提とする。
【００５４】
ステップ２０１）予めホストコンピュータ２２は、ベクトルＤＢ２５をGPUデバイス２６に転送する。
【００５５】
ステップ２０２）  CPU２４は、グラフ探索開始ノードを決定する。
【００５６】
ステップ２０３）  CPU２４は、外部からのクエリのベクトルデータの入力を受け付け、メインメモリ２３に格納する。
【００５７】
ステップ２０４）  CPU２４は、入力されたベクトルデータに対してグラフ探索開始ノードを現ノードとする。
【００５８】
ステップ２０５）  CPU２４は、現ノードの枝Ｎ本のうち、現ノードから距離が近い枝Ｍ本（Ｎ＞Ｍ）を選択し、メインメモリ２３に格納する。
【００５９】
ステップ２０６）  CPU２４において、クエリが現ノードとその枝Ｍ本のノード群との距離を計算し、メインメモリ２３に格納する。
【００６０】
ステップ２０７）  CPU２４は、メインメモリ２３に格納されている計算結果より、クエリから最短距離のノードを選択する。
【００６１】
ステップ２０８）  CPU２４は、もし、クエリから最短距離のノードが現ノードと等しくないならば、ステップ２０９に移行する。等しい場合はステップ２１０に移行する。
【００６２】
ステップ２０９）  CPU２４は、最短距離の枝ノードにホップし、ステップ２０５の処理に戻り、ホップ先のノードを現ノードとしてグラフ探索を続ける。
【００６３】
ステップ２１０）  CPU２４は、クエリから最短距離のノードが現ノードに等しい場合は、現ノードから距離が遠いＮ−Ｍ個の枝ノードに対応するベクトルＩＤを選択する。
【００６４】
ステップ２１１）  CPU２４は、クエリのベクトルデータ及び、ステップ２１０で選択されたＮ−Ｍ個のベクトルＩＤをGPUデバイス２６に転送する。
【００６５】
ステップ２１２）  GPUデバイス２６は、Ｎ−Ｍ個のノードに対応するベクトル群とクエリのベクトルの並列距離計算を行う。
【００６６】
ステップ２１３）  GPUデバイス２６は、ステップ２１２で計算されたＮ−Ｍ個の距離計算結果をホストコンピュータ２２に転送する。
【００６７】
ステップ２１４）  CPU２４は、GPUデバイス２６から取得した距離計算結果をメインメモリ２３に格納し、現ノード及び選択されたＮ−Ｍ個の枝ノードとクエリ間の距離計算結果Ｎ−Ｍ＋１個より、クエリから最短距離のノードを選択する。
【００６８】
ステップ２１５）  CPU２４は、最短距離ノードのベクトルＩＤと、最短距離ノードとクエリ間の距離を出力する。
【００６９】
［第３の実施の形態］
本実施の形態では、第２の実施の形態におけるGPUデバイス２６がメニーコア演算器であった場合について説明する。
【００７０】
図７は、本発明の第３の実施の形態におけるメニーコア演算器を有する並列化近傍探索処理装置の構成例を示す。
【００７１】
同図に示す並列化近傍探索処理装置３１は、図５のGPUデバイス２６としてメニーコア演算器３６がホストコンピュータ３２に接続されている。メニーコア演算器３６はホストコンピュータ３２に複数接続することが可能である。
【００７２】
図７に示すCPU３４は、第１の実施の形態における、N−M個の枝ノードに対応するベクトル群とクエリのベクトルの並列距離計算を、メニーコア演算器３６に対して指示し、計算結果を取得する機能を有する。その他の機能は第１の実施の形態と同様である。
【００７３】
メニーコア演算器３６は、CPU３４から並列距離計算の指示を受けると、N−M個の枝ノードに対応するベクトル群とクエリのベクトルの並列距離計算を行い、その結果をCPU３４に返却する機能を有する。
【００７４】
図８は、本発明の第３の実施の形態における並列化近傍探索処理装置の処理のフローチャートである。
【００７５】
ステップ３０１）  ホストコンピュータ３２は、グラフ探索開始ノードを決定する。
【００７６】
ステップ３０２）  ホストコンピュータ３２は、外部からのクエリのベクトルデータの入力を受け付け、メインメモリ３３に格納する。
【００７７】
ステップ３０３）  CPU３４は、入力されたベクトルデータに対してグラフ探索開始ノードを現ノードに決定する。
【００７８】
ステップ３０４）  CPU３４は、現ノードの枝Ｎ本のうち、現ノードから距離が近い枝Ｍ本（Ｎ＞Ｍ）を選択する。
【００７９】
ステップ３０５）  CPU３４において、クエリが現ノードとその枝Ｍ本のノード群との距離を計算する。
【００８０】
ステップ３０６）  CPU３４は、ステップ３０５の計算結果より、クエリから最短距離のノードを選択する。
【００８１】
ステップ３０７）  もし、クエリから最短距離のノードが現ノードと等しいならば、ステップ３０９に移行し、等しくないならばステップ３０８に移行する。
【００８２】
ステップ３０８）  最短距離の枝ノードにホップし、ステップ３０４の処理に戻り、ホップ先のノードを現ノードとしてグラフ探索を続ける。
【００８３】
ステップ３０９）  CPU３４は、メニーコア演算器３６に対して並列距離計算を指示し、メニーコア演算器３６において、現ノードから距離が遠いＮ−Ｍ個の枝ノードに対応するベクトル群とクエリのベクトルの並列距離を計算し、計算結果をCPU３４に転送する。
【００８４】
ステップ３１０）  CPU３４は、メニーコア演算気３６の距離計算結果をメインメモリ３３に格納し、現ノード及び選択されたＮ−Ｍ個の枝ノードとクエリ間の距離計算結果Ｎ−Ｍ＋１個よりクエリから最願距離のノードを選択する。
【００８５】
ステップ３１１）  CPU３４は、最短距離ノードのベクトルＩＤと最短距離ノードとクエリ間の距離を出力する。
【００８６】
なお、本発明では、ホスト及びその内部の装置（メインメモリやＣＰＵ）、ベクトルＤＢが保存されている記憶装置、GPUデバイス、メニーコア演算器は複数搭載されていても適用可能である。
【００８７】
また、本発明では、kNNグラフのノードの1つがベクトルＤＢ中のベクトル1に対応しているものとする。
【実施例】
【００８８】
以下に、上記の実施の形態における実施例を説明する。
【００８９】
［実施例１］
本実施例では、前述の第２の実施の形態の具体的な例を示す。
【００９０】
事前処理として、ベクトルＤＢ２６に保存されている画像群に対して、画像認識プログラムであるSURFアルゴリズムにより、128次元ベクトル群が合計10,000,000ベクトル抽出され、ハードディスク側（ベクトルDB２５）に保存されている。
【００９１】
SURFアルゴリズムにより抽出されるベクトルの具体例を以下示す。
（0.00771829，0.00876939，-0.00164389，0.00242805，0.00591626，0.0059704，-0.000699053，0.0010269，-0.0402349，0.0478606，-0.00675006，0.008548，0.0079681，0.00937274，0.0254017，0.0303479，0.0105966，0.0781956，0.0237573，0.0313011，-0.0058261，0.00972548，0.00640149，0.00890163，0.00202366，0.005785，0.0008189，0.00261104，0.00168162，0.00313512，0.000645605，0.00187556，0.0156556，0.0198709，0.043964，0.0491846，-0.0457624，0.0519745，0.00104955，0.00352257，-0.0473678，0.0676495，-0.290302，0.372653，-0.105448，0.125615，-0.165742，0.227193，0.00130149，0.33567，0.171501，0.368598，-0.0482353，0.108972，0.0130523，0.0544993，-0.00404431，0.0100914，0.0318822，0.05294，-0.00937941，0.0154139，-0.000685246，0.00858936，0.00154014，0.0031448，0.00700949，0.00804435，-0.00668938，0.00847851，0.000471806，0.00180168，0.0882967，0.18727，0.0836585，0.0885382，-0.00612456，0.128606，0.0955226，0.0993798，-0.122265，0.198727，0.124402，0.35299，-0.0196364，0.0753894，0.0210032，0.155274，-0.00605615，0.0433227，-0.0162856，0.0611591，-0.0026333，0.00693902，1.00823e-005，0.00847174，0.00122396，0.00126437，-4.30777e-005，4.30777e-005，0.000536311，0.000536311，-2.0572e-005，2.79183e-005，0.0566939，0.0566939，-0.00197521，0.00197521，0.0473506，0.0473506，-0.00099733，0.00099733，-0.0350208，0.0410233，-0.00671439，0.0295273，0.00189219，0.003061，0.0154454，0.0282393，0.00100916，0.00239708，-0.00259997，0.00458948，0.00259418，0.00365359，0.000663469，0.00140468）
並列化近傍探索処理装置のCPU２４は、ベクトルＤＢ２５の各ベクトルにおいて、探索用の近傍ベクトル数を10、距離計算用の近傍ベクトル数を512としてkNNグラフを構築する。
【００９２】
ユーザが認識したい画像を撮影し、撮影画像からSURFアルゴリズムにより128次元のベクトル群が1,000ベクトル抽出されたものとして、各クエリのベクトルに対して以下の処理を行う。
【００９３】
以下、第２の実施の形態におけるホストコンピュータ２２とGPUデバイス２６からなる並列化近傍探索処理装置２１において、枝数512本でkNNグラフが構築されている場合における処理を説明する。以下では、図６に示すフローチャートに沿って説明する。
【００９４】
予めホストコンピュータ２２のCPU２４は、ベクトルＤＢ２５のベクトルをGPUデバイス２６に転送し（ステップ２０１）、探索開始ノードを５点決定し（ステップ２０２）、外部から入力されたクエリのベクトルデータを取得し（ステップ２０３）、探索開始ノードを現ノードに設定する（ステップ２０４）。現ノードの枝512本が、例えば、図９のリストで示されていると、このリスト内で現ノードから距離が近い枝10本を選択する（ステップ２０５）。その結果図１０に示すような表となる。
【００９５】
クエリが現ノードとその枝10本のノード群との距離を計算し（ステップ２０６）、計算結果よりクエリから最短距離のノードを選択し（ステップ２０７）、もし、クエリから最短距離のノードが現ノードと等しくないならば（ステップ２０８、No）、最短距離の枝ノードにホップして（ステップ２０９）、ホップ先のノードを現ノードとして探索を続ける（ステップ２０５〜２０８）。もし、クエリから最短距離のノードが現ノードと等しいならば（ステップ２０８、Yes）、クエリのベクトルデータ及び、現ノードから距離が遠い枝502本のノードに対応するベクトルのＩＤをGPUデバイス２６に転送する（ステップ２１０，２１１）。
【００９６】
GPUデバイス２６は、枝502本のノードとベクトルの並列距離計算を行い（ステップ２１２）、計算結果をホストコンピュータ２２に転送する（ステップ２１３）。
【００９７】
CPU２４は、現ノードとGPUデバイス２６で計算された枝ノード502個の計算結果より、クエリから最短距離のノードを選択し（ステップ２１４）、最短距離のノードのＤＢベクトルＩＤと、クエリとそのノードの最短距離値を出力する（ステップ２１５）。
【００９８】
探索開始ノードは５点なので、図１１に示すように、最近傍ベクトル候補が５つ出てくるため、図１１に示すリストの中からクエリのベクトルから最短距離のベクトルID:172818と距離値：0.061359を出力する。
【００９９】
この結果、各クエリのベクトルに対して、ベクトルＤＢ２５内で距離が近似的に最近傍であるベクトルを求めることができる。
【０１００】
このように、SURFアルゴリズムから抽出される高次元ベクトル群に対して、本発明を適用することで、高精度かつ高速な近傍探索処理が可能になる。
【０１０１】
この他にも、音声や文書、位置データなどから抽出されたベクトルの近傍探索にも本発明を適用することが可能である。
【０１０２】
［実施例２］
本実施例では、前述の第３の実施の形態における具体的な例を示す。
【０１０３】
並列化近傍探索処理装置３１は、ホストコンピュータ３２とメニーコア演算器３６を有する。
【０１０４】
事前処理として、DB側に保存されている画像群に対して、局所領域を抽出するPCA-SIFTアルゴリズムにより、36次元のベクトル群が5,000,000ベクトル抽出され、ハードディスク側（ベクトルDB３５）に保存されている。
【０１０５】
PCA-SIFTアルゴリズムにより抽出されるベクトルの具体例を以下に挙げる。
（1573，-1611，1546，-1450，-11，-322，-384，-385，-652，-459，0，377，-619，-969，-858，-591，1138，-535，-2471，-2174，2022，-257，-248，-1820，537，1224，-1272，279，512，-1340，1124，1955，95，-623，1181，-2839）
ベクトルDB３５の各DBベクトルにおいて、探索用の近傍ベクトル数を８、距離計算用の近傍ベクトル数を1024として、kNNグラフを構築する。
【０１０６】
ユーザが認識したい画像を撮影し、撮影画像からSURFアルゴリズムにより36次元のベクトル群が500ベクトル抽出されたとして、各クエリのベクトルに対して以下の処理を行う。
【０１０７】
枝数1024本でkNNグラフが構築されている場合において、ホストコンピュータ３２のCPU３４は、探索開始ノードを10点決定し（ステップ３０１）、クエリのベクトルデータが入力されると（ステップ３０２）、クエリが各探索開始ノードから探索し（ステップ３０３）、現ノードの枝1024本が、例えば図１２のリストで示されていると、このリスト中で、現ノードから距離が近い枝8本を選択する（ステップ３０４）。その例を図１３に示す。
【０１０８】
クエリが、現ノードとその枝８本のノード群と距離計算し（ステップ３０５）、計算結果より、クエリから最短距離のノードを選択し（ステップ３０６）、もし、クエリから最短距離のノードが現ノード以外ならば（ステップ３０７,No）、最短距離の枝ノードにホップし、ホップ先のノードを現ノードとして探索を続ける（ステップ３０４〜３０７）。クエリから最短距離のノードが現ノードの場合（ステップ３０７,Yes）、メニーコア演算器３６において、現ノードから距離が遠い枝1016本のノード群に対応ベクトルとクエリのベクトルの並列距離計算を行い、ホストコンピュータ３２に転送する（ステップ３０９）。
【０１０９】
ホストコンピュータ３２のCPU３４は、現ノードとメニーコア演算器３６で計算された1016個の枝ノードの距離計算結果より、クエリから最願距離のノードを選択し（ステップ３１０）、最短距離ノードのベクトルＩＤと最短距離ノードとクエリ間の距離値を出力する（ステップ３１１）。
【０１１０】
探索開始ノードは10点なので、図１４に示すように、最近傍ベクトル候補が10でてくるので、図１４のリストの中から最短距離のベクトルID:27990と距離値:432507を出力する。
【０１１１】
この結果、各クエリベクトルに対して、ベクトルＤＢ３５内で距離が近似的に最近傍なベクトルを求めることができる。
【０１１２】
このように、PCA-SIFTアルゴリズムから抽出される高次元ベクトル群に対して、本発明を適用することで、高精度かつ高速な近傍探索処理が可能となる。
【０１１３】
この他にも、音声や文書、位置データなどから抽出されたベクトルの近傍探索にも本発明を適用することが可能である。
【０１１４】
以下に、従来技術と本発明の差分を説明する。
【０１１５】
従来技術１のホストのみを利用したkNNグラフを用いた探索は、グラフ探索後、到達したノードのベクトルを出力する。しかし、図１５に示すように、到達したノードが必ずしも最近傍ではない可能性もある。これに対し、本発明は、グラフ探索後、到達したノードのベクトルとその近傍のベクトル群の複数個と距離計算し、その中で最短距離のベクトルを最近傍ベクトルとして出力する。従来技術と比較すると、グラフ探索後に到達したノードとその周辺のノードともう一度距離計算して、到達したノード以外に最近傍がないかを再確認していることにより、従来技術より精度の向上が見込める。
【０１１６】
図１６は、本発明により真の最近傍が探索可能となる例であり、到達ノードの周囲とグラフ探索時より広範囲に、もう一度距離計算することで従来技術では到達し得なかった真の最近傍が探索可能となる例を示している。例えば、枝数100（Ｎ＝100）(Ａの枝（点線）＋Ｂの枝（細い実線）)でkNNグラフを構築し、グラフ探索時は、枝数３（Ｍ＝３）（Ａの枝）で探索し、グラフ探索後に、枝数97（Ｎ−Ｍ）（Ｂの枝）で到達ノード近傍のノードと距離計算を行う。なお、計算コストの上昇はGPUデバイスによる並列化を行うことで抑制できる。
【０１１７】
従来技術においてもN=100でグラフ探索しても、真の最近傍に到達可能であるが、グラフ探索時の距離計算回数が増加して探索速度が低下する。
【０１１８】
また、ホストとGPUデバイスを利用した従来技術２は、グラフを探索時に、ノードヲホップする度に、その距離計算をGPUデバイスで行うために、ホスト−GPUデバイス間の転送が多発し、探索速度が低下するが、本発明では、グラフ探索後にGPUデバイスによる並列距離計算を行うため、ホスト−GPUデバイス間の速度低下を抑えることができる。
【０１１９】
上記の並列化近傍探索処理装置の図４、図６、図８に示す各構成要素の動作をプログラムとして構築し、並列化近傍探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１２０】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１２１】
１１，２１，３１  並列化近傍探索処理装置
１２，２２，３２  ホストコンピュータ
１３，２３，３３  メインメモリ
１４，２４，３４  ＣＰＵ
２５  ベクトルDB
２６  GPUデバイス
２７  GPUグローバルメモリ
２８  GPU
３５  ベクトルDB
３６  メニーコア演算器
【図１】
2014074959.tif 000003
【図２】
2014074959.tif 000004
【図３】
2014074959.tif 000005
【図４】
2014074959.tif 000006
【図５】
2014074959.tif 000007
【図６】
2014074959.tif 000008
【図７】
2014074959.tif 000009
【図８】
2014074959.tif 000010
【図９】
2014074959.tif 000011
【図１０】
2014074959.tif 000012
【図１１】
2014074959.tif 000013
【図１２】
2014074959.tif 000014
【図１３】
2014074959.tif 000015
【図１４】
2014074959.tif 000016
【図１５】
2014074959.tif 000017
【図１６】
2014074959.tif 000018