(57)【特許請求の範囲】
【請求項１】
複数のGPUデバイスと、ベクトル群データを格納したデータベースと、ホスト装置とを備える並列化近傍探索処理装置が実行する並列化近傍探索処理方法であって、
前記ホスト装置は、
前記データベース中のベクトル群データをkd-treeの木構造を用いて分割し、
分割した領域単位でベクトル群データをまとめ、
並び替えたベクトル群データをGPUデバイスのグローバルメモリにコピーし、
クエリのベクトルデータの入力を受け付けると、分割されたベクトル群データのどの領域を探索するかを決め、
決定した領域での探索をGPUデバイスに依頼し、
前記依頼を受けたGPUデバイスは、
探索する分割領域のベクトル群と距離計算を並列に実行し、
最短距離dとそれに対応するベクトルのID（n）を求め、
前記最短距離dと前記対応するベクトルのID（n）を前記ホスト装置側のメインメモリに転送し、
前記ホスト装置が、前記距離dと前記対応するベクトルID（n）を出力する
ことを特徴とする並列化近傍探索処理方法。
【請求項２】
請求項1に記載の並列化近傍探索処理方法において、
前記ベクトル群データをkd-treeの木構造を用いて分割する処理において、
前記ホスト装置は、
前記データベースのベクトル群データを読み込み、
読み込んだベクトル群データをGPUデバイスの数だけ分割し、
各分割ベクトル群データと保持させる各GPUデバイスを対応づけ、
各分割ベクトル群データに対して決められた葉ノード数になるまでkd-treeを作成し、
各分割ベクトル群データを構造化された並びにソートし、ソートされた各分割ベクトル群データを1次元配列上に保持し、
前記ソートされた各分割ベクトル群データの1次元配列を対応するGPUデバイスに転送する
ことを特徴とする並列化近傍探索処理方法。
【請求項３】
請求項1に記載の並列化近傍探索処理方法において、
前記ベクトル群データをkd-treeの木構造を用いて分割する処理において、
前記ホスト装置は、
前記データベースのベクトル群データを読み込み、
読み込んだベクトル群データに対して決められた葉ノード数になるまでkd-treeを作成し、
ベクトル群データを構造化された並びにソートし、ソートされたベクトル群データを1次元配列上に保持し、
前記ソートされた1次元配列をGPUデバイス数で分割し、
前記分割された各1次元配列を異なるGPUデバイスに対応付け、
前記分割された各1次元配列を対応するGPUデバイスに転送する
ことを特徴とする並列化近傍探索処理方法。
【請求項４】
請求項２又は３に記載の並列化近傍探索処理方法において、前記クエリのベクトルデータの入力がされたときに、
前記ホスト装置は、
前記クエリのベクトルデータの入力を受け付け、
kd−treeを探索し、到達した葉ノード中のベクトル群の1次元配列上で先頭のベクトルのIDを対応するGPUデバイスのグローバルメモリに転送し、
前記GPUデバイスは、
前記転送されてきたIDが該当する葉ノードのベクトル群と並列距離計算を行い、複数の計算結果を取得し、
最短距離dとそれに対応するベクトルのID（n）を選択し、
前記最短距離dに対応するベクトルのIDをメインメモリに転送し、
前記ホスト装置は、
前記メインメモリで転送されてきたIDを保持し、
バックトラック半径を決める近似係数εを用いて、バックトラック半径d’を計算し、
前記バックトラック半径d’で、バックトラック対象が全て見つかるバックトラック処理を行い、
バックトラックの対象となった葉ノード群それぞれにおいて、
各葉ノード中のベクトル群の1次元配列上で先頭のベクトルのIDを対応するGPUデバイスのグローバルメモリに転送し、
前記GPUデバイスは、
前記転送されてきたIDが該当する葉ノード群それぞれのベクトル群と並列距離計算を行い、複数の計算結果を取得し、
最短距離d’’とそれに対応するベクトルのID（n’）を選択し、
前記最短距離d’’と前記対応するベクトルのIDをメインメモリに転送し、
前記ホスト装置が、
d’とd’’を比較して、
d’がd’’と同じか大きければ、d’’とd’’に対応するベクトルのIDを出力し、
d’がd’’より小さければ、d’とd’に対応するベクトルのIDを出力する
ことを特徴とする並列化近傍探索処理方法。
【請求項５】
請求項２又は３に記載の並列化近傍探索処理方法において、前記クエリのベクトルデータの入力がされたときに、
前記ホスト装置は、
前記クエリのベクトルデータの入力を受け付け、
kd−treeを探索し、到達した葉ノード中のベクトル群の1次元配列上で先頭のベクトルのIDを対応するGPUデバイスのグローバルメモリに転送し、
前記GPUデバイスは、
前記転送されてきたIDが該当する葉ノードのベクトル群と並列距離計算を行い、複数の計算結果を取得し、
最短距離dとそれに対応するベクトルのID（n）を選択し、
前記最短距離dに対応するベクトルのIDをメインメモリに転送し、
前記ホスト装置は、
前記メインメモリで転送されてきたIDを保持し、
バックトラック半径を決める近似係数εを用いて、バックトラック半径d’を計算し、
前記バックトラック半径d’で、バックトラック処理を開始し、バックトラック対象の葉ノードに到達する度に、
到達した葉ノード中のベクトル群の1次元配列上で先頭のベクトルのIDを対応するGPUデバイスのグローバルメモリに転送し、
前記GPUデバイスは、
前記転送されてきたIDが該当する葉ノード群それぞれのベクトル群と並列距離計算を行い、複数の計算結果を取得し、
最短距離d’’とそれに対応するベクトルのID（n’）を選択し、
前記最短距離d’’と前記対応するベクトルのIDをメインメモリに転送し、
前記ホスト装置が、
d’とd’’を比較して、
d’がd’’と同じか大きければ、dとd’にd’’を代入し、nにn’を代入し、d’を返し、
バックトラック処理が終了すると、dとdに対応するベクトルのIDを出力する
ことを特徴とする並列化近傍探索処理方法。
【請求項６】
複数のGPUデバイスと、ベクトル群データを格納したデータベースと、ホスト装置とを備える並列化近傍探索処理装置における前記ホスト装置として使用されるコンピュータに、請求項１ないし５のうちのいずれか１項に記載の並列化近傍探索処理方法における前記ホスト装置が実行する各処理を実行させるための並列化近傍探索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模な高次元ベクトル群の高速な最近傍探索に関するものであり、特に、ベクトル群データの分割にkd-tree（kd木）を用いた場合の近似最近傍探索技術に関するものである。
【背景技術】
【０００２】
大規模な高次元ベクトル群の高速な最近傍探索に関する従来技術の１つとして、GPU（Graphics Processing Unit）を用いたユークリッド距離計算を並列化した全探索の技術がある。全探索ではクエリのベクトルとDB側との距離計算を１つずつ行い、計算結果から最小の値を求めるので、厳密な探索処理が可能となる。
【０００３】
しかし、全探索では、１つずつ距離計算を行なっていく為、例えばクエリベクトル群の数が1,000個、DBベクトル群の数が100,000,000個の場合、60秒もの処理時間がかかるという問題がある。
【０００４】
他の従来技術として、ハッシュや木構造を用いて、DBベクトル群を構造化し、構造化されたDBベクトル群の特定の領域だけを探索する近似最近傍探索と呼ばれる技術がある。
【０００５】
しかし、近似最近傍探索では、特定の領域だけを探索する為、真の最近傍が求まらない可能性もあり、探索制度の低下を招く問題がある。また、精度を上げると処理が遅くなる。
【０００６】
近似最近傍探索の例として、木構造を用いたkd-tree based ANN(Approximate Nearest Neighbor)（非特許文献1参照）やハッシュを用いたLSH（Locality Sensitive Hashing）が挙げられる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions, Journal of the ACM Volume 45 Issue 6, Nov. 1998
【発明の概要】
【発明が解決しようとする課題】
【０００８】
高次元ベクトル群との探索処理が行われている物体認識システム等において、応答時間の高速なシステムの構築を可能とするために、複数個のクエリベクトル群データと、大規模なDBベクトル群データとの探索処理を非常に高速に行うことが求められている。例えば、ベクトルの次元数を128次元とし、1000個以上のクエリベクトル群データと、1億個以上のDBベクトル群データとの探索処理を、1秒以内に処理し、1秒以内に処理結果を返すという高速な処理を実現することが望まれており、目標とされている。
【０００９】
「背景技術」で説明したように、大規模な高次元ベクトル群の高速な最近傍探索方法として、GPUを用いた全探索や近似最近傍探索処理を用いる技術は存在した。
【００１０】
GPUを用いた全探索では、厳密な探索が可能であり、尚且つ、CPUでの全探索よりも高速に処理することは可能である。しかしながら、上述した目標とする処理時間と比べると遅い。また、近似最近傍探索の場合、探索速度を上げるには、探索精度を犠牲にする必要があった。
【００１１】
本発明は、上記の点に鑑みてなされたものであり、GPUの並列演算能力を活用することで、従来の近似最近傍探索よりも探索精度を落とすことなく、探索速度の向上を可能とした近似最近傍探索技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、本発明は、
複数のGPUデバイスと、ベクトル群データを格納したデータベースと、ホスト装置とを備える並列化近傍探索処理装置が実行する並列化近傍探索処理方法であって、
前記ホスト装置は、
前記データベース中のベクトル群データをkd-treeの木構造を用いて分割し、
分割した領域単位でベクトル群データをまとめ、
並び替えたベクトル群データをGPUデバイスのグローバルメモリにコピーし、
クエリのベクトルデータの入力を受け付けると、分割されたベクトル群データのどの領域を探索するかを決め、
決定した領域での探索をGPUデバイスに依頼し、
前記依頼を受けたGPUデバイスは、
探索する分割領域のベクトル群と距離計算を並列に実行し、
最短距離dとそれに対応するベクトルのID（n）を求め、
前記最短距離dと前記対応するベクトルのID（n）を前記ホスト装置側のメインメモリに転送し、
前記ホスト装置が、前記距離dと前記対応するベクトルID（n）を出力する
ことを特徴とする並列化近傍探索処理方法として構成される。
【発明の効果】
【００１３】
本発明によれば、DB中のベクトル群データをkd-treeの木構造を用いて分割し、分割されたベクトル群データに対してGPUを用いて並列に近傍探索を行うようにしたので、高速な探索が可能になる。これにより、例えば、高次元なベクトルを取り扱う物体認識処理の処理時間を短縮することが可能になる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態における並列化近傍探索処理装置の構成図である。
【図２】本発明の実施の形態における並列化近傍探索処理装置の処理の全体の流れを示すフローチャートである。
【図３】第１の実施の形態における、複数のGPUデバイスのグローバルメモリが保持するベクトルデータ単位でkd-treeを作成する処理を示すフローチャートである。
【図４】第１の実施の形態における、バックトラック対象を全て求めてからバックトラック対象を探索する手順を示すフローチャートである。
【図５】第１の実施の形態における再起呼出内でのバックトラック処理を示すフローチャートである。
【図６】第２の実施の形態において、ベクトルデータ全体でkd-treeを作成し、葉ノード内のベクトルデータの保持を複数のGPUデバイスのグローバルメモリに分担させる処理を示すフローチャートである。
【図７】第２の実施の形態において、バックトラック対象を調べながら、対象が見つかる度にGPUデバイスで探索する手順を示すフローチャートである。
【図８】第２の実施の形態における再起呼出内でのバックトラック処理を示すフローチャートである。
【図９】メモリ上でのデータ例を示す図である。
【図１０】kd-tree構築前後のデータ形態例を示す図である。
【図１１】バックトラックの概要を示す図である。
【図１２】従来技術のkd-tree based ANNにおけるkd-tree作成処理を示す参考図である。
【図１３】従来技術のkd-tree based ANNにおける探索処理を示す参考図である。
【図１４】従来技術のkd-tree based ANNにおける探索処理での再起呼出内のバックトラック処理を示す参考図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の第１の実施の形態、第２の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００１６】
（第１の実施の形態）
＜装置構成＞
図１に、本実施の形態に係る並列化近傍探索処理装置101の構成図を示す。図１に示すように、本実施の形態に係る並列化近傍探索処理装置101は、ホスト装置102、ベクトル群ＤＢ（データベース）105、１つ又は複数のＧＰＵデバイス106を備えて構成される。図示のように、ホスト装置102とベクトル群ＤＢ105が接続されるとともに、ホスト装置102と各ＧＰＵデバイスが接続されている。
【００１７】
ホスト装置102は、コンピュータであり、メインメモリ103、及びＣＰＵ104を含む。各ＧＰＵデバイス106は、ＧＰＵグローバルメモリ107、及びＧＰＵ108を含む。
【００１８】
メインメモリ103には、本発明に係るプログラムが格納され、このプログラムがＣＰＵ104で実行されることにより、以下で説明する処理フローが実現される。当該プログラムは、可搬メモリ等の記憶媒体に格納して配布し、上記コンピュータにインストールして用いてもよいし、ネットワーク上のサーバからダウンロードして上記コンピュータにインストールしてもよい。
【００１９】
＜装置動作＞
以下、本実施の形態に係る並列化近傍探索処理装置101が実行する処理動作を、フローチャートを参照しながら説明する。
【００２０】
図２は、処理の大きな流れを示すフローチャートである。図２のフローチャートを参照して、ホスト装置102でベクトル群データを分割して、分割したベクトル群データの一部または全部を複数または単体のGPUデバイス106で並列に処理する手順を説明する。
【００２１】
ホスト装置102は、ベクトル群DB105中のベクトル群データを分割し（S1101）、分割した領域単位でベクトル群データをまとめ（S1102）、並び替えたベクトル群データをGPUデバイス106のグローバルメモリ107にコピーする（S1103）。
【００２２】
ホスト装置102にクエリのベクトルデータが入力されると（S1104）、ホスト装置102は、分割されたベクトル群データのどの領域を探索するかを決め（S1105）、決定した領域での探索をGPUデバイス106に依頼する（S1106）。
【００２３】
依頼を受けたGPUデバイス106は、探索する分割領域のベクトル群とクエリのベクトルとの距離計算を並列に実行し（S1107）、最短距離dとそれに対応するベクトルのID（n）を求める（S1108）。そして、GPUデバイス106は、距離計算結果で最短距離dと対応するベクトルのID（n）をホスト装置102側のメインメモリ103に転送する（S1109）。ホスト装置102は、距離dとそれに対応するベクトルID（n）を出力する（S1110）。
【００２４】
次に、第１の実施の形態における上記の処理の詳細例を図３〜図５のフローチャートを参照して説明する。図３〜図５は、ベクトル群DB105中のベクトル群データの分割（図２のS1101）にkd-treeの木構造を用いた場合の処理例を示す。
【００２５】
以降の説明では、処理内容の理解を促進するために、図９、図１０、図１１における、処理に対応する符号を適宜示す。図９はメモリ上でのデータ例を示し、図１０はkd-tree構築前後のデータ形態例を示し、図１１はバックトラックの概要を示す。ただし、図９、図１０、図１１に示す内容は処理の理解のための一例に過ぎず、以下で説明する処理内容が図９、図１０、図１１に示された内容に限定されるわけではない。
【００２６】
まず、図３を参照して、複数のGPUデバイス106のグローバルメモリ107が保持するベクトルデータ単位でkd-treeを作成する処理を説明する。
【００２７】
ベクトル群DB105中のベクトル群データの分割（図２のS1101）において、ホスト装置102は、ベクトル群DB105のベクトルデータを読み込み（S2101）、ベクトルデータをGPUデバイス106の数だけ分割する（S2102）。また、ホスト装置102は、各分割ベクトルデータと保持させる各GPUデバイス106を対応づけ（S2103）、各分割ベクトルデータを決められた葉ノード（306）数になるまでkd-treeを作成し（S2104）、各分割ベクトルデータを構造化された並びにベクトル群データをソートし、1次元配列（309）上に保持する（S2105）。
【００２８】
ホスト装置102は、ソートされた各分割ベクトルデータの1次元配列を対応するGPUデバイス106に転送する（S2106）。
【００２９】
上記のようにしてkd-treeが構築された後における、GPUデバイス106を用いたベクトル群の高速な並列化近傍探索処理を図４のフローチャートを参照して説明する。図４は、バックトラック対象を全て求めてから、GPUデバイス106でバックトラック対象を探索する手順を示すフローチャートである。
【００３０】
ホスト装置102は、クエリのベクトルデータの入力を受け付けると（S3101、図２のS1104）、kd−treeを探索（401、S3102）し、到達した葉ノード（308、402）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（307、406）を対応するGPUデバイス106のグローバルメモリ107に転送する（S3103）。
【００３１】
当該GPUデバイス106は、転送されてきたID（314、406）に該当する葉ノード（402）のベクトル群（315）と並列距離計算を行い、複数の計算結果を取得し（S3104）、最短距離dとそれに対応するベクトルのID（n）を選択して（S3105）、距離計算結果で最短距離d（404）に対応するベクトルのID（314、406）をメインメモリ103に転送する（S3106）。
【００３２】
ホスト装置102は、メインメモリ103で転送されてきたIDを保持する（S3107）。更にホスト装置102は、バックトラック半径を決める近似係数ε（410）とｄを用いて、バックトラック半径d'（405）を計算し（S3108）、バックトラック半径d'（405）で、バックトラック対象が全て見つかるバックトラック処理を開始する（S3109）。
【００３３】
バックトラック処理は、再起呼出により再帰的に実行される処理である。以下、ホスト装置102が実行するバックトラック処理例について図５を参照して詳細に説明する。
【００３４】
S3201（及び図４のS3109）に示すように、初期パラメータとして、対象ノードを根ノード、バックトラック半径をd'、対象ノードでのkd-tree作成時の空間分割面をa、分割面と同次元のクエリベクトルの要素値をqとして、バックトラック処理を開始する。
【００３５】
バックトラック処理では、葉ノードに到達したかを判定し（S3202）、葉ノードに到達していれば（S3202のYes）、到達した葉ノードをバックトラック対象にする（S3203）。
【００３６】
葉ノードに到達していなければ（S3202のNo）、d'<aかを判定し（S3204）、d'<aであれば（S3204のYes）、|a-q|<d'を判定し（S3205）、|a-q|<d'であれば（S3205のYes）、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出し（S3207）、パラメータを、（対象ノード：右子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出す（S3208）、
S3205においてNoのとき、すなわち|a-q|<d'でない場合、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出す（S3209）。
【００３７】
S3204においてNoのとき、すなわちd'<aでない場合、|a-q|<d'を判定し（S3206）、  |a-q|<d'であれば（S3206のYes）、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出し（S3210）、パラメータを、（対象ノード：右子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出す（S3211）。
【００３８】
S3206においてNoのとき、すなわち|a-q|<d'でない場合、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出す（S3212）。
【００３９】
図４（S3110)に戻り、ホスト装置102は、バックトラックの対象となった葉ノード群（403）それぞれにおいて、各葉ノード（306、403）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（305）を対応するGPUデバイス106のグローバルメモリ107に転送する（S3110）。
【００４０】
当該GPUデバイス106は、転送されてきたID（311）が該当する葉ノード（312、403）群それぞれのベクトル群と並列距離計算をし、複数の計算結果を取得し（S3111）、最短距離d''とそれに対応するベクトルのID（n'）を選択し（S3112）、距離計算結果で最短距離d''（408）と対応するベクトルのID（409）をメインメモリ103に転送する（S3113）。  
ホスト装置102は、d'（405）とd''（408）を比較し、d'（405）がd''（408）と同じか大きければ（S3114のYes）、d''（408）とd''（408）に対応するベクトルのID（409）を出力する（S3115）。S3114での比較でNoの場合、すなわちd'（405）がd''（408）より小さければ、d'（405）とd'（405）に対応するベクトルのID（406）を出力（3116）する。
【００４１】
尚、上述した例におけるバックトラック時の探索は、幅優先探索を例に示したが、深さ優先探索でもかまわない。
【００４２】
本発明に係る技術の特徴を理解し易くするために、参考として、従来技術のkd-tree based ANNの処理方法を図１２、図１３、図１４に示す。図１２がkd-tree作成を示し、図１３は探索処理を示し、図１４は再起呼出内のバックトラック処理を示す。
【００４３】
従来技術では葉ノードに対応するベクトルデータが１つになるまでkd-treeを作成し、探索時には、クエリのベクトルが到達した葉ノードに対応する１つのベクトルとの距離計算をCPUで行い、求まった距離値でバックトラック処理を行う。一方、本発明の実施の形態に係る技術では、決められた葉ノード数になるまでkd-treeを作成し、（S2104,S4102）探索時には、クエリのベクトルが到達した葉ノードに対応する複数のベクトルとの距離計算をGPUで並列に行い、複数の距離計算結果から最短距離値とそれに対応するベクトルを選択し、選択された最短距離値でバックトラックを行っている。
【００４４】
従って、本発明に係る技術では、従来技術に対して、同じバックトラック半径で見た場合、葉ノード内のベクトル数が増えるので、探索精度が向上し、さらに、GPUで距離計算を並列化することで、計算対象のベクトル数が増加しても、探索速度を落とさずに処理できる。
【００４５】
さらに、バックトラックにおいて、従来技術では、葉ノードに到達する度に葉ノード内のベクトルと距離計算をする（S7203）のに対して、本発明に係る技術では、バックトラック対象の葉ノードを全て求めてから（S3109）、バックトラック対象の葉ノード全てをGPUで探索する（S3110,S3111）。その為、本発明に係る技術では、CPU-GPU間の転送コストを減らすことができ、探索精度はそのままに、探索速度を向上させることができる。
【００４６】
（第２の実施の形態）
次に、kd-treeを第１の実施の形態と異なる方法で作成する形態を第２の実施の形態として説明する。第２の実施の形態におけるシステム構成は図１に示したとおりであり、第１の実施の形態と同じである。また、全体の処理の流れも図２に示したとおりであり、第１の実施の形態と同じである。
【００４７】
第２の実施の形態における処理の詳細例を図６〜図８のフローチャートを参照して説明する。図６〜図８は、第２の実施の形態において、ベクトル群DB105中のベクトル群データの分割（図２のS1101）にkd-treeの木構造を用いた場合の処理例を示すフローチャートである。
【００４８】
まず、図６を参照して、ベクトルデータ全体でkd-treeを作成し、葉ノード内のベクトルデータの保持を複数のGPUデバイス106のグローバルメモリに分担させる処理について説明する。
【００４９】
ベクトル群DB105中のベクトル群データの分割（図２のS1101）において、ホスト装置102は、ベクトル群DB105のベクトルデータを読み込み（S4101）、ベクトルデータから決められた葉ノード（306）数になるまでkd-treeを作成（S4102）し、ベクトルデータを構造化された並びにソートし、1次元配列（309）上に保持する（S4103）。
【００５０】
更にホスト装置102は、ソートされた1次元配列をGPUデバイス数で分割し（S4104）、分割された各1次元配列を異なるGPUデバイス106に対応付け（S4105）、分割された各1次元配列を対応するGPUデバイス106に転送する（S4106）。
【００５１】
上記のようにしてkd-treeが構築された後における、GPUデバイス106を用いたベクトル群の高速な並列化近傍探索処理を図７、図８のフローチャートを参照して説明する。図７は、バックトラック対象を調べながら、対象が見つかる度にGPUデバイス106で探索する手順を示すフローチャートである。図８は、再起呼出内のバックトラック処理のフローチャートである。
【００５２】
ホスト装置102は、クエリのベクトルデータの入力を受け付けると（S5101、図２のS1104）、kd−treeを探索（401、S5102）し、到達した葉ノード（308、402）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（307、406）を対応するGPUデバイス106のグローバルメモリ107に転送する（S5103）。
【００５３】
当該GPUデバイス106は、転送されてきたID（314、406）に該当する葉ノード（402）のベクトル群（315）と並列距離計算し、複数の計算結果を取得し（S5104）、最短距離dとそれに対応するベクトルのID（n）を選択して（S5105）、距離計算結果で最短距離d（404）に対応するベクトルのID（314、406）をメインメモリ103に転送する（S5106）。
【００５４】
ホスト装置102は、メインメモリ103で転送されてきたIDを保持する（S5107）。更にホスト装置102は、バックトラック半径を決める近似係数ε（410）とｄを用いて、バックトラック半径d'（405）を計算（S5108）し、バックトラック半径d'（405）で、バックトラック処理開始する。
【００５５】
バックトラック処理開始以降の処理については、まず基本となる処理を説明し、その後に、より細部を含む詳細について説明する。
【００５６】
バックトラック処理においては、バックトラック対象の葉ノードに到達する度に、到達した葉ノード（306、403）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（305）を対応するGPUデバイス106のグローバルメモリ（107）に転送する（S5203）。
【００５７】
GPUデバイス106は、転送されてきたID（311）が該当する葉ノード（312、403）群それぞれのベクトル群と並列距離計算をし、複数の計算結果を取得し（S5204）、最短距離d''とそれに対応するベクトルのID（n'）を選択し（S5205）、距離計算結果で最短距離d''（408）と対応するベクトルのID（409）をメインメモリ（103）に転送する（S5206）。
【００５８】
ホスト装置102は、d'（405）がd''（408）と同じか大きければ（S5207のYes）、d（404）とd'（405）にd''（408）を代入し、n（406）にn'（409）を代入し（S5208）、d'（405）を返す（S5209）。
【００５９】
バックトラック処理が終了すると、ホスト装置102は、d（404）とd（404）に対応するベクトルのID（406）を出力する（S5110）。
【００６０】
以下、バックトラック半径d'を計算したS5108以降の処理をより詳細に説明する。
【００６１】
初期パラメータを、（対象ノード：クエリのベクトルが最初に到達した葉ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を開始する（S5109）。
【００６２】
バックトラック処理（図８）では、葉ノードに到達したかを判定し（S5202）、葉ノードに到達していれば（S5202のYes）、到達した葉ノード（306、403）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（305）を対応するGPUデバイス106のグローバルメモリ107に転送する（S5203）。
【００６３】
当該GPUデバイス106は、転送されてきたID（311）が該当する葉ノード（312、403）群それぞれのベクトル群と並列距離計算をし、複数の計算結果を取得し（S5204）、最短距離d''とそれに対応するベクトルのID（n'）を選択し（S5205）、距離計算結果で最短距離d''（408）と対応するベクトルのID（409）をメインメモリ103に転送する（S5206）。
【００６４】
ホスト装置102は、d'（405）がd''（408）と同じか大きければ（S5207のYes）、d（404）とd'（405）にd''（408）を代入し、n（406）にn'（409）を代入し（S5208）、d'（405）を返す（S5209）。
【００６５】
S5202においてNoの場合、すなわち、葉ノードに到達していなければ、d'<aかを判定し（S5210）、d'<aであれば（S5210のYes）、|a-q|<d'を判定し（S5211）、|a-q|<d'であれば（S5211のYes）、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出し（S5212）、パラメータを、（対象ノード：右子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出す（S5213）、
S5211においてNoのとき、すなわち|a-q|<d'でない場合、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出す（S5214）。
【００６６】
S5210においてNoのとき、すなわちd'<aでない場合、|a-q|<d'を判定し（S5215）、|a-q|<d'であれば（S5215のYes）、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出し（S5216）、パラメータを、（対象ノード：右子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出す（S5217）。
【００６７】
S5215においてNoのとき、すなわち|a-q|<d'でない場合、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a、分割面と同次元のクエリベクトルの要素値：q）として、バックトラック処理を再帰的に呼び出す（S5218）。
【００６８】
ホスト装置102は、d（404）とd（404）に対応するベクトルのID（406）を出力する（S5110）。
【００６９】
第１の実施の形態と同様、バックトラック時の探索を幅優先探索を例に説明したが、深さ優先探索でもかまわない。
【００７０】
なお、第１の実施の形態では、図３に示す処理と図４に示す処理を組み合わせ、第２の実施の形態では、図６に示す処理と図７に示す処理を組み合わせたが、図３に示す処理と図７に示す処理を組み合わせ、図６に示す処理と図４に示す処理を組み合わせることとしてもよい。
【００７１】
（実施の形態の効果）
本発明の実施の形態によれば、葉ノードに複数のベクトルデータが対応するインデックス処理を行うことで、GPU搭載マシンを用いた高次元ベクトル群の高速な並列化近傍探索処理が可能になる。
【００７２】
これにより、処理コストの大きな、大規模な高次元ベクトル群の近傍探索処理でも、DBを構造化して分割し、分割されたDBをGPUを用いて並列に近傍探索をすることで、高速な探索が可能になる。従って、例えば高次元なベクトルを取り扱う物体認識処理の処理時間を短縮することが可能になる。
【００７３】
次に、より具体的な処理例を実施例１、実施例２として説明する
（実施例１）
実施例１は、上記の第１の実施の形態に対応する実施例である。実施例１では、SURF（Speeded Up Robust Features）アルゴリズムを用いた物体認識処理において、画像から128次元のベクトル群が抽出された場合の例について説明する。
【００７４】
実施例１において、並列化近傍探索処理装置101には、2基のGPUデバイス106が搭載されているものとする。また、事前処理として、画像DB側に保存されている画像群に対して、SURFアルゴリズムにより、128次元のベクトル群が合計10,000,000ベクトル抽出され、ベクトル群DB105（ハードディス）側に保存されている。
【００７５】
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）
ベクトル群DB105のベクトルデータ群を分割する処理において、ベクトル群DB105のベクトルデータを読み込み（S2101）、ベクトルデータをGPUデバイスの数2で分割（S2102）し、GPUデバイス1基あたり、5,000,000ベクトルを担当させることとする。各分割ベクトルデータと保持させる各GPUデバイス106を対応づけ（S2103）、葉ノード数を64として、各分割ベクトルデータについて決められた葉ノード（306）数になるまでkd-treeを作成（S2104）し、各分割ベクトルデータを構造化された並びにソートし、1次元配列（309）上に保持し（S2105）、ソートされた各分割ベクトルデータの1次元配列を対応するGPUデバイス106に転送する（S2106）。
【００７６】
本実施例１では、ユーザが認識したい画像を撮影し、撮影画像からSURFアルゴリズムより128次元のベクトル群が1,000ベクトル抽出されたとする。
【００７７】
各クエリベクトルにおいて、ホスト装置102は、クエリのベクトルデータの入力を受け付け（S3101）、kd−treeを探索（401、S3102）し、到達した葉ノード（308、402）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（307、406）を対応するGPUデバイス106のグローバルメモリ107に転送する（S3103）。
【００７８】
当該GPUデバイス106は、転送されてきたID（314、406）が該当する葉ノード（402）のベクトル群（315）と並列距離計算し、複数の計算結果を取得する（S3104）。
【００７９】
本実施例１では、例えば、下記のような計算結果（計算結果の一部）が取得される。
【００８０】
ベクトルID        距離計算結果
35742                0.099402
98163                0.095652
3890                 0.087106
172818               0.061359
27990                0.06267
140948               0.085252
183242               0.088398
58996                0.073724
8575                 0.084284
127189               0.06245
105814               0.092972
172115               0.082664
GPUデバイス106は、複数の計算結果の中から、最短距離d=0.06245とそれに対応するベクトルのID（n=127189）を選択し（S3105）、距離計算結果で最短距離d=0.06245（404）に対応するベクトルのID（n=127189）（314、406）をメインメモリ103に転送する（S3106）。
【００８１】
ホスト装置102において、メインメモリ（103）で転送されてきたID（n=127189）を保持し（S3107）、バックトラック半径を決める近似係数εを、ε=99として、バックトラック半径（405）d' =  d/（1+ε）= 0.06245/100=0.0006245を計算し（S3108）、バックトラック半径（405）d'=0.0006245で、以下のようにバックトラック処理を開始する。
【００８２】
本実施例１では、初期パラメータを、（対象ノード：根ノード、バックトラック半径：d'=0.0006245、対象ノードでのkd-tree作成時の空間分割面：a=0.0753894、分割面と同次元のクエリベクトルの要素値：q=0.031301）として、バックトラック処理を開始する（S3109）。
【００８３】
バックトラック処理（図５）では、葉ノードに到達したかを判定し（S3202）、葉ノードに到達していれば（S3202のYes）、到達した葉ノードをバックトラック対象にする（S3203）。
【００８４】
葉ノードに到達していない場合（S3202のNo）、d'<aであり（S3204）、|a-q|<d'ではないので（S3205のNo）、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'、対象ノードでのkd-tree作成時の空間分割面：a=-0.00668938、分割面と同次元のクエリベクトルの要素値：q=0.000536311）として、バックトラック処理を再帰的に呼び出す（S3209）。
【００８５】
バックトラックの対象となった葉ノード群（403）それぞれにおいて、各葉ノード（306、403）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（305）を対応するGPUデバイス106のグローバルメモリ107に転送する（図４のS3110）。
【００８６】
GPUデバイス106は、転送されてきたID（311）が該当する葉ノード（312、403）群それぞれのベクトル群と並列距離計算をし、複数の計算結果を取得する（S3111）。例えば、以下のような計算結果（計算結果の一部）が取得される。
【００８７】
ベクトルID        距離計算結果
72289                0.081518
80535                0.069957
170734               0.072266
166491               0.005922
57625                0.006741
55956                0.059269
30643                0.048778
5838                 0.066382
126520               0.016892
206660               0.058364
89650                0.005679
113461               0.033354
GPUデバイス106は、最短距離d''=0.005679とそれに対応するベクトルのID（n'=89650）を選択し（S3112）、距離計算結果で最短距離d''=0.005679（408）と対応するベクトルのID（n'=89650）（409）をメインメモリ103に転送する（S3113）。
【００８８】
ホスト装置102は、d'=0.0006245（405）がd''=0.005679（408）より大きいので（S3114のYes）、d''=0.005679（408）とd''=0.005679（408）に対応するベクトルのID（n'=89650）（409）を出力する（S3115）。
【００８９】
この結果、各クエリベクトルに対して、DBベクトル群内で距離が最短である最近傍ベクトルが求められる。このように、SURFアルゴリズムから抽出される高次元ベクトル群に対して、本発明を適用することで、高速な近傍探索処理が可能になる。
【００９０】
（実施例２）
次に、実施例２を説明する。実施例２は、上記の第２の実施の形態に対応する実施例である。実施例２では、PCA-SIFT（Principal Component Analysis−Scale Invariant Feature Transform）アルゴリズムを用いた物体認識処理において、画像から36次元のベクトル群が抽出された場合の例について説明する。
【００９１】
実施例２では、並列化近傍探索処理装置101には、4基のGPUデバイス106が搭載されているものとする。また、事前処理として、画像DB側に保存されている画像群に対して、PCA-SIFTアルゴリズムにより、36次元のベクトル群が6,000,000ベクトル抽出され、ベクトル群DB105（ハードディス）側に保存されている。
【００９２】
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）
ベクトル群DB105のベクトルデータ群を分割する処理において、ホスト装置102は、ベクトル群DB105のベクトルデータを読み込み（S4101）、葉ノード数を128として、ベクトルデータに対して決められた葉ノード（306）数になるまでkd-treeを作成（S4102）し、ベクトルデータを構造化された並びにソートし、1次元配列（309）上に保持し（S4103）、ソートされた1次元配列をGPUデバイス数4で分割し（S4104）、4つに分割された各1次元配列を異なるGPUデバイス106に対応付け（S4105）、4つに分割された各1次元配列を対応するGPUデバイスに転送する（S4106）。
【００９３】
本実施例２では、ユーザが認識したい画像を撮影し、撮影画像からPCA-SIFTアルゴリズムより36次元のベクトル群が2000ベクトル抽出されたとする。
【００９４】
各クエリベクトルにおいて、ホスト装置102は、クエリのベクトルデータの入力を受け付け（S5101）、kd−treeを探索（401、S5102）し、到達した葉ノード（308、402）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（307、406）を対応するGPUデバイス106のグローバルメモリ107に転送する（S5103）。
【００９５】
当該GPUデバイス106は、転送されてきたID（314、406）が該当する葉ノード（402）のベクトル群（315）と並列距離計算し、複数の計算結果を取得する（S5104）。
【００９６】
本実施例２では、例えば、下記のような計算結果（計算結果の一部）が取得される。
【００９７】
ベクトルID         距離計算結果
72289                4619847
80535                219754678
170734               968428
166491               84259310
57625                4613847
55956                641251
30643                21488949
5838                 748516
126520               847556
206660               52987462
89650                2541844
113461               36598741
GPUデバイス106は、最短距離d=64125とそれに対応するベクトルのID（n=55956）を選択し（S5105）、距離計算結果で最短距離d=64125（404）に対応するベクトルのID（n=55956）（314、406）をメインメモリ103に転送する（S5106）。
【００９８】
ホスト装置102において、メインメモリ103で転送されてきたID（n=55956）を保持し（S5107）、バックトラック半径を決める近似係数εを、ε=499として、バックトラック半径d'=  d/（1+ε）=64125/500=128.25 （405）を計算し（S5108）し、バックトラック半径d' =128.25 （405）で、以下のようにバックトラック処理を開始する。
【００９９】
本実施例２では、初期パラメータを、（対象ノード：根ノード、バックトラック半径：d' =128.25、対象ノードでのkd-tree作成時の空間分割面：a=-248、分割面と同次元のクエリベクトルの要素値：q=1138）として、バックトラック処理を開始する（S5109）。
【０１００】
バックトラック処理（図８）では、葉ノードに到達したかを判定し（S5202）、葉ノードに到達していれば（S5202のYes）、到達した葉ノード（306、403）中のベクトル群の1次元配列（309）上で先頭のベクトルのID（305）を対応するGPUデバイス（106）のグローバルメモリ（107）に転送する（S5203）。
【０１０１】
GPUデバイス106は、転送されてきたID（311）が該当する葉ノード（312、403）群それぞれのベクトル群と並列距離計算を行って、複数の計算結果を取得する（S5204）。例えば、以下のような計算結果（計算結果の一部）が取得される。
【０１０２】
ベクトルID          距離計算結果
163856                1498483
8700                  44149474
11233                 5874358
33124                 16737933
77875                 432507
27794                 18812086
96333                 2747275
148766                1992416
93235                 60519212
128207                10021389
141947                7465054
8575                  876302
GPUデバイス106は、最短距離d''=43250とそれに対応するベクトルのID（n'=77875）を選択し（S5205）、距離計算結果で最短距離d''=43250（408）と対応するベクトルのID（n'=77875）（409）をメインメモリ103に転送する（S5206）。
【０１０３】
ホスト装置102は、d' =128.25 （405）がd''=43250 （408）より小さいので（S5207のNo）、d'=128.25を返す（S5209）。
【０１０４】
葉ノードに到達していない場合（S5202のNo）、d'<aでなく（S5210のNo）、|a-q|<d'でないので（S5215のNo）、パラメータを、（対象ノード：左子ノード、バックトラック半径：d'=128.25、対象ノードでのkd-tree作成時の空間分割面：a=279、分割面と同次元のクエリベクトルの要素値：q=2022）として、バックトラック処理を再帰的に呼び出す（S5218）。
【０１０５】
ホスト装置102において、バックトラック処理後のd=845617とそれに対応するベクトルのID（n=2065）を出力する（S5110）。
【０１０６】
この結果、各クエリベクトルに対して、最近傍ベクトルが求められる。このように、PCA-SIFTアルゴリズムから抽出される高次元ベクトル群に対して、本発明を適用することで、高速な近傍探索処理が可能になる。
【０１０７】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１０８】
101  並列化近傍探索処理装置
102  ホスト装置
103  メインメモリ
104  ＣＰＵ
105  ベクトル群ＤＢ（データベース）
106  ＧＰＵデバイス
107  ＧＰＵグローバルメモリ
108  ＧＰＵ
【図１】
0005600695.tif 000002
【図２】
0005600695.tif 000003
【図３】
0005600695.tif 000004
【図４】
0005600695.tif 000005
【図５】
0005600695.tif 000006
【図６】
0005600695.tif 000007
【図７】
0005600695.tif 000008
【図８】
0005600695.tif 000009
【図９】
0005600695.tif 000010
【図１０】
0005600695.tif 000011
【図１１】
0005600695.tif 000012
【図１２】
0005600695.tif 000013
【図１３】
0005600695.tif 000014
【図１４】
0005600695.tif 000015