任意の実数群から探索点の最近傍値を探索する方法
【課題】任意の実数群から探索点の最近傍値を高速に探索する。
【解決手段】実数群（x[1],x[2],x[3]…x[n]）から、探索点ｑの最近傍値を探索する方法であって、探索用データベースを作るステップと、探索データベースを探索するステップとを含む。探索用データベースは、実数群の区間（x[1]〜x[n]）をバケットで隙間無くかつ等間隔でｍ個に区分したバケット列を有する。各バケットには、バケット番号と、その中に含まれる実数の個数であるバケットサイズとが記憶される。各バケットには、バケットサイズがゼロでなくかつ当該バケットに最も近いバケットのバケット番号を示すラストフィルドバケットが記憶される。探索ステップは、探索点ｑが属するバケットを計算し、そのバケットのバケットサイズが０でない場合、当該バケット内から最近傍値を計算する。バケットサイズが０の場合、ラストフィルドバケットから最近傍値を計算する。
【解決手段】実数群（x[1],x[2],x[3]…x[n]）から、探索点ｑの最近傍値を探索する方法であって、探索用データベースを作るステップと、探索データベースを探索するステップとを含む。探索用データベースは、実数群の区間（x[1]〜x[n]）をバケットで隙間無くかつ等間隔でｍ個に区分したバケット列を有する。各バケットには、バケット番号と、その中に含まれる実数の個数であるバケットサイズとが記憶される。各バケットには、バケットサイズがゼロでなくかつ当該バケットに最も近いバケットのバケット番号を示すラストフィルドバケットが記憶される。探索ステップは、探索点ｑが属するバケットを計算し、そのバケットのバケットサイズが０でない場合、当該バケット内から最近傍値を計算する。バケットサイズが０の場合、ラストフィルドバケットから最近傍値を計算する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを利用した計算方法であり、任意の実数群から探索点の最近傍値を高速に探索することができる方法に関する。
【背景技術】
【０００２】
コンピュータを用いた数値計算において、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索しなければならない場合がある。このような状況の例としては、コンピュータを使用した例えば空力シミュレーション計算において、運動する物体（ラグランジュ要素）の表面座標を、構造格子（オイラー要素）の座標系に取り込む場合等が挙げられる。
【０００３】
しかしながら、上記実数群(x[1],x[2], x[3] … x[n])のサイズが大きくなった場合（例えばｎが１億を超えるような場合）、探索対象となる実数ｑの数が多い場合（例えば１００万を超える様な場合）、又はこのような探索を繰り返し何度も行う場合、計算時間が数時間にも及ぶ場合がある。従って、計算コストを低減するために、従来より、上述の計算時間を短縮する試みが種々提案されている。
【０００４】
従来、この種の課題を解決するために、大きく分けて下記二つの方法が提案されている。第１の方法は、実数x[1] からx[n]まで順番にｑと値の大小を比較し、大小関係が逆転する値が見つかるまで探索する方法である。この場合、例えば、下式に示す条件を満たすインデックス（ ipoint ）が見つかれば、そのインデックス（ ipoint ） が解となる。
x[ipoint] ≦ ｑ ＜ x[ipoint+1]
【０００５】
また、他の方法として、２分法（bisection method）又はkd-tree methodが提案されている。これらの方法は、近年、良く使用されている探索手法であり、上記方法よりも効率良く探索点ｑに近い数を見つけることができる。
【０００６】
さらに、近年では、これらの二つの手法を組み合わせたＡＮＮ(Approximate Nearest Neighbor)解法も提案されている。
【０００７】
関連する先行技術としては次のものがある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００３−２４２１５１号公報
【非特許文献】
【０００９】
【非特許文献１】荒井英剛、他２名共著、「空間分割と直交変換の統合による高次元最近傍探索の高速化」 社団法人情報処理学会研究報告 2006/3/16
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来の方法では、探索する対象が増え多次元になるほどその効果が減少し、３０次元程度からほぼ全探索に近くなる。また、探索規模が大きくなるほど、ツリー構造が複雑化し、探索範囲も大きくなり計算に多くの時間を要するという欠点がある。
【００１１】
本発明は、以上のような問題点に鑑み案出なされたもので、探索に先立ち、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットで隙間無くかつ等間隔に区分した探索用データベースを作成し、そこに所定の情報を記憶させることにより、計算時間を大幅に短縮しうる任意の実数群から探索点の最近傍値を探索する方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明のうち請求項１記載の発明は、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索する方法であって、コンピュータ装置の記憶部に、探索用データベースを作る前処理ステップと、前記コンピュータ装置が前記探索データベースを使用して前記探索を行う探索ステップとを含み、前記探索用データベースは、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットで隙間無くかつ等間隔でｍ個に区分されたバケット列を有し、前記各バケットには、先頭バケットから末尾バケットまで順番に割り当てられた固有のバケット番号と、各バケットの中に含まれる前記実数の個数であるバケットサイズとが記憶されるとともに、少なくとも前記先頭バケットを除いた各バケットには、前記バケットサイズがゼロでなくかつ当該バケットに最も近いバケットのバケット番号を示すラストフィルドバケットが記憶され、前記探索ステップは、前記探索点ｑが属するバケットを計算する第１のステップと、前記計算されたバケットのバケットサイズを参照する第２のステップと、前記参照されたバケットサイズが０でない場合、当該参照されたバケットから最近傍値を計算する一方、前記参照されたバケットサイズが０の場合、そのバケットのラストフィルドバケットが示すバケットから前記最近傍値を計算する第３のステップとを含むことを特徴とする。
【００１３】
また請求項２記載の発明は、前記最近傍値は、前記探索点を超えない該探索点に最も近い値とし、前記探索用データベースには、前記ラストフィルドバケットとして、当該バケットよりも先頭バケット側で当該バケット番号に最も近いバケット番号が記憶されている請求項１記載の最近傍値を探索する方法である。
【００１４】
また請求項３記載の発明は、前記探索用データベースの少なくともバケットサイズが０でないバケットには、そのバケット内の実数のうちの最小値及び最大値がさらに記憶されている請求項２記載の最近傍値を探索する方法である。
【００１５】
また請求項４記載の発明は、前記第２のステップにおいて、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、探索点ｑが最小値よりも小さい場合には、そのバケットのラストフィルドバケットの最大値を最近傍値とする請求項３記載の最近傍値を探索する方法である。
【００１６】
また請求項５記載の発明は、前記第２のステップにおいて、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、前記探索点ｑが最小値以上の場合には、そのバケットに含まれる実数に対してx[ ipoint ] ≦ｑ＜x[ ipoint + 1 ]となるx[ ipoint ] を最近傍値とする請求項３又は４記載の最近傍値を探索する方法である。
【００１７】
また請求項６記載の発明は、複数の多次元の座標値（x,y,z…）が与えられており、探索点ｑ（x1,y1,z1）が与えられたとき、前記座標値を各次元毎の実数群に分け、
各実数群に対して請求項１乃至５のいずれかに記載された探索方法を適用することで前記探索点ｑの各座標に最も近い最近傍値を各次元の実数群の中からそれぞれ探索することを特徴とする最近傍値を探索する方法である。
【発明の効果】
【００１８】
本発明では、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索する方法として、コンピュータ装置の記憶部に、探索用データベースを作るステップと、前記コンピュータ装置が前記探索データベースを使用して前記探索を行う探索ステップとを含む。
【００１９】
前記探索用データベースは、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットで隙間無くかつ等間隔でｍ個に区分されたバケット列を有し、前記各バケットには、先頭バケットから末尾バケットまで順番に割り当てられた固有のバケット番号と、各バケットの中に含まれる前記実数の個数であるバケットサイズとが記憶される。また、探索用データベースは、少なくとも前記先頭バケットを除いた各バケットに、バケットサイズがゼロでなくかつ当該バケット番号に最も近い近接バケット番号を示すラストフィルドバケットが記憶される。なお先頭バケットには、例えばラストフィルドバケットとして、自らのバケット番号を記憶させることができる。
【００２０】
次に、探索ステップでは、前記探索点ｑが属するバケットを計算する第１のステップと、前記計算されたバケットのバケットサイズを参照する第２のステップと、前記参照されたバケットサイズが０でない場合、当該参照されたバケットから最近傍値を計算する一方、前記参照されたバケットサイズが０の場合、そのバケットのラストフィルドバケットが示すバケットから前記最近傍値を計算する第３のステップとを含む。
【００２１】
バケットは、等間隔で設定されている。従って、前記第１のステップは、単純な一次式で所定のバケットを見つけることができる。
【００２２】
また、第３のステップでは、参照されたバケットのバケットサイズが０ではない場合、当該バケットに含まれる実数から、また、バケットサイズが０の場合にはそのバケットに記憶されているラストフィルドバケットに含まれる実数から最近傍値をそれぞれ計算できる。従って、第３のステップでは、いずれの場合でも、一つのバケットだけを対象とし、その中の実数から最近傍値を見つければ良い。このため、計算時間を大幅に低減することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の探索を行うコンピュータ装置のブロック図である。
【図２】本発明の探索方法の処理手順を示すフローチャートである。
【図３】実数群及び探索用データベースの構造を示す線図である。
【図４】探索用データベースを作成する処理手順を示すフローチャートである。
【図５】ラストフィルドバケットを決定する処理手順の一例を示すフローチャートである。
【図６】探索ステップの処理手順の一例を示すフローチャートである。
【図７】空力シミュレーションのモデルを視覚化した線図である。
【図８】バケット座標とバケット番号との関係を示すグラフである。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の一形態が図面に基づき説明される。
本発明は、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索する方法である。本実施形態の方法では、コンピュータ装置を使用して行われる。なお、前記実数群は、x[1]からx[n]まで連続した規則性はないものとする。
【００２５】
コンピュータ装置１は、図１に示されるように、中央演算装置２、作業用メモリである主記憶装置３、ハードディスク等の補助記憶装置４、キーボードないしマウス等の入力手段５、ディスプレイやプリンタ等を含む出力手段６及びこれらを接続するバス７とを含む。前記補助記憶装置には、本発明に係る方法を該コンピュータ装置１に実行させるためのプログラムが記憶されている。ただし、本発明は、このような態様に限定されるものではない。
【００２６】
本発明の探索方法は、図２に示されるように、探索用データベースを作る前処理ステップＳ１と、前記コンピュータ装置が前記探索データベースを使用して前記探索を行う探索ステップＳ２とが含まれる。
【００２７】
前記前処理ステップＳ１は、探索ステップＳ２の前に一度だけ実行される。そして、この前処理ステップＳ１において、探索ステップＳ２で必要になる探索用データベースが作成される。
【００２８】
探索用データベースは、図３に視覚化して示される。図３では、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）がある。前記探索用データベースは、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットＢで隙間無くかつ等間隔でｍ個に区分されたバケット列Ｂｒを有する。
【００２９】
［バケット］
バケットＢは、１次元の空間と言え、実数ｙ1と実数ｙ2を用いてｙ1≦ x[] ＜ｙ2を満たす空間として表すことができる。各バケットはいずれも同じ空間サイズを有し、前記実数群の区間（x[1]〜x[n]）を隙間無くかつ等間隔で分割している。
【００３０】
［バケット番号］
また、各バケットＢには、先頭バケットから末尾バケットまで順番に割り当てられた固有のバケット番号が定義される。この実施形態では、先頭バケットのバケット番号が１、末尾バケットのバケット番号がｍ、これらの間でバケット番号が１ずつ増加している。
【００３１】
［バケットサイズ］
さらに、各バケットには、その中に含まれる前記実数の個数であるバケットサイズが記憶される。この実施形態では、バケット番号１、２、６、９及び１０のバケットにそれぞれ１つの実数x[1]、x[2]、x[3] 、x[4] 、x[5] が含まれているので、これらのバケットサイズにはいずれも”１”が記憶される。また、実数を一つも含まないバケットには、”０”が記憶される。
【００３２】
［ラストフィルドバケット］
さらに、少なくとも前記先頭バケットを除いた各バケットには、ラストフィルドバケットが記憶される。ラストフィルドバケットは、前記バケットサイズがゼロでなくかつ当該バケット番号に最も近い近接バケット番号を示すラストフィルドバケットが記憶される。ここで「最も近い」とは、３つの意味を含むものとする。一番目の意味は、文字通り、当該バケットに最も近いという意味、二番目の意味は、当該バケットの先頭バケット側で最も近いという意味、三番目の意味は当該バケットの末尾バケット側で最も近いという意味である。本発明では、これらのいずれかの意味を選択して、実施することができる。
【００３３】
このラストフィルドバケットは、実数群をx[1]からx[n]までスキャンし、ｙ1≦ x[i] ＜ｙ2を満たすか否かを調べていく課程の中で、一番最後にバケットサイズが≠０となったときのバケットを、メモリ上に「ラストフィルドバケット」として記憶させておく。なお先頭バケットには、ラストフィルドバケットとして、自らのバケット番号を記憶させることができる。
【００３４】
さらに、探索用データベースの少なくともバケットサイズがゼロでないバケットＢには、そのバケット内の実数のうちの最小値及び最大値がさらに記憶されている。バケットサイズが１の場合、最小値及び最大値はいずれも同じ値である。
【００３５】
次に、この前処理ステップＳ１において探索用データベースを作成する具体的な処理手順の一例を図４に示す。
【００３６】
中央演算装置２は、前記実数群（x[1],x[2], x[3] … x[n]）を主記憶装置３に読み込む（ステップＳ１１）。
【００３７】
次に、中央演算装置２は、前記実数群の区間（x[1]〜x[n]）を前記バケットで隙間無くかつ等間隔でｍ個に区分する（ステップＳ１２）。これにより、１、２、３、… ｍのバケット番号を有するバケットが作られる。前記ｍは、０よりも大きい整数であり、ユーザにより決定される。そして、整数ｍは、予め入力手段５からコンピュータ装置１に入力されている。通常、前記整数ｍは、実数の組（x[1]、x[2]、 x[3] … x[n])の個数ｎの数倍大きな値をとるように定められるのが望ましい。
【００３８】
次に、中央演算装置２は、入力された前記整数ｍに基づき、前記主記憶装置３に、バケット番号、バケットサイズ、ラストフィルドバケット、最小値及び最大値を記憶するための領域をそれぞれｍ個割り当てる（ステップＳ１３）。
【００３９】
次に、中央演算装置２は、前記実数群（x[1],x[2], x[3] … x[n]）を各々のバケットに代入するとともに、割り当てられた主記憶装置３の各領域にそれぞれの値を記憶させる（ステップＳ１４）。この処理では、先ず、バケット総数を示す前記整数ｍと、実数の最小値x[1]、同最大値x[n]とを用いて、下式（１）にて各バケットの間隔Δxが計算される。
Δx＝（x[n] − x[1]）／ｍ …（１）
【００４０】
次に、中央演算装置２は、実数x[1]からx[n]まで、順番に次の計算を行う。即ち、現在の実数の値をx[i]とすると、x[i]がどのバケットに属しているのかを見つけるため、下記式（２）の計算を行う。
ibucket ＝ ＃切捨て(（x[i] − x[1]）／ Δx)＋１ …（２）
（ここで、「＃切り捨て」は、関数であり、戻り値として、小数点以下を切り捨てた整数値を返すものとする。）
【００４１】
ここで、 ibucket のバケット番号を持つバケット（これを[ibucket]として示す。）には、１つの実数x[i] を含むことが分かる。従って、中央演算装置２は、下記式（３）により、当該バケット[ibucket]に記憶されているバケットサイズの値を一つ増やす処理を行う。
バケットサイズ[ibucket] = 現在のバケットサイズ＋１ … （３）
【００４２】
また、この処理で新たにバケット[ibucket]内にx[i]が入るので、中央演算装置２は、最小値又は最大値を書き換える必要が生じたときには、それらの値を書き換える。
【００４３】
次に、バケットサイズ、最小値、最大値が全てのバケットに対して決定されるが、この例では、いくつかのバケットは、そのバケットサイズが０となり、実数x[]とは無関係になっていることが分かる。この様なバケットサイズ＝０のバケットについては、無視して検索対象から除外するのが得策である。
【００４４】
次に、中央演算装置２は、先頭バケットを除いて、各バケットのラストフィルドバケットを計算し、かつ、記憶させる（ステップＳ１５）。この実施形態では、ラストフィルドバケットは、バケットサイズがゼロでなくかつ当該バケットに先頭バケット側で最も近い（即ち、前記二番目の意味）バケットのバケット番号として定義される。これは、現在のバケットのバケット番号をｋ、ラストフィルドバケットをｐとすると次の条件ａないしｃで表すことができる。
（ａ）ｐ＜ｋ
（ｂ）バケット番号ｐのバケットサイズ≠０
（ｃ）ｋ−ｐが最小値
【００４５】
また、中央演算装置２がラストフィルドバケットを決定する処理手順の一例は図５に示される。
【００４６】
次に、中央演算装置２は、変数ＬＦＢ及び変数ｋにそれぞれ１を代入し（ステップＳ２０、Ｓ２１）、バケット番号ｋについて、バケットサイズが０より大きいかを判断する（ステップＳ２２）。
【００４７】
ステップＳ２２で結果が真（Ｙ）の場合、中央演算装置２は、バケット番号ｋのラストフィルドバケットの値に、現在の変数ＬＦＢの値を代入する（ステップＳ２３）。その後、中央演算装置２は、変数ＬＦＢの値を、現在のバケット番号ｋに更新し（ステップＳ２４）、ステップＳ２５を実行する。
【００４８】
他方、ステップＳ２２で結果が偽（Ｎｏ）の場合、バケット番号ｋのラストフィルドバケットの値に、現在の変数ＬＦＢの値を代入するが（ステップＳ２６）、変数ＬＦＢの値は更新せずに、ステップＳ２５を実行する。
【００４９】
ステップＳ２５では、現在のバケット番号ｋが末尾バケット（即ち、ｋ＝ｍ）かを判断し、結果が真（Ｙｅｓ）の場合には処理を終える。他方、ステップＳ２５の結果が偽（Ｎｏ）の場合、変数ｋに１を加算し（ステップＳ２７）、末尾バケットになるまでステップＳ２２以降を繰り返す。
【００５０】
以上の処理により、前処理ステップが完了し、探索用データベースが作成される。なお、探索用データベースは、アクセス速度が早い主記憶装置３上に設けられるのが好ましいが、補助記憶装置に作成されても良い。
【００５１】
次に、前記探索ステップでは、前記探索用データベースを使用して、図６の処理が行われる。先ず、探索点ｑが与えられたとき（ステップＳ３０）、中央演算装置２は、前記探索点ｑが属するバケットのバケット番号（ibucket）を計算する（第１のステップ：ステップＳ３１）。この計算は、バケットが等間隔で設定されているため、単純な下記式（４）の一次式で所定のバケット見つけることができる。
ibucket ＝ ＃切捨て(（ｑ − x[1]）／ Δx)＋１ …（４）
ここで、「＃切り捨て」は、関数であり、戻り値として、小数点以下を切り捨てた整数値を返すものとする。また、Δｘは、上記式（１）で表される。
【００５２】
次に、中央演算装置２は、前記計算されたバケット（ibucket）のバケットサイズを参照し、０か否かを判断する（ステップＳ３２）。もし、バケットサイズが０でない場合（ステップＳ３２でＮｏ）、当該参照されたバケットの中から最近傍値を計算する（ステップＳ３３、Ｓ３４）。
【００５３】
具体的には、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、探索点ｑが最小値よりも小さい場合（ステップＳ３３でＹｅｓ）、そのバケットのラストフィルドバケットの最大値を最近傍値とする（ステップＳ３５）。
【００５４】
また、ステップＳ３３でＮｏ、即ち、バケットサイズが０でなく、かつ、探索点ｑがそのバケットの最小値以上の場合には、そのバケットに含まれる実数に対してx[ ipoint ] ≦ｑ＜x[ ipoint + 1 ]となるx[ ipoint ] を最近傍値とする（ステップＳ３４）。
【００５５】
一方、中央演算装置２は、前記参照されたバケットサイズが０の場合（ステップＳ３２でＹｅｓ）、そのバケットのラストフィルドバケットが示すバケットから前記最近傍値を計算する（ステップＳ３５）。
【００５６】
このように、本実施形態の方法によれば、ステップＳ３２以降、一つのバケットだけを対象とし、その中の実数から最近傍値を見つけることができる。このため、計算時間を大幅に短縮することができる。
【００５７】
なお、上記実施形態では、前記最近傍値は、前記探索点ｑを超えずかつ該探索点に最も近い値として定義されているが、例えば、最近傍値は、前記探索点ｑを下回らない該探索点に最も近い値として定義されても良い。この場合、前記ラストフィルドバケットは、当該バケットよりも末尾バケット側で当該バケットに最も近いバケット番号を記憶させれば良い。また、ステップＳ３５については、「最大値」を「最小値」と読み替えれば良い。また、ステップＳ３３については、「最小値」を「最大値」と読み替える。さらに、ステップＳ３４については、x[ ipoint ] ≧ｑ＞x[ ipoint-1 ]となるx[ ipoint ] を最近傍値とすれば良い。
【実施例】
【００５８】
［実施例１］
次に、図７を用いて具体的な実施例について述べる。
図７には、二次元のゴルフボールの空力シミュレーションの計算モデルが視覚化して示され、ゴルフボールをモデル化したラグランジュ要素からなるゴルフボールモデル１０と、このゴルフボールモデル１０の周囲の空気の流れを再現する空間場である直交格子からなるオイラー要素からなる空気モデル１１とを含む。
【００５９】
ゴルフボールモデル１０は、節点１０ａと、これらを継ぐ辺１０ｂとによって定義される。節点１０ａは、（ｘ、ｙ）の座標値を持つ。
【００６０】
また、空気モデル１１は、予め設定された格子に区分されているが、この実施形態では、ゴルフボールモデル１０の表面近傍の空気の流れをより詳細に解析するために、ゴルフボールモデル１０に近い部分は比較的小さいピッチの格子をなし、ゴルフボールモデル１０から遠ざかるについてピッチが大きくなっている。このように、空気モデル１は、非均等なピッチの格子構造を持つ。
【００６１】
いま、任意のｙ座標値（ｙ1）上のゴルフボールモデル１０の節点のｘ座標値が、探索点ｑとして与えられ、この探索点ｑを超えずかつこの探索点ｑに最も近い空気モデル１１のｘ座標を最近傍値として探索するものとする。
【００６２】
表１には、空気モデルのｘ座標を、実数群のｘ座標として扱った探索用データベースファイルを視覚化して示す。
【００６３】
【表１】
【００６４】
この実施例の探索用データベースは、バケットの間隔Δx＝１．６とした。また、バケット番号は先頭バケットを１とし、末尾バケットまで１ずつ増えるように番号付けされている。そして、例えばバケット番号１のバケットには、前記実数群から０以上かつ１．６未満の値が取り込まれる。また、探索用データベースには、前述のバケットサイズ、ラストフィルドバケット、最小値及び最大値がそれぞれ記憶されている。
【００６５】
また、図８には、バケットｘ座標と、バケット番号とのグラフを示している。表１及び図８から明らかなように、この実施例では、バケット番号が小さいバケットほど、多くの実数が格納されるように定められているが、このような態様に限定されるものではない。
【００６６】
いま探索点ｑのｘ座標値が５２である場合、この値がどのバケット（ibucket）に属しているのかが、前記式（２）により計算される。この結果、探索点ｑが属するバケットは、バケット番号３３であることが分かる。
ibucket ＝ ＃切捨て（（５２ − ０）／ １．６）＋１＝３３
（ここで、「＃切り捨て」は、関数であり、戻り値として、小数点以下を切り捨てた整数値を返すものとする。）
【００６７】
次に、中央演算装置は、バケット番号３３のバケットサイズを調べる。結果は”０”であるため、そのラストフィルドバケットであるバケット番号３１の最大値、即ち”４９．２８４”を最近傍値として得る。
【００６８】
他方、探索点ｑのｘ座標値が７の場合、そのibucketは”５”となる。バケット番号５のバケットサイズは”２”であり”０”ではない。従って、この場合、中央演算装置は、当該参照されたバケット番号５に格納されている実数から最近傍値を計算する。この例では、探索点ｑ（＝７）が、そのバケットの最小値（＝６．４９８）よりも小さいか否かが判断される。この場合、結果は偽（False）となる。この場合には、バケット番号５に含まれる実数に対してx[ ipoint ] ≦ｑ＜x[ ipoint + 1 ]となるx[ ipoint ] が最近傍値として計算され、６．４９８をすぐに計算することができる。
【００６９】
［実施例２］
次に、さらに大規模な計算モデルを用いて本発明の効果を述べる。
三次元の空気モデルＡとして、ｘ−ｙ−ｚの各座標値の個数が、それぞれ２５２、１００及び２５０２個（合計６３０５０４００個の座標値）の実数群に対して、３７５５５９８個のラグランジュ要素の節点座標値（探索点）を与え、それぞれの最近傍値の探索が行われた。
【００７０】
また、三次元の空気モデルＢとして、ｘ−ｙ−ｚの各座標値の個数が、それぞれ５０２、１００及び３００２個（合計１５０７００４００個の座標値）の実数群に対して、３７５５５９８個の探索点を与え、上記同様にそれらの最近傍値の探索が行われた。空気モデルＢは、空気モデルＡの約２．４倍の実数群を具えるものである。
【００７１】
探索方法には、本発明方法の他、ＡＮＮ（従来例）を用いた。ＡＮＮは、バケットサイズを１及び３の２種類でテストされた。テストの結果は、表２の通りであるが、本発明方法は、探索時間を顕著に削減できることが確認できた。なお、各空気モデルＡ、Ｂについての探索用データベース作成時間は、本発明方法では０．０１秒以下、従来例では約５秒であった。
【００７２】
【表２】
【産業上の利用可能性】
【００７３】
例えば、ゴルフボール（構造体）の周りの空気（流体）の流れ、タイヤ製造工程における押出機（構造体）の内部の可塑化したゴム（流体）の流れ等のシミュレーション（数値計算）を実施する場合、流体部分を構造格子のオイラーメッシュで定義する一方、構造体を非構造格子のラグランジュメッシュでモデル化し、ボールの回転や、スクリューの回転を考慮した計算を実施することは、モデル作成にかかる工数を低減でき、かつ、計算精度を上げやすい等のメリットがあり、非常に有用である。従って、大規模な数値計算を実施するときには、今後、構造格子の利用が増加すると考えられるが、構造格子を用いる場合、構造物が複雑な形状であると、流体と構造体の境界を認識する必要が生じ、計算コストが莫大になっていた。
【００７４】
本発明は、この種の計算に最適に利用され、大幅に計算時間を短縮し、計算コストを低減できる。なお、ゴルフボールの流体解析は、通常、３次元空間で行う必要があるため、構造格子の構成は、直交座標系では（ｘ，ｙ，ｚ）、円筒座標系では（ｒ，ｚ、θ）、球座標系では（ｒ、θ、φ）となるが、それぞれの座標について、１次元毎に本発明の探索を行うことにより、大幅な計算時間短縮を実現しうる。具体的には、従来の探索手法（ANNや、kd-tree）を用いるよりも、２倍以上の速さで探索が可能になる。これは、例えば、ゴルフボールを回転させる移動境界の計算で、特に計算効率が高くなり、より多い格子数での計算が可能となるため、空間の近似精度が高まり、計算精度の向上をもたらす。また、ＡＮＮ等の従来の手法では、構造物（ラグランジュ要素）が移動するたびに、探索の全ての工程を繰り返す必要があるが、本発明では、このような必要はない。
【符号の説明】
【００７５】
１ コンピュータ装置
２ 中央演算装置
３ 主記憶装置
５ 入力手段
６ 出力手段
【技術分野】
【０００１】
本発明は、コンピュータを利用した計算方法であり、任意の実数群から探索点の最近傍値を高速に探索することができる方法に関する。
【背景技術】
【０００２】
コンピュータを用いた数値計算において、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索しなければならない場合がある。このような状況の例としては、コンピュータを使用した例えば空力シミュレーション計算において、運動する物体（ラグランジュ要素）の表面座標を、構造格子（オイラー要素）の座標系に取り込む場合等が挙げられる。
【０００３】
しかしながら、上記実数群(x[1],x[2], x[3] … x[n])のサイズが大きくなった場合（例えばｎが１億を超えるような場合）、探索対象となる実数ｑの数が多い場合（例えば１００万を超える様な場合）、又はこのような探索を繰り返し何度も行う場合、計算時間が数時間にも及ぶ場合がある。従って、計算コストを低減するために、従来より、上述の計算時間を短縮する試みが種々提案されている。
【０００４】
従来、この種の課題を解決するために、大きく分けて下記二つの方法が提案されている。第１の方法は、実数x[1] からx[n]まで順番にｑと値の大小を比較し、大小関係が逆転する値が見つかるまで探索する方法である。この場合、例えば、下式に示す条件を満たすインデックス（ ipoint ）が見つかれば、そのインデックス（ ipoint ） が解となる。
x[ipoint] ≦ ｑ ＜ x[ipoint+1]
【０００５】
また、他の方法として、２分法（bisection method）又はkd-tree methodが提案されている。これらの方法は、近年、良く使用されている探索手法であり、上記方法よりも効率良く探索点ｑに近い数を見つけることができる。
【０００６】
さらに、近年では、これらの二つの手法を組み合わせたＡＮＮ(Approximate Nearest Neighbor)解法も提案されている。
【０００７】
関連する先行技術としては次のものがある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００３−２４２１５１号公報
【非特許文献】
【０００９】
【非特許文献１】荒井英剛、他２名共著、「空間分割と直交変換の統合による高次元最近傍探索の高速化」 社団法人情報処理学会研究報告 2006/3/16
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来の方法では、探索する対象が増え多次元になるほどその効果が減少し、３０次元程度からほぼ全探索に近くなる。また、探索規模が大きくなるほど、ツリー構造が複雑化し、探索範囲も大きくなり計算に多くの時間を要するという欠点がある。
【００１１】
本発明は、以上のような問題点に鑑み案出なされたもので、探索に先立ち、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットで隙間無くかつ等間隔に区分した探索用データベースを作成し、そこに所定の情報を記憶させることにより、計算時間を大幅に短縮しうる任意の実数群から探索点の最近傍値を探索する方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明のうち請求項１記載の発明は、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索する方法であって、コンピュータ装置の記憶部に、探索用データベースを作る前処理ステップと、前記コンピュータ装置が前記探索データベースを使用して前記探索を行う探索ステップとを含み、前記探索用データベースは、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットで隙間無くかつ等間隔でｍ個に区分されたバケット列を有し、前記各バケットには、先頭バケットから末尾バケットまで順番に割り当てられた固有のバケット番号と、各バケットの中に含まれる前記実数の個数であるバケットサイズとが記憶されるとともに、少なくとも前記先頭バケットを除いた各バケットには、前記バケットサイズがゼロでなくかつ当該バケットに最も近いバケットのバケット番号を示すラストフィルドバケットが記憶され、前記探索ステップは、前記探索点ｑが属するバケットを計算する第１のステップと、前記計算されたバケットのバケットサイズを参照する第２のステップと、前記参照されたバケットサイズが０でない場合、当該参照されたバケットから最近傍値を計算する一方、前記参照されたバケットサイズが０の場合、そのバケットのラストフィルドバケットが示すバケットから前記最近傍値を計算する第３のステップとを含むことを特徴とする。
【００１３】
また請求項２記載の発明は、前記最近傍値は、前記探索点を超えない該探索点に最も近い値とし、前記探索用データベースには、前記ラストフィルドバケットとして、当該バケットよりも先頭バケット側で当該バケット番号に最も近いバケット番号が記憶されている請求項１記載の最近傍値を探索する方法である。
【００１４】
また請求項３記載の発明は、前記探索用データベースの少なくともバケットサイズが０でないバケットには、そのバケット内の実数のうちの最小値及び最大値がさらに記憶されている請求項２記載の最近傍値を探索する方法である。
【００１５】
また請求項４記載の発明は、前記第２のステップにおいて、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、探索点ｑが最小値よりも小さい場合には、そのバケットのラストフィルドバケットの最大値を最近傍値とする請求項３記載の最近傍値を探索する方法である。
【００１６】
また請求項５記載の発明は、前記第２のステップにおいて、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、前記探索点ｑが最小値以上の場合には、そのバケットに含まれる実数に対してx[ ipoint ] ≦ｑ＜x[ ipoint + 1 ]となるx[ ipoint ] を最近傍値とする請求項３又は４記載の最近傍値を探索する方法である。
【００１７】
また請求項６記載の発明は、複数の多次元の座標値（x,y,z…）が与えられており、探索点ｑ（x1,y1,z1）が与えられたとき、前記座標値を各次元毎の実数群に分け、
各実数群に対して請求項１乃至５のいずれかに記載された探索方法を適用することで前記探索点ｑの各座標に最も近い最近傍値を各次元の実数群の中からそれぞれ探索することを特徴とする最近傍値を探索する方法である。
【発明の効果】
【００１８】
本発明では、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索する方法として、コンピュータ装置の記憶部に、探索用データベースを作るステップと、前記コンピュータ装置が前記探索データベースを使用して前記探索を行う探索ステップとを含む。
【００１９】
前記探索用データベースは、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットで隙間無くかつ等間隔でｍ個に区分されたバケット列を有し、前記各バケットには、先頭バケットから末尾バケットまで順番に割り当てられた固有のバケット番号と、各バケットの中に含まれる前記実数の個数であるバケットサイズとが記憶される。また、探索用データベースは、少なくとも前記先頭バケットを除いた各バケットに、バケットサイズがゼロでなくかつ当該バケット番号に最も近い近接バケット番号を示すラストフィルドバケットが記憶される。なお先頭バケットには、例えばラストフィルドバケットとして、自らのバケット番号を記憶させることができる。
【００２０】
次に、探索ステップでは、前記探索点ｑが属するバケットを計算する第１のステップと、前記計算されたバケットのバケットサイズを参照する第２のステップと、前記参照されたバケットサイズが０でない場合、当該参照されたバケットから最近傍値を計算する一方、前記参照されたバケットサイズが０の場合、そのバケットのラストフィルドバケットが示すバケットから前記最近傍値を計算する第３のステップとを含む。
【００２１】
バケットは、等間隔で設定されている。従って、前記第１のステップは、単純な一次式で所定のバケットを見つけることができる。
【００２２】
また、第３のステップでは、参照されたバケットのバケットサイズが０ではない場合、当該バケットに含まれる実数から、また、バケットサイズが０の場合にはそのバケットに記憶されているラストフィルドバケットに含まれる実数から最近傍値をそれぞれ計算できる。従って、第３のステップでは、いずれの場合でも、一つのバケットだけを対象とし、その中の実数から最近傍値を見つければ良い。このため、計算時間を大幅に低減することができる。
【図面の簡単な説明】
【００２３】
【図１】本発明の探索を行うコンピュータ装置のブロック図である。
【図２】本発明の探索方法の処理手順を示すフローチャートである。
【図３】実数群及び探索用データベースの構造を示す線図である。
【図４】探索用データベースを作成する処理手順を示すフローチャートである。
【図５】ラストフィルドバケットを決定する処理手順の一例を示すフローチャートである。
【図６】探索ステップの処理手順の一例を示すフローチャートである。
【図７】空力シミュレーションのモデルを視覚化した線図である。
【図８】バケット座標とバケット番号との関係を示すグラフである。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の一形態が図面に基づき説明される。
本発明は、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索する方法である。本実施形態の方法では、コンピュータ装置を使用して行われる。なお、前記実数群は、x[1]からx[n]まで連続した規則性はないものとする。
【００２５】
コンピュータ装置１は、図１に示されるように、中央演算装置２、作業用メモリである主記憶装置３、ハードディスク等の補助記憶装置４、キーボードないしマウス等の入力手段５、ディスプレイやプリンタ等を含む出力手段６及びこれらを接続するバス７とを含む。前記補助記憶装置には、本発明に係る方法を該コンピュータ装置１に実行させるためのプログラムが記憶されている。ただし、本発明は、このような態様に限定されるものではない。
【００２６】
本発明の探索方法は、図２に示されるように、探索用データベースを作る前処理ステップＳ１と、前記コンピュータ装置が前記探索データベースを使用して前記探索を行う探索ステップＳ２とが含まれる。
【００２７】
前記前処理ステップＳ１は、探索ステップＳ２の前に一度だけ実行される。そして、この前処理ステップＳ１において、探索ステップＳ２で必要になる探索用データベースが作成される。
【００２８】
探索用データベースは、図３に視覚化して示される。図３では、実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）がある。前記探索用データベースは、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットＢで隙間無くかつ等間隔でｍ個に区分されたバケット列Ｂｒを有する。
【００２９】
［バケット］
バケットＢは、１次元の空間と言え、実数ｙ1と実数ｙ2を用いてｙ1≦ x[] ＜ｙ2を満たす空間として表すことができる。各バケットはいずれも同じ空間サイズを有し、前記実数群の区間（x[1]〜x[n]）を隙間無くかつ等間隔で分割している。
【００３０】
［バケット番号］
また、各バケットＢには、先頭バケットから末尾バケットまで順番に割り当てられた固有のバケット番号が定義される。この実施形態では、先頭バケットのバケット番号が１、末尾バケットのバケット番号がｍ、これらの間でバケット番号が１ずつ増加している。
【００３１】
［バケットサイズ］
さらに、各バケットには、その中に含まれる前記実数の個数であるバケットサイズが記憶される。この実施形態では、バケット番号１、２、６、９及び１０のバケットにそれぞれ１つの実数x[1]、x[2]、x[3] 、x[4] 、x[5] が含まれているので、これらのバケットサイズにはいずれも”１”が記憶される。また、実数を一つも含まないバケットには、”０”が記憶される。
【００３２】
［ラストフィルドバケット］
さらに、少なくとも前記先頭バケットを除いた各バケットには、ラストフィルドバケットが記憶される。ラストフィルドバケットは、前記バケットサイズがゼロでなくかつ当該バケット番号に最も近い近接バケット番号を示すラストフィルドバケットが記憶される。ここで「最も近い」とは、３つの意味を含むものとする。一番目の意味は、文字通り、当該バケットに最も近いという意味、二番目の意味は、当該バケットの先頭バケット側で最も近いという意味、三番目の意味は当該バケットの末尾バケット側で最も近いという意味である。本発明では、これらのいずれかの意味を選択して、実施することができる。
【００３３】
このラストフィルドバケットは、実数群をx[1]からx[n]までスキャンし、ｙ1≦ x[i] ＜ｙ2を満たすか否かを調べていく課程の中で、一番最後にバケットサイズが≠０となったときのバケットを、メモリ上に「ラストフィルドバケット」として記憶させておく。なお先頭バケットには、ラストフィルドバケットとして、自らのバケット番号を記憶させることができる。
【００３４】
さらに、探索用データベースの少なくともバケットサイズがゼロでないバケットＢには、そのバケット内の実数のうちの最小値及び最大値がさらに記憶されている。バケットサイズが１の場合、最小値及び最大値はいずれも同じ値である。
【００３５】
次に、この前処理ステップＳ１において探索用データベースを作成する具体的な処理手順の一例を図４に示す。
【００３６】
中央演算装置２は、前記実数群（x[1],x[2], x[3] … x[n]）を主記憶装置３に読み込む（ステップＳ１１）。
【００３７】
次に、中央演算装置２は、前記実数群の区間（x[1]〜x[n]）を前記バケットで隙間無くかつ等間隔でｍ個に区分する（ステップＳ１２）。これにより、１、２、３、… ｍのバケット番号を有するバケットが作られる。前記ｍは、０よりも大きい整数であり、ユーザにより決定される。そして、整数ｍは、予め入力手段５からコンピュータ装置１に入力されている。通常、前記整数ｍは、実数の組（x[1]、x[2]、 x[3] … x[n])の個数ｎの数倍大きな値をとるように定められるのが望ましい。
【００３８】
次に、中央演算装置２は、入力された前記整数ｍに基づき、前記主記憶装置３に、バケット番号、バケットサイズ、ラストフィルドバケット、最小値及び最大値を記憶するための領域をそれぞれｍ個割り当てる（ステップＳ１３）。
【００３９】
次に、中央演算装置２は、前記実数群（x[1],x[2], x[3] … x[n]）を各々のバケットに代入するとともに、割り当てられた主記憶装置３の各領域にそれぞれの値を記憶させる（ステップＳ１４）。この処理では、先ず、バケット総数を示す前記整数ｍと、実数の最小値x[1]、同最大値x[n]とを用いて、下式（１）にて各バケットの間隔Δxが計算される。
Δx＝（x[n] − x[1]）／ｍ …（１）
【００４０】
次に、中央演算装置２は、実数x[1]からx[n]まで、順番に次の計算を行う。即ち、現在の実数の値をx[i]とすると、x[i]がどのバケットに属しているのかを見つけるため、下記式（２）の計算を行う。
ibucket ＝ ＃切捨て(（x[i] − x[1]）／ Δx)＋１ …（２）
（ここで、「＃切り捨て」は、関数であり、戻り値として、小数点以下を切り捨てた整数値を返すものとする。）
【００４１】
ここで、 ibucket のバケット番号を持つバケット（これを[ibucket]として示す。）には、１つの実数x[i] を含むことが分かる。従って、中央演算装置２は、下記式（３）により、当該バケット[ibucket]に記憶されているバケットサイズの値を一つ増やす処理を行う。
バケットサイズ[ibucket] = 現在のバケットサイズ＋１ … （３）
【００４２】
また、この処理で新たにバケット[ibucket]内にx[i]が入るので、中央演算装置２は、最小値又は最大値を書き換える必要が生じたときには、それらの値を書き換える。
【００４３】
次に、バケットサイズ、最小値、最大値が全てのバケットに対して決定されるが、この例では、いくつかのバケットは、そのバケットサイズが０となり、実数x[]とは無関係になっていることが分かる。この様なバケットサイズ＝０のバケットについては、無視して検索対象から除外するのが得策である。
【００４４】
次に、中央演算装置２は、先頭バケットを除いて、各バケットのラストフィルドバケットを計算し、かつ、記憶させる（ステップＳ１５）。この実施形態では、ラストフィルドバケットは、バケットサイズがゼロでなくかつ当該バケットに先頭バケット側で最も近い（即ち、前記二番目の意味）バケットのバケット番号として定義される。これは、現在のバケットのバケット番号をｋ、ラストフィルドバケットをｐとすると次の条件ａないしｃで表すことができる。
（ａ）ｐ＜ｋ
（ｂ）バケット番号ｐのバケットサイズ≠０
（ｃ）ｋ−ｐが最小値
【００４５】
また、中央演算装置２がラストフィルドバケットを決定する処理手順の一例は図５に示される。
【００４６】
次に、中央演算装置２は、変数ＬＦＢ及び変数ｋにそれぞれ１を代入し（ステップＳ２０、Ｓ２１）、バケット番号ｋについて、バケットサイズが０より大きいかを判断する（ステップＳ２２）。
【００４７】
ステップＳ２２で結果が真（Ｙ）の場合、中央演算装置２は、バケット番号ｋのラストフィルドバケットの値に、現在の変数ＬＦＢの値を代入する（ステップＳ２３）。その後、中央演算装置２は、変数ＬＦＢの値を、現在のバケット番号ｋに更新し（ステップＳ２４）、ステップＳ２５を実行する。
【００４８】
他方、ステップＳ２２で結果が偽（Ｎｏ）の場合、バケット番号ｋのラストフィルドバケットの値に、現在の変数ＬＦＢの値を代入するが（ステップＳ２６）、変数ＬＦＢの値は更新せずに、ステップＳ２５を実行する。
【００４９】
ステップＳ２５では、現在のバケット番号ｋが末尾バケット（即ち、ｋ＝ｍ）かを判断し、結果が真（Ｙｅｓ）の場合には処理を終える。他方、ステップＳ２５の結果が偽（Ｎｏ）の場合、変数ｋに１を加算し（ステップＳ２７）、末尾バケットになるまでステップＳ２２以降を繰り返す。
【００５０】
以上の処理により、前処理ステップが完了し、探索用データベースが作成される。なお、探索用データベースは、アクセス速度が早い主記憶装置３上に設けられるのが好ましいが、補助記憶装置に作成されても良い。
【００５１】
次に、前記探索ステップでは、前記探索用データベースを使用して、図６の処理が行われる。先ず、探索点ｑが与えられたとき（ステップＳ３０）、中央演算装置２は、前記探索点ｑが属するバケットのバケット番号（ibucket）を計算する（第１のステップ：ステップＳ３１）。この計算は、バケットが等間隔で設定されているため、単純な下記式（４）の一次式で所定のバケット見つけることができる。
ibucket ＝ ＃切捨て(（ｑ − x[1]）／ Δx)＋１ …（４）
ここで、「＃切り捨て」は、関数であり、戻り値として、小数点以下を切り捨てた整数値を返すものとする。また、Δｘは、上記式（１）で表される。
【００５２】
次に、中央演算装置２は、前記計算されたバケット（ibucket）のバケットサイズを参照し、０か否かを判断する（ステップＳ３２）。もし、バケットサイズが０でない場合（ステップＳ３２でＮｏ）、当該参照されたバケットの中から最近傍値を計算する（ステップＳ３３、Ｓ３４）。
【００５３】
具体的には、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、探索点ｑが最小値よりも小さい場合（ステップＳ３３でＹｅｓ）、そのバケットのラストフィルドバケットの最大値を最近傍値とする（ステップＳ３５）。
【００５４】
また、ステップＳ３３でＮｏ、即ち、バケットサイズが０でなく、かつ、探索点ｑがそのバケットの最小値以上の場合には、そのバケットに含まれる実数に対してx[ ipoint ] ≦ｑ＜x[ ipoint + 1 ]となるx[ ipoint ] を最近傍値とする（ステップＳ３４）。
【００５５】
一方、中央演算装置２は、前記参照されたバケットサイズが０の場合（ステップＳ３２でＹｅｓ）、そのバケットのラストフィルドバケットが示すバケットから前記最近傍値を計算する（ステップＳ３５）。
【００５６】
このように、本実施形態の方法によれば、ステップＳ３２以降、一つのバケットだけを対象とし、その中の実数から最近傍値を見つけることができる。このため、計算時間を大幅に短縮することができる。
【００５７】
なお、上記実施形態では、前記最近傍値は、前記探索点ｑを超えずかつ該探索点に最も近い値として定義されているが、例えば、最近傍値は、前記探索点ｑを下回らない該探索点に最も近い値として定義されても良い。この場合、前記ラストフィルドバケットは、当該バケットよりも末尾バケット側で当該バケットに最も近いバケット番号を記憶させれば良い。また、ステップＳ３５については、「最大値」を「最小値」と読み替えれば良い。また、ステップＳ３３については、「最小値」を「最大値」と読み替える。さらに、ステップＳ３４については、x[ ipoint ] ≧ｑ＞x[ ipoint-1 ]となるx[ ipoint ] を最近傍値とすれば良い。
【実施例】
【００５８】
［実施例１］
次に、図７を用いて具体的な実施例について述べる。
図７には、二次元のゴルフボールの空力シミュレーションの計算モデルが視覚化して示され、ゴルフボールをモデル化したラグランジュ要素からなるゴルフボールモデル１０と、このゴルフボールモデル１０の周囲の空気の流れを再現する空間場である直交格子からなるオイラー要素からなる空気モデル１１とを含む。
【００５９】
ゴルフボールモデル１０は、節点１０ａと、これらを継ぐ辺１０ｂとによって定義される。節点１０ａは、（ｘ、ｙ）の座標値を持つ。
【００６０】
また、空気モデル１１は、予め設定された格子に区分されているが、この実施形態では、ゴルフボールモデル１０の表面近傍の空気の流れをより詳細に解析するために、ゴルフボールモデル１０に近い部分は比較的小さいピッチの格子をなし、ゴルフボールモデル１０から遠ざかるについてピッチが大きくなっている。このように、空気モデル１は、非均等なピッチの格子構造を持つ。
【００６１】
いま、任意のｙ座標値（ｙ1）上のゴルフボールモデル１０の節点のｘ座標値が、探索点ｑとして与えられ、この探索点ｑを超えずかつこの探索点ｑに最も近い空気モデル１１のｘ座標を最近傍値として探索するものとする。
【００６２】
表１には、空気モデルのｘ座標を、実数群のｘ座標として扱った探索用データベースファイルを視覚化して示す。
【００６３】
【表１】
【００６４】
この実施例の探索用データベースは、バケットの間隔Δx＝１．６とした。また、バケット番号は先頭バケットを１とし、末尾バケットまで１ずつ増えるように番号付けされている。そして、例えばバケット番号１のバケットには、前記実数群から０以上かつ１．６未満の値が取り込まれる。また、探索用データベースには、前述のバケットサイズ、ラストフィルドバケット、最小値及び最大値がそれぞれ記憶されている。
【００６５】
また、図８には、バケットｘ座標と、バケット番号とのグラフを示している。表１及び図８から明らかなように、この実施例では、バケット番号が小さいバケットほど、多くの実数が格納されるように定められているが、このような態様に限定されるものではない。
【００６６】
いま探索点ｑのｘ座標値が５２である場合、この値がどのバケット（ibucket）に属しているのかが、前記式（２）により計算される。この結果、探索点ｑが属するバケットは、バケット番号３３であることが分かる。
ibucket ＝ ＃切捨て（（５２ − ０）／ １．６）＋１＝３３
（ここで、「＃切り捨て」は、関数であり、戻り値として、小数点以下を切り捨てた整数値を返すものとする。）
【００６７】
次に、中央演算装置は、バケット番号３３のバケットサイズを調べる。結果は”０”であるため、そのラストフィルドバケットであるバケット番号３１の最大値、即ち”４９．２８４”を最近傍値として得る。
【００６８】
他方、探索点ｑのｘ座標値が７の場合、そのibucketは”５”となる。バケット番号５のバケットサイズは”２”であり”０”ではない。従って、この場合、中央演算装置は、当該参照されたバケット番号５に格納されている実数から最近傍値を計算する。この例では、探索点ｑ（＝７）が、そのバケットの最小値（＝６．４９８）よりも小さいか否かが判断される。この場合、結果は偽（False）となる。この場合には、バケット番号５に含まれる実数に対してx[ ipoint ] ≦ｑ＜x[ ipoint + 1 ]となるx[ ipoint ] が最近傍値として計算され、６．４９８をすぐに計算することができる。
【００６９】
［実施例２］
次に、さらに大規模な計算モデルを用いて本発明の効果を述べる。
三次元の空気モデルＡとして、ｘ−ｙ−ｚの各座標値の個数が、それぞれ２５２、１００及び２５０２個（合計６３０５０４００個の座標値）の実数群に対して、３７５５５９８個のラグランジュ要素の節点座標値（探索点）を与え、それぞれの最近傍値の探索が行われた。
【００７０】
また、三次元の空気モデルＢとして、ｘ−ｙ−ｚの各座標値の個数が、それぞれ５０２、１００及び３００２個（合計１５０７００４００個の座標値）の実数群に対して、３７５５５９８個の探索点を与え、上記同様にそれらの最近傍値の探索が行われた。空気モデルＢは、空気モデルＡの約２．４倍の実数群を具えるものである。
【００７１】
探索方法には、本発明方法の他、ＡＮＮ（従来例）を用いた。ＡＮＮは、バケットサイズを１及び３の２種類でテストされた。テストの結果は、表２の通りであるが、本発明方法は、探索時間を顕著に削減できることが確認できた。なお、各空気モデルＡ、Ｂについての探索用データベース作成時間は、本発明方法では０．０１秒以下、従来例では約５秒であった。
【００７２】
【表２】
【産業上の利用可能性】
【００７３】
例えば、ゴルフボール（構造体）の周りの空気（流体）の流れ、タイヤ製造工程における押出機（構造体）の内部の可塑化したゴム（流体）の流れ等のシミュレーション（数値計算）を実施する場合、流体部分を構造格子のオイラーメッシュで定義する一方、構造体を非構造格子のラグランジュメッシュでモデル化し、ボールの回転や、スクリューの回転を考慮した計算を実施することは、モデル作成にかかる工数を低減でき、かつ、計算精度を上げやすい等のメリットがあり、非常に有用である。従って、大規模な数値計算を実施するときには、今後、構造格子の利用が増加すると考えられるが、構造格子を用いる場合、構造物が複雑な形状であると、流体と構造体の境界を認識する必要が生じ、計算コストが莫大になっていた。
【００７４】
本発明は、この種の計算に最適に利用され、大幅に計算時間を短縮し、計算コストを低減できる。なお、ゴルフボールの流体解析は、通常、３次元空間で行う必要があるため、構造格子の構成は、直交座標系では（ｘ，ｙ，ｚ）、円筒座標系では（ｒ，ｚ、θ）、球座標系では（ｒ、θ、φ）となるが、それぞれの座標について、１次元毎に本発明の探索を行うことにより、大幅な計算時間短縮を実現しうる。具体的には、従来の探索手法（ANNや、kd-tree）を用いるよりも、２倍以上の速さで探索が可能になる。これは、例えば、ゴルフボールを回転させる移動境界の計算で、特に計算効率が高くなり、より多い格子数での計算が可能となるため、空間の近似精度が高まり、計算精度の向上をもたらす。また、ＡＮＮ等の従来の手法では、構造物（ラグランジュ要素）が移動するたびに、探索の全ての工程を繰り返す必要があるが、本発明では、このような必要はない。
【符号の説明】
【００７５】
１ コンピュータ装置
２ 中央演算装置
３ 主記憶装置
５ 入力手段
６ 出力手段
【特許請求の範囲】
【請求項１】
実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索する方法であって、
コンピュータ装置の記憶部に、探索用データベースを作る前処理ステップと、
前記コンピュータ装置が前記探索データベースを使用して前記探索を行う探索ステップとを含み、
前記探索用データベースは、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットで隙間無くかつ等間隔でｍ個に区分されたバケット列を有し、
前記各バケットには、先頭バケットから末尾バケットまで順番に割り当てられた固有のバケット番号と、
各バケットの中に含まれる前記実数の個数であるバケットサイズとが記憶されるとともに、
少なくとも前記先頭バケットを除いた各バケットには、前記バケットサイズがゼロでなくかつ当該バケットに最も近いバケットのバケット番号を示すラストフィルドバケットが記憶され、
前記探索ステップは、前記探索点ｑが属するバケットを計算する第１のステップと、
前記計算されたバケットのバケットサイズを参照する第２のステップと、
前記参照されたバケットサイズが０でない場合、当該参照されたバケットから最近傍値を計算する一方、前記参照されたバケットサイズが０の場合、そのバケットのラストフィルドバケットが示すバケットから前記最近傍値を計算する第３のステップとを含むことを特徴とする最近傍値を探索する方法。
【請求項２】
前記最近傍値は、前記探索点を超えない該探索点に最も近い値とし、
前記探索用データベースには、
前記ラストフィルドバケットとして、当該バケットよりも先頭バケット側で当該バケット番号に最も近いバケット番号が記憶されている請求項１記載の最近傍値を探索する方法。
【請求項３】
前記探索用データベースの少なくともバケットサイズが０でないバケットには、そのバケット内の実数のうちの最小値及び最大値がさらに記憶されている請求項２記載の最近傍値を探索する方法。
【請求項４】
前記第２のステップにおいて、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、探索点ｑが最小値よりも小さい場合には、そのバケットのラストフィルドバケットの最大値を最近傍値とする請求項３記載の最近傍値を探索する方法。
【請求項５】
前記第２のステップにおいて、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、前記探索点ｑが最小値以上の場合には、そのバケットに含まれる実数に対してx[ ipoint ] ≦ｑ＜x[ ipoint + 1 ]となるx[ ipoint ] を最近傍値とする請求項３又は４記載の最近傍値を探索する方法。
【請求項６】
複数の多次元の座標値（x,y,z…）が与えられており、探索点ｑ（x1,y1,z1）が与えられたとき、前記座標値を各次元毎の実数群に分け、
各実数群に対して請求項１乃至５のいずれかに記載された探索方法を適用することで前記探索点ｑの各座標に最も近い最近傍値を各次元の実数群の中からそれぞれ探索することを特徴とする最近傍値を探索する方法。
【請求項１】
実数が小さいものから順番に並んでいる実数群（x[1],x[2], x[3] … x[n]）に対して、ある探索対象となる探索点ｑが与えられ、その探索点ｑに最も近い最近傍値を前記実数群の中から探索する方法であって、
コンピュータ装置の記憶部に、探索用データベースを作る前処理ステップと、
前記コンピュータ装置が前記探索データベースを使用して前記探索を行う探索ステップとを含み、
前記探索用データベースは、前記実数群の区間（x[1]〜x[n]）を小領域であるバケットで隙間無くかつ等間隔でｍ個に区分されたバケット列を有し、
前記各バケットには、先頭バケットから末尾バケットまで順番に割り当てられた固有のバケット番号と、
各バケットの中に含まれる前記実数の個数であるバケットサイズとが記憶されるとともに、
少なくとも前記先頭バケットを除いた各バケットには、前記バケットサイズがゼロでなくかつ当該バケットに最も近いバケットのバケット番号を示すラストフィルドバケットが記憶され、
前記探索ステップは、前記探索点ｑが属するバケットを計算する第１のステップと、
前記計算されたバケットのバケットサイズを参照する第２のステップと、
前記参照されたバケットサイズが０でない場合、当該参照されたバケットから最近傍値を計算する一方、前記参照されたバケットサイズが０の場合、そのバケットのラストフィルドバケットが示すバケットから前記最近傍値を計算する第３のステップとを含むことを特徴とする最近傍値を探索する方法。
【請求項２】
前記最近傍値は、前記探索点を超えない該探索点に最も近い値とし、
前記探索用データベースには、
前記ラストフィルドバケットとして、当該バケットよりも先頭バケット側で当該バケット番号に最も近いバケット番号が記憶されている請求項１記載の最近傍値を探索する方法。
【請求項３】
前記探索用データベースの少なくともバケットサイズが０でないバケットには、そのバケット内の実数のうちの最小値及び最大値がさらに記憶されている請求項２記載の最近傍値を探索する方法。
【請求項４】
前記第２のステップにおいて、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、探索点ｑが最小値よりも小さい場合には、そのバケットのラストフィルドバケットの最大値を最近傍値とする請求項３記載の最近傍値を探索する方法。
【請求項５】
前記第２のステップにおいて、参照されたバケットサイズが０でない場合、前記探索点ｑと、そのバケットの最小値とを比較し、前記探索点ｑが最小値以上の場合には、そのバケットに含まれる実数に対してx[ ipoint ] ≦ｑ＜x[ ipoint + 1 ]となるx[ ipoint ] を最近傍値とする請求項３又は４記載の最近傍値を探索する方法。
【請求項６】
複数の多次元の座標値（x,y,z…）が与えられており、探索点ｑ（x1,y1,z1）が与えられたとき、前記座標値を各次元毎の実数群に分け、
各実数群に対して請求項１乃至５のいずれかに記載された探索方法を適用することで前記探索点ｑの各座標に最も近い最近傍値を各次元の実数群の中からそれぞれ探索することを特徴とする最近傍値を探索する方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−１０８１１３（Ｐ２０１１−１０８１１３Ａ）
【公開日】平成２３年６月２日（２０１１．６．２）
【国際特許分類】
【出願番号】特願２００９−２６４２０２（Ｐ２００９−２６４２０２）
【出願日】平成２１年１１月１９日（２００９．１１．１９）
【出願人】（０００１８３２３３）住友ゴム工業株式会社 (3,458)
【Ｆターム（参考）】
【公開日】平成２３年６月２日（２０１１．６．２）
【国際特許分類】
【出願日】平成２１年１１月１９日（２００９．１１．１９）
【出願人】（０００１８３２３３）住友ゴム工業株式会社 (3,458)
【Ｆターム（参考）】
[ Back to top ]