(57)【要約】【課題】浮動小数点演算装置（ＦＰＵ）を備えないハードウェアであっても、全体の処理速度に影響を及ぼすことなく、データ集合に対する範囲検索や近傍検索を行う。【解決手段】この近傍探索装置は、次元数Ｄの平方根の値をあらかじめ格納している記憶手段と、多次元空間における２点Ａ，Ｂ間の距離ｄｏ（Ａ，Ｂ）を下記式及び前記記憶手段に記憶されている次元数Ｄの平方根の値を用いて算出する距離計算手段とを有することを特徴としている。【数５２】2011086124.tif 000054但し、上記式においてＤは多次元空間の次元数、ｄｍは２点Ａ，Ｂ間のマンハッタン距離、ａｉは点Ａの座標ベクトルのｉ番目の成分、ｂｉは点Ａの座標ベクトルのｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数。【選択図】図２
2011086124.tif 000002
【特許請求の範囲】
【請求項１】
次元数Ｄの平方根の値をあらかじめ格納している記憶手段と、
多次元空間における２点Ａ，Ｂ間の距離ｄｏ（Ａ，Ｂ）を下記式及び前記記憶手段に記憶されている次元数Ｄの平方根の値を用いて算出する距離計算手段と
を有することを特徴とする、多次元空間において指定座標について近傍探索を行う近傍探索装置、但し、Ｄは多次元空間の次元数、ｄｍは２点Ａ，Ｂ間のマンハッタン距離、ａｉは点Ａの座標ベクトルのｉ番目の成分、ｂｉは点Ａの座標ベクトルのｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数。
【数４８】
2011086124.tif 000050
【請求項２】
次元数Ｄ及びＤｓの平方根の値をあらかじめ格納している記憶手段と、
多次元空間における２点Ａ，Ｂ間の距離ｄｍｏ（Ａ，Ｂ）を下記式及び前記記憶手段に記憶されている次元数Ｄの平方根の値を用いて算出する距離計算手段と
多次元空間において指定座標について近傍探索を行う近傍探索装置、但し、Ｄは多次元空間の次元数、Ｄｓは制限次元数、ｄｘ１及びｄｘｉは、軸間距離を大きい順に並べたものを(dx1, dx2,…dxD)としたときの１番目の成分及びｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数。
【数４９】
2011086124.tif 000051
【請求項３】
下記式で計算される距離が中心から一定となる図形を包囲図形として使用することを特徴とする多次元インデクスを記憶したインデクス記憶手段と、
指定座標と前記セルとの距離ｄｏ（Ａ，Ｂ）を算出することにより指定座標の近傍探索を実行する探索実行手段と
を有することを特徴とする、多次元空間において指定座標について近傍探索を行う近傍探索装置、但し、Ｄは多次元空間の次元数、ｄｍは２点Ａ，Ｂ間のマンハッタン距離、ａｉは点Ａの座標ベクトルのｉ番目の成分、ｂｉは点Ａの座標ベクトルのｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数。
【数５０】
2011086124.tif 000052
【請求項４】
下記式で計算される距離が中心から一定となる図形を包囲図形として使用することを特徴とする多次元インデクスを記憶したインデクス記憶手段と、
指定座標と前記セルとの距離を算出することにより指定座標の近傍探索を実行する探索実行手段と
を有する近傍探索装置、但し、Ｄは多次元空間の次元数、ｄｍは２点Ａ，Ｂ間のマンハッタン距離、ａｉは点Ａの座標ベクトルのｉ番目の成分、ｂｉは点Ａの座標ベクトルのｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数。
【数５１】
2011086124.tif 000053
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、近傍探索装置に関する。
【背景技術】
【０００２】
マルチメディアデータから抽出した特徴量や成分データ等、特徴量空間上の点として表現されるデータ集合に対して範囲検索や近傍検索を行う際に用いられる技術として、多次元インデクシング技術がある。これは包含関係を持つ図形で特徴量空間を区切ることにより探索を効率化する手法で、包囲図形（セルと呼ぶ）に矩形を採用したR-tree、R*-tree、セルに球形を採用したSS-tree、セルに球形と矩形の論理和を採用したSR-tree等がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】「SR-tree：高次元点データに対する最近接検索のためのインデックス構造の提案」、電子情報通信学会論文誌、D-I、Vol.J80-D-I、No.8、pp.703-717、1997年8月
【発明の概要】
【発明が解決しようとする課題】
【０００４】
これらR-treeの派生となるインデクスを用いた近傍検索は、セルまでの最短距離をヒューリスティックとした深さ優先検索として実装されている。そのため指定座標から実際のデータへの距離計算だけでなく、ヒューリスティックとしてのセル最短距離を計算する必要がある。
【０００５】
ここでいう距離は空間における２点間の最短距離、つまり２点間を直接結んだ線分の長さであり、ユークリッド距離と呼ばれている。一般に、Ｄ次元空間上に２点Ａ、Ｂがあり、各々の座標を
【０００６】
【数１】
2011086124.tif 000003
【０００７】
とするとき、点ＡＢ間のユークリッド距離ｄｕは以下の式で計算される。
【０００８】
【数２】
2011086124.tif 000004
【０００９】
上記式[数２]に含まれる二乗および平方根の計算は、固定小数点としての計算が困難であるため、浮動小数点として計算するのが通例である。しかしこの演算処理はコストが大きく、特に演算を行うハードウェア側が浮動小数点演算装置（ＦＰＵ）を備えない場合には全体の処理速度に影響を及ぼす可能性が高い。
【００１０】
本発明の目的は、浮動小数点演算装置（ＦＰＵ）を備えないハードウェアであっても、全体の処理速度に影響を及ぼすことなく、データ集合に対する範囲検索や近傍検索を行う技術を提供することにある。
【課題を解決するための手段】
【００１１】
上記課題を解決するための手段として、本発明は以下の特徴を有する。
本発明の第１の態様は多次元空間において指定座標について近傍探索を行う近傍探索装置として提案される。この近傍探索装置は、次元数Ｄの平方根の値をあらかじめ格納している記憶手段と、多次元空間における２点Ａ，Ｂ間の距離ｄｏ（Ａ，Ｂ）を下記式及び前記記憶手段に記憶されている次元数Ｄの平方根の値を用いて算出する距離計算手段と
を有することを特徴としている。
【００１２】
【数３】
2011086124.tif 000005
【００１３】
但し、上記式においてＤは多次元空間の次元数、ｄｍは２点Ａ，Ｂ間のマンハッタン距離、ａｉは点Ａの座標ベクトルのｉ番目の成分、ｂｉは点Ａの座標ベクトルのｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数である。
【００１４】
本発明の第２の態様は多次元空間において指定座標について近傍探索を行う近傍探索装置として提案される。この近傍探索装置は、次元数Ｄ及びＤｓの平方根の値をあらかじめ格納している記憶手段と、多次元空間における２点Ａ，Ｂ間の距離ｄｍｏ（Ａ，Ｂ）を下記式及び前記記憶手段に記憶されている次元数Ｄの平方根の値を用いて算出する距離計算手段とを有することを特徴としている。
【００１５】
【数４】
2011086124.tif 000006
【００１６】
但し、上記式において、Ｄは多次元空間の次元数、Ｄｓは制限次元数、ｄｘ１及びｄｘｉは、軸間距離を大きい順に並べたものを(dx1, dx2,…dxD)としたときの１番目の成分及びｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数である。
【００１７】
本発明の第３の態様は多次元空間において指定座標について近傍探索を行う近傍探索装置として提案される。この近傍探索装置は、包囲図形として中心から下記式で計算される距離が一定となる図形を使用することを特徴とする多次元インデクスを記憶したインデクス記憶手段と指定座標と前記セルとの距離ｄｏ（Ａ，Ｂ）を算出することにより指定座標の近傍探索を実行する探索実行手段とを有することを特徴としている。
【００１８】
【数５】
2011086124.tif 000007
【００１９】
但し、上記式において、Ｄは多次元空間の次元数、ｄｍは２点Ａ，Ｂ間のマンハッタン距離、ａｉは点Ａの座標ベクトルのｉ番目の成分、ｂｉは点Ａの座標ベクトルのｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数である。
【００２０】
本発明の第４の態様は、多次元空間において指定座標について近傍探索を行う近傍探索装置として提案される。この近傍探索装置は、下記式で計算される距離が中心から一定となる図形を包囲図形として使用することを特徴とする多次元インデクスを記憶したインデクス記憶手段と、指定座標と前記セルとの距離を算出することにより指定座標の近傍探索を実行する探索実行手段とを有することを特徴としている。
【００２１】
【数６】
2011086124.tif 000008
【００２２】
但し、上記式において、Ｄは多次元空間の次元数、ｄｍは２点Ａ，Ｂ間のマンハッタン距離、ａｉは点Ａの座標ベクトルのｉ番目の成分、ｂｉは点Ａの座標ベクトルのｉ番目の成分、ｉ及びＤは１≦ｉ≦Ｄを満たす整数である。
【発明の効果】
【００２３】
本発明によれば、浮動小数点演算装置（FPU）を備えないハードウェアであっても、全体の処理速度に影響を及ぼすことなく、データ集合に対する範囲検索や近傍検索を行うことを可能とする。
【発明を実施するための最良の形態】
【００２４】
以下、図面を参照しながら本発明の実施の形態を説明する。
[１．オクタゴン距離の説明]  
本発明にかかる多次元インデクシング技術は、セルまでの最短距離を計算する場合において、従来のユークリッド距離の代わりに、これを近似する「オクタゴン距離」を用いる。この「オクタゴン距離」は軸方向距離とマンハッタン距離から計算される。ここで、「軸方向距離」とは、特定軸にのみ着目した場合の座標差分である。「マンハッタン距離」は軸方向にのみ移動できるという制約下での最短距離であり、定義された全次元の軸方向距離の総和となる。
【００２５】
Ｄ次元空間上に点Ａ、点Ｂがあり、各々の座標を
【００２６】
【数７】
2011086124.tif 000009
【００２７】
とするとき、点Ａ、Ｂ間のｉ軸についての軸方向距離（ｉ軸方向距離、ただし、１≦ｉ≦Ｄ）は
【００２８】
【数８】
2011086124.tif 000010
【００２９】
となる。
【００３０】
また点Ａ、Ｂ間のマンハッタン距離ｄｍは以下の式で計算される。
【００３１】
【数９】
2011086124.tif 000011
【００３２】
指定座標からのユークリッド距離・マンハッタン距離・軸方向距離・オクタゴン距離を一定とする図形を２次元空間上に取り、これら距離の関係を図１に示す。なお、指定座標は点Ｃである。
【００３３】
図１において、図形１０１は、点Ｃからの軸方向の距離が一定（Ｒ）となる点の集合からなる正方形である。この図形１０１は、１軸と平行となる直線と、もう一方の軸と垂直な直線とからなり、中心を点Ｃにおき、一辺の長さを２Ｒとする正方形となる。
【００３４】
もう一つの図形１０２は点Ｃからのマンハッタン距離が一定の値（√２×Ｒ）となる点の集合である。この図形１０２は、全ての軸と４５度の角度を成す直線（対角線）からなり、先に述べた図形１０１と合同かつ同一の中心（この例では点Ｃ）を持つ正方形となる。
【００３５】
図形１０３は点Ｃからのユークリッド距離が一定（Ｒ）となる点の集合であり、図形１０１および図形１０２と同一の中心（この例では点Ｃ）を持つ半径Ｒの円となる。よって円１０３は図形１０１と図形１０２の内接円になる。
【００３６】
このとき、図形１０１と図形１０２の論理積は図形１０４となり、図形１０４は図１中斜線ハッチングで塗りつぶされた部分で示す正八角形である。この正八角形１０４の内接円半径Ｒをオクタゴン距離とする。すなわち本発明で用いるオクタゴン距離は「マンハッタン距離÷（√２）」と「軸方向距離の最大値」のどちらか大きい側の値である。２次元空間上における点Ａ，点Ｂ間のオクタゴン距離ｄｏ（Ａ，Ｂ）は以下の式で計算できる。
【００３７】
【数１０】
2011086124.tif 000012
【００３８】
これをＤ次元空間に拡張する。Ｄ次元空間上でマンハッタン距離を同一とする点集合の超立体にユークリッド距離を同一とする点集合の超球体が内接するとき、その接点は空間の全軸からの角度を４５度とする対角線上に存在するため、原点から見た接点の座標すなわち軸方向距離は全ての軸において等しい値となる。このときのユークリッド距離ｄｕをＲ、軸方向距離をｘとすると、
【００３９】
【数１１】
2011086124.tif 000013
【００４０】
となり、これと同一の条件で測定したときのマンハッタン距離ｄｍは
【００４１】
【数１２】
2011086124.tif 000014
【００４２】
となる。よってＤ次元空間でマンハッタン距離一定の超立体がユークリッド距離一定の超球を内接球として持つとき、そのマンハッタン距離はユークリッド距離または軸方向距離の√Ｄ倍となる。よってＤ次元空間における点(Ａ,Ｂ)間のオクタゴン距離ｄｏ（Ａ，Ｂ）は以下の式で計算できる。
【００４３】
【数１３】
2011086124.tif 000015
【００４４】
上記計算式の実行について、√Ｄの演算は、次元数Ｄに応じた平方根の値をテーブルなどの形式で予め準備し、メモリなどの記憶装置、記憶媒体などに記憶させておけばよい。後述するの近傍探索装置２０では、平方根値記憶部２８がこれに相当する。その結果、上記計算式によるオクタゴン距離の算出処理において、二乗および平方根の算出処理を含まない処理とすることができ、その結果固定小数点としての演算が容易となり、FPUを持たない装置(たとえば、組込み機器）でも処理速度の低下を招くことなくデータ集合に対する範囲検索や近傍検索を行うことができる。
【００４５】
また、図１の図形１０５である正八角形は、図形１０４に示す円と同様に中心座標と半径を指定するだけで一意に領域を定めることが出来る。そのためセルの形状として正八角形は円を代替することが可能であり、本発明かかる多次元インデクシング技術は、距離計算方法以外のアルゴリズムをSS-treeのものを利用することが出来る。よって、本発明にかかる多次元インデクシング技術は、距離計算においてはR-treeの派生系を、インデックス形状の変更という点においてはSS-treeの派生形式あるいは改善策と併用することが可能である。この中にはSR-treeや特開2003-85205号公開公報に開示された楕円型インデックス方式も含まれる。
【００４６】
[２．近傍探索装置の構成例]  
つぎに、上記オクタゴン距離を用いた探索処理を実行する装置、及びその探索処理に必要なインデクスの生成、管理を行う装置である近傍探索装置について説明する。
【００４７】
この近傍探索装置は、情報処理装置によって実現される装置であって、たとえばいわゆる組み込み機器（ハードディスクレコーダ、携帯電話機など）、コンピュータ、ワークステーションなどである。この情報処理装置は、演算処理装置（ＣＰＵ）、主メモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、入出力装置（Ｉ／Ｏ）、及び必要な場合にはハードディスク装置等の外部記憶装置を具備している装置である。
【００４８】
図２は、近傍探索装置の構成例を示した機能ブロック図である。近傍探索装置２０は、データ記憶部２１と、データ記憶部２１に接続された探索実行部２２及びインデクス管理部２７と、探索実行部２２及びインデクス管理部２７に接続された入力部２３及び出力部２４と、探索実行部２２に接続された平方根値記憶部２８とを有している。本発明のインデクス記憶手段に相当するデータ記憶部２１は、特徴量や成分データ等、特徴量空間上の点として表現される実データの集合であるデータ２５と、前記特徴量空間を区切るための包囲図形（セル）を有するインデクス２６とを記憶している。
【００４９】
本発明の距離計算手段及び探索実行手段に相当する探索実行部２２は、後述する探索処理を行い、インデクス２６を参照しながら指定されたデータに近似するデータをデータ２５から探索して抽出する機能を有する。
【００５０】
インデクス管理部２７は、インデクス２６の生成、インデクス２６に含まれるセルの拡張（調整）、セルの分割などを行う。
入力部２３はユーザからの指令や新たなデータの数値などを入力する機能を有し、例えばキーボード、ポインティングデバイス、記憶媒体読み取り装置などである。
出力部２４は、探索処理の結果をユーザに示し、あるいは探索処理のための必要情報の入力、実データの入力、インデクス２６の内容の表示などを行うユーザインターフェイス（ＵＩ）を提示する機能を有し、例えば液晶表示装置、プリンタなどである。
本発明の記憶手段に相当する平方根値記憶部２８は、√Ｄ（Ｄは次元数、又は制限次元数）の値を格納して探索実行部２２へ必要に応じて√Ｄの値を渡す機能を有する。
【００５１】
[３．探索処理]  
[３．１．一般的な探索処理]  
本発明にかかる探索処理の説明の前提として、一般的なR-tree系列における実際の探索処理を説明する。  
多次元インデクシング技術の中でもR-tree、SS-tree、SR-treeなどの系列は、従来のB-treeインデクス技術を多次元空間に拡張した技術である。例としてB-treeとR-treeのインデクス構造を図３Ａ及び図３Ｂに挙げ、簡単に説明する。
【００５２】
[３．２．B-treeのインデクス構造]  
図３Ａは、B-treeのインデクスの例を示した図である。B-treeのインデクスは、ノード２０１と、エントリ２０２と、キー２０３とから構成される。探索の際に比較される値（以下、データ２０４という）はキー２０３に格納される。データ２０４はデータベースに収められた実際のデータを示す。
【００５３】
ノード２０１は複数のエントリ２０２から成り、エントリ２０２はキー２０３と子ノードへのポインタのペアで構成される。ノード２０１内のエントリ２０２はキー値の昇順に並び、その最小値が親ノードから自ノードを指すエントリのキーに入る。図２Ａに示した例では、根ノードのエントリのキーに収められた「２０」,「６８」、「１１２」という数値がそれぞれに対応する子ノードの最も左側に存在し、また孫ノードに対しても同様である。探索の際は指定データに最も近いキーを持つエントリ２０２から子ノードを辿っていくことで、データベースに格納されたデータ集合のすべてに対してキー値を検分することなく効率的に探索を進めることが出来る。
【００５４】
[３．３．R-treeのインデクス構造]  
図３Ｂは、R-treeのインデクス構造の例を示した図である。R-treeのインデクスは、ノード２０５、エントリ２０６、及びセル２０７によって構成されている。ノード２０５およびエントリ２０６は、B-treeのものと同様であるが、キー２０３に代えてセル２０７が用いられる。セル２０７は、キー値の代わりに空間上の範囲情報を保持する。B-treeではキー値の最小値を親ノードが保持するという親子関係を持っていたが、R-treeでは親ノードから自ノードを指すセルは自ノードの全セルを包含するという親子関係を持つ。図４は、図３Ｂに示したR-treeにおけるセルの包含関係を示した図である。セルＡはセルＣ,セルＤを包含し、セルＣはセルＥとセルＦを包含し、セルＤはセルＧ,及びセルＨを、をそれぞれ包含している。
【００５５】
[３．４．探索処理の例]  
以下に、上記のR-treeを用いた一般的な近傍探索処理の例について説明する。図５は、R-treeを用いた一般的な近傍探索処理の例を示したフローチャートである。以下、図５を参照しながら近傍探索装置によって実行される近傍探索処理を説明する。
【００５６】
まず、近傍探索装置は、ユーザよりクエリ座標Ｑを受け取り、解候補リストＬを作成した上で、探索対象のノードＮを根ノードに定める（Ｓ３０１）。
次に近傍探索装置は、ノードＮ内の全セル２０７に対して、クエリ座標Ｑからの最短距離を計算し、計算した最短距離が短い順にセル２０７を並べたデータをセルリストデータＣＮとして保存する（Ｓ３０２）。
【００５７】
次に、セルリストデータＣＮのセルの有無を確認する（Ｓ３０３）。このステップＳ３０３の判定においてセルリストデータＣＮにセルが入っている場合（Ｓ３０３，Ｙｅｓ）は，近傍探索装置はセルリストデータＣＮの中を一つ一つ見て、現在見つかっている解候補リストL中の最遠距離と、セルリストデータＣＮ中の各セル２０７の最短距離とを比較する。より具体的には、セルリストデータＣＮから１個セル２０７を取り出してこれをセルＣ０とし、セルＣ０をセルリストデータＣＮから削除する（Ｓ３０４）。次に、近傍探索装置は、クエリ座標ＱからセルＣ０までの最短距離は、解候補リストＬ内の最遠距離より短いか否かを判定する（Ｓ３０５）。解候補リストL中の最遠距離よりセルＣ０までの最短距離が短い場合（Ｓ３０５，Ｙｅｓ）は、解候補リストＬを置き換える近傍データが当該セルに含まれている可能性があるため、そのセルＣ０が指す子ノードを更に調査するように、近傍探索装置はセルＣ０が指す子ノードを新たなノードＮにする（Ｓ３０６）。
【００５８】
次に、近傍探索装置はこの新たなノードＮとなった子ノードが葉ノードであるか否かを判定する（Ｓ３０７）。このＳ３０７の判定においてノードＮが葉ノードであると判定された場合（Ｓ３０７、Ｙｅｓ）、近傍探索装置はクエリ座標Ｑからセル内のデータまでの距離を計算して解候補リストＬを置き換える（Ｓ３０８〜Ｓ３１２）。より具体的にはノードＮ内のデータ集合をＰとし（Ｓ３０８）、データ集合Ｐからデータを一個取り出しＰ０とするとともに、データ集合ＰからデータＰ０を削除し（Ｓ３０９）、さらに解候補リストＬ内の最遠データよりデータＰ０がクエリ座標Ｑに近い場合には、その最遠データを解候補リストＬから削除するとともに、データＰ０を解候補リストＬ内の適切な位置に挿入する（Ｓ３１０）。その後、近傍探索装置はデータ集合Ｐが空集合か否かを判定し（Ｓ３１１）、データ集合Ｐが空集合であると判定した場合（Ｓ３１１、Ｙｅｓ）は、セルリストデータＣＮ中の各セル２０７を近い方に置き換えてクエリ座標Ｑとの距離順に並び変えて格納する（Ｓ３１２）。次に、ノードＮを親ノードに戻すとともに、セルリストデータＣＮを親ノードのセル２０７で構成されるセルリストデータに戻す（Ｓ３１４）。その後前述のステップＳ３０３に戻り、ステップＳ３０３以降の処理を実行していく。一方、ステップＳ３１１の判定においてデータ集合Ｐが空集合でないと判定した場合には、近傍探索装置は前述のステップＳ３０９に戻り、ステップＳ３０９の処理を繰り返す。
【００５９】
また、前述のステップＳ３０３の判定において、セルリストデータＣＮの中にセルが入っていない場合（Ｓ３０３，Ｎｏ）、及び前述のステップＳ３０５の判定において、解候補リストL中の最遠距離より、クエリ座標ＱからセルＣ０までの最短距離が長いと判定した場合（Ｓ３５４、Ｎｏ）、近傍探索装置はノードＮが根ノードであるか否かを判定する（Ｓ３１３）。ノードＮが根ノードであると判定した場合（Ｓ３１３，Ｙｅｓ）、近傍探索装置は探索処理を終了する。一方、ノードＮが根ノードでないと判定した場合（Ｓ３１３，Ｎｏ）、近傍探索装置は前述のステップＳ３１４の処理を実行する。
【００６０】
また、先に述べたステップＳ３０７の判定において、ノードＮが葉ノードでないと判定した場合（Ｓ３０７、Ｎｏ）、近傍探索装置はそのノードを探索対象ノードNとして更にステップＳ３０２に戻り、ステップＳ３０２及びそれ以降の処理を行う。
【００６１】
[４．探索処理中の距離計算]  
上記の近傍検索処理（Ｓ３０１〜Ｓ３１４）の中で距離計算が発生するのはステップＳ３０２とステップＳ３１０である。従来の近傍探索処理では、この距離計算はユークリッド距離の計算であり、浮動小数点演算を多用するため専用の演算装置を備えない組み込み機器では動作速度に致命的な影響を与える。一般的にＦＰＵの有無によって浮動小数点演算の速度には１０〜２５倍程度の差が出ると言われており、例えば通常のＰＣで検索した際に距離計算とそれ以外の処理の比が２０:８０と仮定しても、ＦＰＵの無い機器では２００〜５００:８０となる。よって全体での処理コストも２．８〜５．８倍となる。
【００６２】
よって、この問題を解決するために、本発明ではマンハッタン距離と軸間距離から求められる「オクタゴン距離」を採用する。オクタゴン距離の定義、計算方法などについては前述したとおりである。
【００６３】
[４．１．オクタゴン距離による誤差]  
しかし、上述のオクタゴン距離はいわゆる近似距離であるため、実際の距離（ユークリッド距離）との間にはどこかで差が生じる。図６に、２次元空間におけるユークリッド距離とオクタゴン距離の差について示した。これは図１の第一象限を取り出したものであり、図６の図形４０１〜図形４０４は、図１の図形１０１〜図形１０４の第一象限部分に相当する。
【００６４】
中心Ｃからのユークリッド距離とオクタゴン距離の差が最も大きくなる点は、図６に示す八角形の頂点４０５であり、点Ｃから点４０５までのオクタゴン距離Ｒに対して、同区間のユークリッド距離、つまり線分４０６の実長がどの程度食い違うかを計算することで距離としての違い（近似距離の最大誤差）を評価できる。
【００６５】
図形４０２が基準とするマンハッタン距離は√２Ｒであるため、線長４０７もまた√２Ｒとなる。図形４０８（斜線ハッチングされた三角形）は直角二等辺三角形であるため、線長４０９は（√２―１）Ｒとなる。よってピタゴラスの定理により線分４０６の長さは
【００６６】
【数１４】
2011086124.tif 000016
【００６７】
となり、このことから２次元空間におけるオクタゴン距離の最大誤差ｄｕ／ｄｏはおよそ８％と算出できる。言い換えると、２次元空間でオクタゴン距離を用いた場合は実際の距離より短く見積もられることがあり、その比率は最大で約８％となる。
【００６８】
では次に、この誤差が探索にもたらす影響について述べる。近似距離が実際の距離より長く算出される場合、近似距離を一定とする点の集合は円の内側にある。よって前述の近傍探索処理（図５フローチャート参照）のステップＳ３０５に記した処理の中で、ユークリッド距離で測定すると探索対象となるはずのセルが、近似距離で測定すると対象から外れる可能性がある。
【００６９】
図７に、ユークリッド距離で測定すると探索対象となるはずのセルが、近似距離で測定すると対象から外れる場合の例を示す。図７は、ユークリッド距離で測定すると探索対象となるはずのセルが、近似距離で測定すると対象から外れる可能性がある例を説明する図である。図７の円５０１、円５０２がそれぞれの中心からユークリッド距離Ｒ１、Ｒ２の範囲であり、二つの円は互いに接している。その一方で八角形５０３と八角形５０４はユークリッド距離より長く算出される近似距離をそれぞれＲ１,Ｒ２とする範囲だが、この八角形５０３と八角形５０４は互いに接していない。このように実際のユークリッド距離より長く算出される近似距離を用いた場合は、セルまでの実際の最短距離が条件を満たす場合であっても探索を行わない可能性があるため、近傍解の完全性が保証されない。
【００７０】
また前述の図５に示した近傍探索処理におけるステップＳ３１０に記したベクトルデータとの距離測定に関しても、この処理に近似を導入し、実際の距離より長く算定される場合は、近傍解を取り逃がす可能性を示唆している。例えば対象ベクトルデータが八角形５０３より外側かつ円５０１より内側にある場合は、近似距離測定では近傍解とみなされない。この問題に対処するためには適宜正確なユークリッド距離を測定する必要がある。
【００７１】
今回提案するオクタゴン距離は実際の距離（ユーグリッド距離）より短く算出されるため、近似距離を一定とする点の集合は円の外側にある。よって図５に示した近傍探索処理におけるステップＳ３０５に記した処理の中で、ユークリッド距離で測定すると探索対象とならないはずのセルが、近似距離で測定すると対象に入る可能性がある。
【００７２】
図８に、ユークリッド距離で測定すると探索対象とならないはずのセルが、近似距離で測定すると対象に入る場合の例を示す。図８の円６０１,円６０２は、それぞれの中心からユークリッド距離Ｒ１,Ｒ２の範囲を示し、これら二つの円６０１、６０２は互いに接していない。その一方で八角形６０３と八角形６０４はそれぞれの中心からオクタゴン距離をＲ１，Ｒ２とする範囲であり、二つの八角形は互いに接している。このように実際のユークリッド距離より短く算出される近似距離を用いた場合は、セルまでの実際の最短距離が条件を満たさない場合であっても探索を行う可能性があるため、より多くのセルを探索することになる。つまり検索の絞込み効率を低下させ、探索処理時間を延ばす可能性がある。ただし実際の距離より長く算出される可能性は無いため必要なセル探索をもらす可能性は無く、近傍解の完全性は保証される。
【００７３】
また前述の図５に示した探索処理の例におけるステップ３０９に記したベクトルデータ（実データに相当する点座標）との距離測定に関しても、実際の距離より短く算定される場合は近傍解の候補を実際の解より多く提示する可能性がある。例えば対象ベクトルデータが円６０１より外側かつ正八角形６０３より内側にある場合は、近似距離測定では近傍解とみなされてしまう。この問題に対処するためには、オクタゴン距離による近傍解を解候補として扱い、候補が出た時点で正確なユークリッド距離を測定することが好ましい。
【００７４】
[４．２．３次元以上の多次元空間におけるオクタゴン距離とその誤差]  
２次元空間におけるオクタゴン距離の誤差と影響について見たところで、次に３次元以上のオクタゴン距離とその誤差について説明する。  
３次元空間では、軸方向距離を同一とする点の集合は１軸に平行、他軸に垂直な線分で構成される立方体となる。またマンハッタン距離を同一とする点の集合は、軸方向に頂点を置く正八面体となる。これら立方体又は正八面体の内接球の半径をＲとするとき、軸方向距離はＲ、マンハッタン距離は√３×Ｒとなる。
【００７５】
図９に軸方向距離を同一（Ｒ）とする点の集合である立方体と、半径をＲとする内接球の関係を示す。図９中の立方体７０２が軸方向距離をＲとする点の集合である立体（立方体）、その内接球７０１の半径はＲである。
【００７６】
図１０にマンハッタン距離を同一（√３×Ｒ）とする点の集合である正八面体と、その内接球の関係を示す。正八面体７０４はンハッタン距離を同一（√３×Ｒ）とする点の集合であり、正八面体７０４内の内接球７０３は、半径をＲとする球である。
【００７７】
立方体７０２と正八面体７０４の論理積を取る様子を図１１に示す。図１１中、斜線ハッチングを付した部分が、立方体７０２によって正八面体７０４から削られる領域を示す。図１２は、立方体７０２と正八面体７０４の論理積をとった結果得られる立体を示した図である。図１２中、立体８０６が論理積の結果得られる領域、つまり三次元空間における八角形セルである。立体８０６の表面では立体中心８０７からのオクタゴン距離が一定となる。
【００７８】
このとき、オクタゴン距離の最大誤差は立体８０６の中心点８０７から、立体（八角形セル）８０６の一つの頂点８０８までのユークリッド距離を内接円の半径（Ｒ）で割った値であり、頂点８０８に至る軸方向の距離８０９及び距離８１０から得られる。距離８１０の長さはＲとなり、距離８０９の長さは残る一軸方向の距離が０であるため、マンハッタン距離（軸方向距離の合計）√３×ＲからＲを引いた値になる。よってオクタゴン距離の最大誤差は以下の計算式で求められる。
【００７９】
【数１５】
2011086124.tif 000017
【００８０】
また、４次元以上の空間でオクタゴン距離の誤差を考察するときは、頂点となる条件を数学的に置き換える必要がある。
【００８１】
オクタゴン距離を制約条件として見ると、明らかにマンハッタン距離と軸方向距離に分離できることがわかる。
【００８２】
【数１６】
2011086124.tif 000018
【００８３】
ｄｕ＝Ｒ＝１とした場合、
【００８４】
【数１７】
2011086124.tif 000019
【００８５】
を満たしつつ、できるだけ軸方向距離を少数の軸に偏らせた場合にオクタゴン距離の誤差が最大となる。言い換えると、与えられたマンハッタン距離√Ｄを割り振るとき、可能な限り軸方向距離を１（最大値）とし、余剰分を残った１軸の距離とすればよい。図６の点４０５、図１２の点８０８は共にこの条件を満たす点である。
【００８６】
以上の考察により、Ｄ次元空間におけるオクタゴン距離の最大誤差は床関数（ガウス記号）を用いて以下の式で表現できる。
【００８７】
【数１８】
2011086124.tif 000020
【００８８】
したがって、Ｄ＝４では最大誤差ｄｕ／ｄｏは1.4142、Ｄ＝５では最大誤差ｄｕ／ｄｏは1.4338となり、Ｄの増加に伴って小数部分
【００８９】
【数１９】
2011086124.tif 000021
【００９０】
が相対的に小さくなるため、この値は４乗根
【００９１】
【数２０】
2011086124.tif 000022
【００９２】
に近づく。
【００９３】
[５．修正オクタゴン距離]  
上述の実施の形態では、ユーグリッド距離に代えてオクタゴン距離を用いて近傍探索を行う技術を提案した。本発明者は、上記オクタゴン距離に代わる修正オクタゴン距離をさらに提案する。この修正オクタゴン距離は、上記オクタゴン距離の制限として、次元の一部に対するマンハッタン距離の制限を新たに施した修正八角形（２次元の場合）を用いる。
【００９４】
図１３から図１５に、３次元空間の２次元に対するマンハッタン距離制限を加えた場合の例を示す。図面中の左右方向をｘ軸、上下方向をｙ軸、奥行き方向をｚ軸とすると、図１３は、ｙｚ平面についてのマンハッタン距離制限が加えられた状態を示し、図１４は、ｘｙ平面についてのマンハッタン距離制限が加えられた状態を示し、図１５は、ｘｚ平面についてのマンハッタン距離制限が加えられた状態を示している。図１３から図１５において、軸距離制限に相当する立方体９０１から、２次元のマンハッタン距離制限に相当する第２の立方体９０２ａ、９０２ｂ、９０２ｃによって、斜線ハッチングされた部分９０３が切り取られる。
【００９５】
上記の立方体９０１から切り取られた八角形セル８０６を更に立方体９０２ａ、９０２ｂ、９０２ｃによって切り取った結果得られる三次元の修正八角形セルを図１６に示す
２次元及び３次元マンハッタン距離の切り取りにより、修正八角形セル１０００は斜方立方八面体（ルービックスネーク）に似た形状となる。この修正八角形セルのＺ＝Ｒで示されるｘｙ平面の第一象限を図１７に示す。
【００９６】
この修正オクタゴン距離ｄｍｏを用いた場合の誤差の最大値は以下の通りとなる。
【００９７】
【数２１】
2011086124.tif 000023
【００９８】
すなわち、最大で約１３％の誤差と算出できる。
【００９９】
[Ｄ次元空間における修正八角形セルの定義]   
次に、Ｄ次元空間における修正八角形セルの定義について説明する。Ｄ次元空間における修正八角形セルは、Ｄ次元空間のうちＤｓ次元（以下、このＤｓを「制限次元数」と呼ぶ）に対するマンハッタン距離の制限を加えたものをいう。
【０１００】
Ｄ次元空間における軸間距離の成分を大きい順に並べたものを(dx1, dx2,…dxD)としたとき、修正八角形セルに入る条件は以下の通りである。なお、軸間距離とは特定の軸ないし次元における２点間の距離である。
【０１０１】
【数２２】
2011086124.tif 000024
【０１０２】
これを用いた修正オクタゴン距離ｄｍｏは以下の式により表わされる。
【０１０３】
【数２３】
2011086124.tif 000025
【０１０４】
[５．１．修正オクタゴン距離の誤差]  
[５．１．１．制限次元数Ｄｓ＝２の場合]  
次に、マンハッタン距離の制限を加える制限次元数Ｄｓと、最大誤差の大きさについて検討する。  
【０１０５】
Ｄｓ=２の場合は、ある点座標（dx1, dx2,…dxD）が修正八角形セルに入る条件には
【０１０６】
【数２４】
2011086124.tif 000026
【０１０７】
の制限が加わる。Ｄｓ＝２の際は、このｄｘ１＋ｄｘ２≦√２の制限が加わるため、偏りを最大とするとき、各ベクトル成分は、ｄｘ１＝１、ｄｘ２＝√２−１、ｄｘ３以降はｄｍ≦√Ｄかつｄｘｉ≦√２−１を満たす最大値となる。この各ベクトル成分の大きさの比較を図１８に示す。
【０１０８】
上記ベクトル成分に基づいて、ユーグリット距離ｄｕに対する修正オクタゴン距離ｄｍｏの誤差を数式で表すと、
【０１０９】
【数２５】
2011086124.tif 000027
【０１１０】
となる。
【０１１１】
上記式の次元数Ｄに３，４，５を当てはめて計算するとＤ＝３のときは前述のとおり1.1281となり、Ｄ＝４のときは
【０１１２】
【数２６】
2011086124.tif 000028
【０１１３】
また、Ｄ＝５のときは
【０１１４】
【数２７】
2011086124.tif 000029
【０１１５】
となり、制限次元数Ｄｓ＝２を用いる場合には次元数Ｄ＝３とする場合が最大誤差が最も小さくなる。
【０１１６】
[５．１．２．制限次元数Ｄｓ＝３の場合の検討]  
次に、制限次元数Ｄｓ＝３とする場合の、最大誤差の大きさについて検討する。
【０１１７】
Ｄｓ＝３の際は、ある点座標（dx1,dx2,…dxD）が修正八角形セルに入る条件には、ｄｘ１＋ｄｘ２＋ｄｘ３≦√３の制限が加わる。
【０１１８】
【数２８】
2011086124.tif 000030
【０１１９】
を境に対応が異なるので、それぞれの場合について以下に検討する。
【０１２０】
（１）第１の場合
【０１２１】
【数２９】
2011086124.tif 000031
【０１２２】
となる次元数Ｄのときは、ｄｘ１＝１、かつｄｘ３＝ｄｘ４を最小とするときに偏りが最大となる。このとき
【０１２３】
【数３０】
2011086124.tif 000032
【０１２４】
となる。上記各ベクトル成分の大きさの関係を、図１９（Ａ）に示す。
【０１２５】
ユーグリット距離ｄｕに対する修正オクタゴン距離ｄｍｏの誤差を数式化すると
【０１２６】
【数３１】
2011086124.tif 000033
【０１２７】
となる。
【０１２８】
上記式の次元数Ｄに４を当てはめて計算するとＤ＝４のときは、ｄｕ／ｄｍｏは
【０１２９】
【数３２】
2011086124.tif 000034
【０１３０】
となる。
【０１３１】
（２）第２の場合  
次に、次元数Ｄが下記式を満たす場合について検討する。
【０１３２】
【数３３】
2011086124.tif 000035
【０１３３】
この場合には、点座標（dx1, dx2,…dxD）のベクトル成分は以下のようになる。
【０１３４】
【数３４】
2011086124.tif 000036
【０１３５】
ｄｘ５以降は
【０１３６】
【数３５】
2011086124.tif 000037
【０１３７】
となる。これら成分の大きさの関係を図１９（Ｂ）に示す。
【０１３８】
上記ベクトル成分の大きさに基づいて、ユーグリット距離ｄｕに対する修正オクタゴン距離ｄｍｏの誤差を数式化すると
【０１３９】
【数３６】
2011086124.tif 000038
【０１４０】
となる。
上記式にＤ＝５を代入すると、
【０１４１】
【数３７】
2011086124.tif 000039
【０１４２】
となる。なお、Ｄ＝４のときは1.157となり、前述の第１の場合に次元数Ｄ＝４とした場合の誤差より小さい（＝最大誤差を検出できない）。
【０１４３】
[５．２．Ｄｓで一般化した場合]
次に、ユーグリット距離ｄｕに対する修正オクタゴン距離ｄｍｏの誤差を制限次元数Ｄｓを用いて一般化する。
【０１４４】
【数３８】
2011086124.tif 000040
【０１４５】
を境に対応が異なるので、場合分けをして説明する。
【０１４６】
（１）第１の場合
【０１４７】
【数３９】
2011086124.tif 000041
【０１４８】
を満たす次元数Ｄ、制限次元数Ｄｓのときは、点座標（dx1, dx2,…dxD）のベクトル成分の関係は以下のようになる。
【０１４９】
【数４０】
2011086124.tif 000042
【０１５０】
となり、ｄｘ２はその余りで
【０１５１】
【数４１】
2011086124.tif 000043
【０１５２】
となる。上記ベクトル成分の関係を図２０（Ａ）に示す。
【０１５３】
上記から最大誤差ｄｕ／ｄｍｏを求めると、
【０１５４】
【数４２】
2011086124.tif 000044
【０１５５】
（２）第２の場合
【０１５６】
【数４３】
2011086124.tif 000045
【０１５７】
を満たす次元数Ｄ、制限次元数Ｄｓのときは、
【０１５８】
【数４４】
2011086124.tif 000046
【０１５９】
となり、ｄ（Ｄｓ＋２）以降は、
【０１６０】
【数４５】
2011086124.tif 000047
【０１６１】
の最大値となる。上記ベクトル成分の関係を図２０（Ｂ）に示す。  
ここで、
【０１６２】
【数４６】
2011086124.tif 000048
【０１６３】
ただし、
【０１６４】
【数４７】
2011086124.tif 000049
【０１６５】
を下回ることはない。上記条件３におけるベクトル成分の大きさの関係を図２１に示す。
最終的な誤差は、上記条件１または条件２と条件３のうち、大きい方となる。
【０１６６】
次元数Ｄと、制限次元数Ｄｓを代えて上記最大誤差を求める式を用いて修正オクタゴン距離を用いた場合の誤差を算出して、比較した結果を図２２に示す。この比較により、誤差最小とする制限次元数Ｄｓは、次元数の平方根＋１程度となることがわかった。そのため、基本的に条件１が適用されることは無い。
【０１６７】
制限次元数Ｄｓの選定基準についてはこの特許の範囲外とするが、軸間距離の各軸における並べ替え処理を考えるとＤｓとして２や３などの低い値が考えられる。また、割り算処理の軽減を考えると平方根が整数あるいは２の乗数となるＤｓが考えられる。前者の場合は４，９，１６，２５、３６などがあり、後者の場合は４，１６，６４，２５６などが挙げられる。
【０１６８】
[６．本発明の利点]  
オクタゴン距離は軸間距離、すなわち各軸の座標差分とマンハッタン距離から計算されるため複雑な浮動小数点演算が無く、ＦＰＵを持たない組込み機器でも処理速度の低下を招かない。
【０１６９】
また、指定座標からのユークリッド距離が一定となる点の集合が 指定座標を中心とした円ないし球となるのと同様、指定座標からのオクタゴン距離が一定となる点の集合は 指定座標を中心とする八角形となる。この八角形は中心座標と直径の指定のみで領域を定めることが出来るため、セルの形状として円を代替することが可能である。よって、本発明にかかる多次元インデクシング技術は、距離計算においてはR-treeの派生系を、インデックス形状の変更という点においてはSS-treeの派生形式あるいは改善策と併用することが可能である。この中にはSR-treeや特開2003-85205号公開公報に開示された楕円型インデックス方式も含まれる。
【図面の簡単な説明】
【０１７０】
【図１】指定座標からのユークリッド距離・マンハッタン距離・軸方向距離・オクタゴン距離の関係を示す図
【図２】近傍探索装置の構成例を示した機能ブロック図
【図３Ａ】B-treeのインデクス構造の例を示す図
【図３Ｂ】R-treeのインデクス構造の例を示した
【図４】図３Ｂに示したR-treeにおけるセルの包含関係を示した図
【図５】R-treeを用いた一般的な近傍探索処理の例を示したフローチャート
【図６】２次元空間におけるユークリッド距離とオクタゴン距離の差について示した
【図７】ユークリッド距離で測定すると探索対象となるはずのセルが、近似距離で測定すると対象から外れる可能性がある例を説明する図
【図８】ユークリッド距離で測定すると探索対象とならないはずのセルが、近似距離で測定すると対象に入る場合の例を示す図
【図９】軸方向距離を同一（Ｒ）とする点の集合である立方体と、半径をＲとする内接球の関係を示す図
【図１０】マンハッタン距離を同一（√３×Ｒ）とする点の集合である正八面体と、その内接球の関係を示す図
【図１１】立方体７０２と正八面体７０４の論理積を取る様子を示す図
【図１２】立方体７０２と正八面体７０４の論理積をとった結果得られる立体を示した図
【図１３】３次元空間の２次元に対するマンハッタン距離制限を加えた場合の例を示す図
【図１４】３次元空間の２次元に対するマンハッタン距離制限を加えた場合の例を示す図
【図１５】３次元空間の２次元に対するマンハッタン距離制限を加えた場合の例を示す図
【図１６】三次元の修正八角形セルを示す図
【図１７】この修正八角形セルのＺ＝Ｒで示されるｘｙ平面の第一象限を示す図
【図１８】Ｄｓ＝２の場合の各ベクトル成分の大きさの比較を示した図
【図１９】（Ａ）は制限次元数Ｄｓ＝３かつ第１の場合の各ベクトル成分の大きさの比較を示した図、（Ｂ）は制限次元数Ｄｓ＝３かつ第２の場合の各ベクトル成分の大きさの比較を示した図
【図２０】（Ａ）は次元数Ｄ、制限次元数Ｄｓかつ第１の場合の各ベクトル成分の大きさの比較を示した図、（Ｂ）はかつ次元数Ｄ、制限次元数Ｄｓかつ第２の場合の各ベクトル成分の大きさの比較を示した図
【図２１】条件３の場合のベクトル成分大きさの関係を示す図
【図２２】次元数Ｄと、制限次元数Ｄｓごとの修正オクタゴン距離を用いた場合の誤差を比較した図
【符号の説明】
【０１７１】
２０…近傍探索装置；  ２１…データ記憶部；  ２２…探索実行部；  ２３…入力部；  ２４…出力部；  ２５…データ；  ２６…インデクス；  ２７…インデクス管理部；  ２８…平方根値記憶部
【図１】
2011086124.tif 000055
【図２】
2011086124.tif 000056
【図３Ａ】
2011086124.tif 000057
【図３Ｂ】
2011086124.tif 000058
【図４】
2011086124.tif 000059
【図５】
2011086124.tif 000060
【図６】
2011086124.tif 000061
【図７】
2011086124.tif 000062
【図８】
2011086124.tif 000063
【図９】
2011086124.tif 000064
【図１０】
2011086124.tif 000065
【図１１】
2011086124.tif 000066
【図１２】
2011086124.tif 000067
【図１３】
2011086124.tif 000068
【図１４】
2011086124.tif 000069
【図１５】
2011086124.tif 000070
【図１６】
2011086124.tif 000071
【図１７】
2011086124.tif 000072
【図１８】
2011086124.tif 000073
【図１９】
2011086124.tif 000074
【図２０】
2011086124.tif 000075
【図２１】
2011086124.tif 000076
【図２２】
2011086124.tif 000077