(57)【要約】【課題】多次元空間データのインデックスの矩形と球の中心を一致させたデータ構造を適用し、検索精度を維持しつつ省メモリを実現する。【解決手段】多次元空間におけるベクトルデータ集合のインデックス情報を多次元空間木構造として格納するために、多次元空間を矩形と球の論理積の領域に分割し、その領域情報を木構造のノードに格納する多次元インデックスのセル生成方法において、矩形の頂点であって、最遠関係にある頂点同士を両端とする対角線の中点を矩形の中心に決定するステップと、球の中心を前記矩形の中心と同一の点に決定するステップと、前記球の半径を前記球の子ノードが表す領域を完全に包含する最小の長さに決定するステップと、前記矩形の大きさを矩形の中心から各軸と平行な辺までの最短距離とするステップとを有するセル生成方法。【選択図】図７
2011081554.tif 000002
【特許請求の範囲】
【請求項１】
多次元空間におけるベクトルデータ集合のインデックス情報を多次元空間木構造として格納するために、多次元空間を矩形と球の論理積の領域に分割し、その領域情報を木構造のノードに格納する多次元インデックスのセル生成方法において、
矩形の頂点であって、最遠関係にある頂点同士を両端とする対角線の中点を矩形の中心に決定するステップと、
球の中心を前記矩形の中心と同一の点に決定するステップと、
前記球の半径を前記球の子ノードが表す領域を完全に包含する最小の長さに決定するステップと、
前記矩形の大きさを矩形の中心から各軸と平行な辺までの最短距離とするステップと
を有する多次元インデックスのセル生成方法。
【請求項２】
多次元インデックスのデータ構造において、葉ノードの外に位置する点を新たにインデックスに格納するために、その点からみて最近傍の葉ノードが持つ矩形および球の領域を拡張するインデックスのセル拡張方法において、
前記葉ノードの矩形の中心および長さをその点を包含するように変更するステップと、
前記葉ノードの球の中心を前記矩形の新たな中心とし、前記球の半径をその点を包含するように変更するステップと、
前記葉ノードが親ノードの領域外に出た場合は、この親ノードも葉ノードを完全に包含するように領域を変更し、包含関係を根ノードまで保つように変更するステップと
を有することを特徴とする多次元インデックスのセル拡張方法。
【請求項３】
多次元空間におけるベクトルデータ集合のインデックス情報を多次元空間木構造として格納するために、多次元空間をセルである矩形と球の論理積の領域に分割し、その領域情報を木構造のノードに格納する多次元インデックスのセルのデータ構造であって、
矩形及び球の共通の中心座標と、
前記矩形の中心から各軸と平行な辺までの最短距離と、
球の半径
のみからなる多次元インデックスのセルのデータ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多次元インデックスのセル生成方法、セル拡張方法、並びにセルのデータ構造に関する。
【背景技術】
【０００２】
マルチメディアデータから抽出した特徴量や成分データ等、特徴量空間上の点として表現されるデータ集合に対して範囲検索や近傍検索を行う際に用いられる技術として、空間インデクシング技術がある。この中でも空間を図形で階層的に分割し、木構造の形でインデックスに登録することで探索を効率化する手法が代表的である。木構造の種類には、セルと呼ばれる包囲図形に矩形を採用したR-tree、球を採用したSS-tree、球と矩形の論理積を採用したSR-tree などがある（例えば、非特許文献１）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】「SR-tree：高次元点データに対する最近接検索のためのインデックス構造の提案」、電子情報通信学会論文誌、D-I、Vol.J80-D-I、No.8、pp.703-717、1997年8月
【発明の概要】
【発明が解決しようとする課題】
【０００４】
包囲図形としての矩形の長所は、各次元で点集合の包囲する長さを調節できるため、球に比べて体積が小さいことである。そのため他の矩形との重複が起こりにくく、検索の二度手間を減らすことが出来る。
一方、包囲図形としての球は中心からの距離が一定であるため、高次元データであっても領域内の最大距離が一定値に抑えられるという利点がある。矩形の場合、例えばD次元空間における超立方体の対角線は辺長の√Ｄ倍となり、高次元になれば頂点付近の点が探索領域に入る可能性が高くなるので検索効率が低下するが、球形セルではこの現象をある程度回避できる。
SR-treeは矩形と球の双方の長所を併せ持つが、球と矩形の情報を別々に持つ分、セル1個あたりの情報量が多くなるため、インデックスサイズが大きいという問題点がある。そのためSR-treeで高次元点データを扱う場合、セルが表す領域の体積が大きくなり、1ノードあたりの枝の数が少なくなるため、木の高さが高くなったり、検索時に読み込むノード数が増加することが考えられる。
【０００５】
すなわち、従来の球と矩形の情報を別々に持つSR-treeでは、球か矩形を単独で持つtreeに比べて検索が高速ではあるが、セル1個あたりの情報量が多くなるため、インデックスサイズが大きいという問題点があった。
【０００６】
本発明の目的は、多次元空間データのインデックスを生成するときに、矩形と球の中心を一致させたデータ構造を適用することで、検索精度を維持しつつ省メモリを実現する技術を提供することにある。
【課題を解決するための手段】
【０００７】
上記課題を解決するための手段として、本発明は以下の特徴を有する。
本発明の第１の態様は、多次元空間におけるベクトルデータ集合のインデックス情報を多次元空間木構造として格納するために、多次元空間を矩形と球の論理積の領域に分割し、その領域情報を木構造のノードに格納する多次元インデックスのセル生成方法として提案される。
【０００８】
このセル生成方法は、矩形の頂点であって、最遠関係にある頂点同士を両端とする対角線の中点を矩形の中心に決定するステップと、球の中心を前記矩形の中心と同一の点に決定するステップと、前記球の半径を前記球の子ノードが表す領域を完全に包含する最小の長さに決定するステップと、前記矩形の大きさを矩形の中心から各軸と平行な辺までの最短距離とするステップとを有することを特徴としている。
本発明の第２の態様は、多次元インデックスのデータ構造において、葉ノードの外に位置する所定の点を新たにインデックスに格納するために、その点からみて最近傍の葉ノードが持つ矩形および球の領域を拡張するインデックスのセル拡張方法として提案される。
このセル拡張方法は、前記葉ノードの矩形の中心および長さをその点を包含するように変更するステップと、前記葉ノードの球の中心を前記矩形の新たな中心とし、前記球の半径をその点を包含するように変更するステップと、前記葉ノードが親ノードの領域外に出た場合は、この親ノードも葉ノードを完全に包含するように領域を変更し、包含関係を根ノードまで保つように変更するステップとを有することを特徴としている。
本発明の第３の態様は、多次元空間におけるベクトルデータ集合のインデックス情報を多次元空間木構造として格納するために、多次元空間をセルである矩形と球の論理積の領域に分割し、その領域情報を木構造のノードに格納する多次元インデックスのセルのデータ構造であって、矩形及び球の共通の中心座標と、前記矩形の中心から各軸と平行な辺までの最短距離と、球の半径のみからなることを特徴としている。
【発明の効果】
【０００９】
本発明によれば、多次元空間データのインデックスを生成するときに、矩形と球の中心を一致させたデータ構造を適用することで、検索精度を維持しつつ省メモリを実現することが可能となる。
【発明を実施するための最良の形態】
【００１０】
［１．従来の探索処理について］
本発明の説明の前提として、一般的なR-tree系列における実際の探索処理を説明する。
多次元インデクシング技術の中でもR-tree、SS-tree、SR-treeなどの系列は、従来のB-treeインデックス技術を多次元空間に拡張した技術である。例としてB-treeとR-treeのインデックス構造を図１に挙げ、簡単に説明する。
【００１１】
[１．１．B-tree]
図１は、B-treeのインデックスの例を示した図である。B-treeのインデックスは、ノード１０１と、エントリ１０２と、キー１０３とから構成される。探索の際に比較される値（以下、データ１０４という）はキー１０３に格納される。データ１０４はデータベースに収められた実際のデータを示す。
【００１２】
ノード１０１は複数のエントリ１０２から成り、エントリ１０２はキー１０３と子ノードへのポインタのペアで構成される。ノード１０１内のエントリ１０２はキー値の昇順（図１中では図面に向かって左から右）に並び、その最小値が親ノードから自ノードを指すエントリのキーに入る。図１に示した例では、根ノードのエントリのキーに収められた「２０」,「６８」、「１１２」という数値がそれぞれに対応する子ノードの最も左側に存在し、また孫ノードに対しても同様である。探索の際は指定データに最も近いキーを持つエントリ２０２から子ノードを辿っていくことで、データベースに格納されたデータ集合のすべてに対してキー値を検分することなく効率的に探索を進めることが出来る。
【００１３】
図２は、R-treeのインデックスの例を示した図である。R-treeのインデックスは、ノード１０５、エントリ１０６、及びセル１０７によって構成されている。ノード１０５およびエントリ１０６は、B-treeのものと同様であるが、キー１０３に代えてセル１０７が用いられる。セル１０７は、キー値の代わりに空間上の範囲情報（セル又は包囲図形）を保持する。B-treeではキー値の最小値を親ノードが保持するという親子関係を持っていたが、R-treeでは親ノードから自ノードを指すセルは自ノードの全セルを包含するという親子関係を持つ。図３は、図２に示したR-treeの包含関係を示した図である。セルＡはセルＣ,セルＤを包含し、セルＣはセルＥとセルＦを包含し、セルＤはセルＧ,及びセルＨを、それぞれ包含している。
【００１４】
R-treeは、空間情報を矩形で保持し、SS-treeは球で保持する。SR-treeは矩形と球の両方を保持することでこれらの長所を取り込んでいる。矩形は最小点と最大点の1対の組により一意に表される。最小点とは矩形の頂点の中で最小値をとる点であり、最大点はその逆に最大値を持つ点をさす。球の中心はその内部の点集合の平均位置（重心）に基づいて決定され、球の半径はセル内の球全てを包含するように決定される。したがって、従来のSR-treeでは、セル1個あたりのデータは次のように表される。
【００１５】
セルのデータ＝（Rm、RM、C、r）
但し、Rm：矩形の最小点の座標、RM：矩形の最大点の座標、C：球の中心の座標、r：球の半径である。
【００１６】
[２．近傍探索装置の構成例]
つぎに、上記距離を用いた探索処理を実行する装置、及びその探索処理に必要なインデックスの生成、管理を行う装置である近傍探索装置について説明する。
【００１７】
この近傍探索装置は、情報処理装置によって実現される装置であって、たとえばいわゆる組み込み機器（ハードディスクレコーダ、携帯電話機など）、コンピュータ、ワークステーションなどである。この情報処理装置は、演算処理装置（ＣＰＵ）、主メモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、入出力装置（Ｉ／Ｏ）、及び必要な場合にはハードディスク装置等の外部記憶装置を具備している装置である。
【００１８】
図４は、近傍探索装置の構成例を示した機能ブロック図である。近傍探索装置２０は、データ記憶部２１と、データ記憶部２１に接続された探索実行部２２及びインデックス管理部２７と、探索実行部２２及びインデックス管理部２７に接続された入力部２３及び出力部２４と、探索実行部２２に接続された平方根値記憶部２８とを有している。本発明のインデックス記憶手段に相当するデータ記憶部２１は、特徴量や成分データ等、特徴量空間上の点として表現される実データの集合であるデータ２５と、前記特徴量空間を区切るための包囲図形（セル）を有するインデックス２６とを記憶している。
【００１９】
探索実行部２２は、後述する探索処理を行い、インデックス２６を参照しながら指定されたデータに近似するデータをデータ２５から探索して抽出する機能を有する。
インデックス管理部２７は、インデックス２６の生成、インデックス２６に含まれるセルの拡張（調整）、セルの分割などを行う。
入力部２３はユーザからの指令や新たなデータの数値などを入力する機能を有し、例えばキーボード、ポインティングデバイス、記憶媒体読み取り装置などである。
出力部２４は、探索処理の結果をユーザに示し、あるいは探索処理のための必要情報の入力、実データの入力、インデックス２６の内容の表示などを行うユーザインターフェイス（ＵＩ）を提示する機能を有し、例えば液晶表示装置、プリンタなどである。
【００２０】
［２．従来の一般的な多次元インデックスに対する探索処理］
次に、従来の一般的な多次元インデックスに対する探索処理について説明する。図５は、多次元インデックスを用いた一般的な近傍探索処理の例を示したフローチャートである。以下、図５を参照しながら近傍探索装置によって実行される近傍探索処理を説明する。
【００２１】
まず、近傍探索装置２０は、ユーザよりクエリ座標Ｑを受け取り、解候補リストＬを作成した上で、探索対象のノードＮを根ノードに定める（Ｓ１０１）。
次に近傍探索装置２０は、ノードＮ内の全セル１０７に対して、クエリ座標Ｑからの最短距離を計算し、計算した最短距離が短い順にセル１０７を並べたデータをセルリストデータＣＮとして保存する（Ｓ１０２）。
【００２２】
次に、セルリストデータＣＮのセルの有無を確認する（Ｓ１０３）。このステップＳ１０３の判定においてセルリストデータＣＮにセルが入っている場合（Ｓ１０３，Ｙｅｓ）は，近傍探索装置２０はセルリストデータＣＮの中を一つ一つ見て、現在見つかっている解候補リストL中の最遠距離と、セルリストデータＣＮ中の各セル１０７の最短距離とを比較する。より具体的には、セルリストデータＣＮから１個セル１０７を取り出してこれをセルＣ０とし、セルＣ０をセルリストデータＣＮから削除する（Ｓ１０４）。次に、近傍探索装置は、クエリ座標ＱからセルＣ０までの最短距離は、解候補リストＬ内の最遠距離より短いか否かを判定する（Ｓ１０５）。解候補リストL中の最遠距離よりセルＣ０までの最短距離が短い場合（Ｓ１０５，Ｙｅｓ）は、解候補リストＬを置き換える近傍データが当該セルに含まれている可能性があるため、そのセルＣ０が指す子ノードを更に調査するように、近傍探索装置はセルＣ０が指す子ノードを新たなノードＮにする（Ｓ１０６）。
【００２３】
次に、近傍探索装置はこの新たなノードＮとなった子ノードが葉ノードであるか否かを判定する（Ｓ１０７）。このステップＳ１０７の判定においてノードＮが葉ノードであると判定された場合（Ｓ１０７、Ｙｅｓ）、近傍探索装置はクエリ座標Ｑからセル内のデータまでの距離を計算して解候補リストＬを置き換える（Ｓ１０８〜Ｓ１１２）。より具体的にはノードＮ内のデータ集合をＰとし（Ｓ１０８）、データ集合Ｐからデータを一個取り出しＰ０とするとともに、データ集合ＰからデータＰ０を削除し（Ｓ１０９）、さらに解候補リストＬ内の最遠データよりデータＰ０がクエリ座標Ｑに近い場合には、その最遠データを解候補リストＬから削除するとともに、データＰ０を解候補リストＬ内の適切な位置に挿入する（Ｓ１１０）。その後、近傍探索装置はデータ集合Ｐが空集合か否かを判定し（Ｓ１１１）、データ集合Ｐが空集合であると判定した場合（Ｓ１１１、Ｙｅｓ）は、セルリストデータＣＮ中の各セル１０７を近い方に置き換えてクエリ座標Ｑとの距離順に並び変えて格納する（Ｓ１１２）。次に、ノードＮを親ノードに戻すとともに、セルリストデータＣＮを親ノードのセル１０７で構成されるセルリストデータに戻す（Ｓ１１４）。その後前述のステップＳ１０３に戻り、ステップＳ１０３以降の処理を実行していく。一方、ステップＳ１１１の判定においてデータ集合Ｐが空集合でないと判定した場合には、近傍探索装置は前述のステップＳ１０９に戻り、ステップＳ１０９からの処理を繰り返す。
【００２４】
また、前述のステップＳ１０３の判定において、セルリストデータＣＮの中にセルが入っていない場合（Ｓ１０３，Ｎｏ）、及び、前述のステップＳ１０５の判定において、解候補リストL中の最遠距離より、クエリ座標ＱからセルＣ０までの最短距離が長いと判定した場合（Ｓ１０５、Ｎｏ）、近傍探索装置はノードＮが根ノードであるか否かを判定する（Ｓ１１３）。ノードＮが根ノードであると判定した場合（Ｓ１１３，Ｙｅｓ）、近傍探索装置は探索処理を終了する。一方、ノードＮが根ノードでないと判定した場合（Ｓ１１３，Ｎｏ）、近傍探索装置は前述のステップＳ１１４の処理を実行する。
【００２５】
また、先に述べたステップＳ１０７の判定において、ノードＮが葉ノードでないと判定した場合（Ｓ１０７、Ｎｏ）、近傍探索装置はそのノードを探索対象ノードＮとして更にステップＳ１０２に戻り、ステップＳ１０２及びそれ以降の処理を行う。
【００２６】
［３．従来の一般的な多次元インデックスに対する登録（挿入）処理］
次に従来の一般的な多次元インデックスに新たなデータを登録（挿入）する登録処理について述べる。図６は、従来の一般的な多次元インデックスに新たなデータを登録（挿入）する登録処理の一般的な例を示したフローチャートである。
【００２７】
まず、近傍探索装置は、多次元インデックスに対する探索手順と同様に、挿入するデータ（挿入データと呼ぶこととする）に最も距離が近い葉ノードを検索する（Ｓ２０１）。次に近傍探索装置は、先のステップＳ２０１で見つかった葉ノード（挿入対象ノードと呼ぶ）のエントリに挿入データを追加する（Ｓ２０２）。
【００２８】
通常１個のノードに格納されるエントリ数には最大値と最小値があらかじめ設定されており、ステップＳ２０２で挿入データを挿入対象ノードのエントリに追加した後、近傍探索装置は挿入対象ノードのエントリ数が最大値を超えているか否かを判定する（Ｓ２０３）。超えている場合（Ｓ２０３、Ｙｅｓ）は、近傍探索装置はエントリの再挿入を行う（２０４）。
【００２９】
ステップＳ２０４でのエントリ再挿入後、近傍探索装置はエントリ数が最大値を超えているかどうか再び判定する（Ｓ２０５）。エントリ数が最大値を超えている場合（Ｓ２０５，Ｙｅｓ）、近傍探索装置はその葉ノードを分割する（Ｓ２０６）。次に、近傍探索装置は包囲球あるいは包囲矩形を変更したセルの親ノードに対して、親子関係が包含関係となるよう矩形と球を変更する（Ｓ２０７）。
【００３０】
ステップＳ２０７若しくはステップＳ２０５において、エントリ数の判定で最大値を超えていない場合（ステップＳ２０３、Ｎｏ又はステップＳ２０５、Ｎｏ）、近傍探索装置は直ちにステップＳ２０７に移行し、包囲球あるいは包囲矩形を変更したセルの親ノードに対して、親子関係が包含関係となるよう矩形と球を変更する（Ｓ２０７）。
以上で、登録処理が終了する。
【００３１】
［４．本発明のセルのデータ構造］
次に、本発明の特徴である、セル（矩形と球）のデータ構造について説明する。
本発明のセル（矩形と球）のデータ構造は、多次元空間におけるベクトルデータ集合のインデックス情報を多次元空間木構造として格納するために、多次元空間をセルである矩形と球の論理積の領域に分割し、その領域情報を木構造のノードに格納する多次元インデックスのセルのデータ構造である。このデータ構造は、矩形及び球の共通の中心座標と、前記矩形の中心から各軸と平行な辺までの最短距離と、球の半径のみからなることを特徴としている。
【００３２】
従来手法の問題点を解決するための本発明にかかるセルのデータ構造を示す。図７（Ａ）は２次元の特徴量空間における本発明のセルの例、図７（Ｂ)は３次元の特徴量空間における本発明にかかるセルの例である。
【００３３】
図７（Ａ）に示す例において、矩形７０１は、矩形７０１の中心７０３と、各軸に沿った中心からの長さｌｘ、ｌｙにより一意に定められる。矩形７０１の中心７０３は、矩形７０１の頂点の中で最小値を持つ最小点と、最大値を持つ最大点との平均値をさす。したがって任意の軸において、中心から軸と順方向と逆方向との長さは等しくなる。円(球に相当する）７０２は、中心ｃと半径ｒにより定まる。中心ｃは矩形７０１の中心７０３と同一点である。半径ｒは、そのセルが包含する実データまたは子ノードのセルのうち、中心から最も離れているものまでの距離によって定まる。
【００３４】
図７（Ｂ）に示す例において、矩形(直方体又は立方体）７１１は、矩形７１１の中心７１３と、各軸に沿った中心からの長さｌｘ、ｌｙ、ｌｚにより一意に定められる。矩形７１１の中心７１３は、矩形７１１の頂点の中で最小値を持つ最小点と、最大値を持つ最大点との平均値により定まる。
【００３５】
球７１２は、球７１２の中心７１３の座標と、半径ｒにより一意に定められる。球７１２の中心７１３は矩形７１１の中心７１３と一致させる。なお、矩形（直方体）７１１の中心７１３は、２次元における矩形７０１の場合と同様に、矩形（直方体）７１１の頂点の中で最小値を持つ最小点と、最大値を持つ最大点との平均値をさす。半径ｒはそのセルが包含する実データまたは子ノードのセルのうち、中心から最も離れているものまでの距離によって定まる。
【００３６】
本発明において、Ｄ次元におけるセル１個あたりのデータは次のように表される。
セルのデータ＝（Ｃ、l1、… 、li、… 、lD、r）  …式（１）
但し、上記式（１）においてC：矩形および球の中心座標、li：軸iにおける矩形の長さ（但し、１≦ｉ≦Ｄ）、D：データの次元数、r：球の半径である。
【００３７】
また、上記Ｃで表される中心座標は次元数（Ｄ個）のデータ（例えば、Ｃ＝（ｃ１、ｃ２、…、ｃＤ））で表現されるため、本発明におけるセル１個あたりのデータ量は２Ｄ＋１となる。一方、従来のSR-treeでは（球の中心＋球の半径＋矩形の最小点＋矩形の最大点）とデータの次元数の約３倍（３Ｄ＋１）であるため、本発明は従来手法と比較して、1個のノードにつき約２／３倍にデータ量を減らすことができる。
【００３８】
本発明のセルは、上記データ構造とすることにより、R-treeなどの矩形の最小点と最大点のみで表されるtree構造と、ほぼ同じデータ量のままSR-treeの近傍検索の精度を引き継ぐことができる。
【００３９】
［５．セル生成方法］
上記データ構造を有するセルのデータは、以下の処理方法（セル生成方法）により生成できる。
このセル生成方法は、多次元空間におけるベクトルデータ集合のインデックス情報を多次元空間木構造として格納するために、多次元空間を矩形と球の論理積の領域に分割し、その領域情報を木構造のノードに格納する多次元インデックスのセル生成方法であって、矩形の頂点であって、最遠関係にある頂点同士を両端とする対角線の中点を矩形の中心に決定するステップと、球の中心を前記矩形の中心と同一の点に決定するステップと、前記球の半径を前記球の子ノードが表す領域を完全に包含する最小の長さに決定するステップと、前記矩形の大きさを矩形の中心から各軸と平行な辺までの最短距離とするステップと
を有するセル生成方法である。
【００４０】
以下に、このセル生成方法をより詳細に説明する。
[５．１．葉ノードにおける矩形の中心と長さ]
上記式（１）に示したデータ構造を用いて、多次元インデックスにおける葉ノードに対応するセルのうち矩形の作成、すなわち葉ノードが包含する実データの点集合から、その実データを収容する矩形の中心および長さを求める方法を示す。
【００４１】
矩形の中心座標は矩形の最小点と最大点の中間点、すなわち上記実データの点集合から全ての次元ごとに求められた最大値と最小値それらの平均値で定められる。したがって、n個のD次元点データの集合をP1= (p11, p12, … , p1D), P2 = (p21, p22, … , p2D), … , Pn = (pn1, pn2, … , pnD)としたときの矩形の最小点Rmおよび最大点RMの座標は
【００４２】
【数１】
2011081554.tif 000003
により決定される。
【００４３】
また、矩形の中心Cr(cr1, cr2, … , crD)は
【数２】
2011081554.tif 000004
【００４４】
矩形の長さlは
【数３】
2011081554.tif 000005
【００４５】
を計算することにより決定される。上記のように計算することにより、セルのうち矩形部分が定まる。
【００４６】
[５．２．葉ノードにおける球の中心と半径]
セルの球については以下の処理方法により定める。
Ｄ次元の超球の中心CS(cs1, cs2, … , csD)は前述の通り、矩形の中心と同一の座標である。したがって、矩形の中心を求めることにより、超球の中心CSが自動的に定まる。
【００４７】
超球の半径rは前記矩形の中心からの距離が最も遠い点（実データ）の座標までの距離となるので、前記セルに包含される実データのうち、前記中心CSから最も遠い実データと中心CSとの距離を半径ｒとする。半径ｒは下記式の計算を実行することにより定まる。
【００４８】
【数４】
2011081554.tif 000006
【００４９】
実データと中心CSとの距離の算出方法は、本実施の形態ではユークリッド距離による算出方法を用いるものとして説明するが、マンハッタン距離や最大距離による算出方法により、実データと中心CSとの距離を算出するようにしても本発明は成立する。
【００５０】
ユークリッド距離による実データＰｎと中心Ｃｓとの距離の算出式は以下の通りである。
【００５１】
【数５】
2011081554.tif 000007
【００５２】
但し、上記式においてｐｎｉはＤ次元空間内のある実データの座標Ｐｎ＝（ｐｎ１、ｐｎ２、…、ｐｎＤ）のｉ番目の成分であり、ｃｓｉはＤ次元空間内のある実データの座標Ｃｓ＝（ｃｓ１、ｃｓ２、…、ｃｓＤ）のｉ番目の成分である。
【００５３】
また、マンハッタン距離による実データＰｎと中心Ｃｓとの距離の算出式は以下の通りである。
【００５４】
【数６】
2011081554.tif 000008
【００５５】
上記式においてｐｎｉ、ｃｓｉの意味は先のユークリッド距離による実データＰｎと中心Ｃｓとの距離の算出式の場合と同様である。
【００５６】
[５．３．葉以外のノードにおける矩形の中心と長さ]
次に、葉ノード以外のノードの第１の包囲図形である矩形の中心Ｃｒの計算方法を示す。
【００５７】
まず中心を求める対象であるノード（算出対象ノードと呼ぶこととする）が包含するノードに対応する矩形の集合（矩形集合と呼ぶ）のそれぞれ矩形の最小点および最大点を求め、さらにそれら矩形集合を包含する矩形Rの最小点および最大点を求める。図８に、Ｄ次元空間におけるある算出対象ノードに対応する矩形Ｒとそれに包含される矩形の例を示す。計算対象ノードに対応する矩形Ｒはｎ個の矩形Ｒ１、Ｒ２，…、Ｒｎを包含している。但し、図８では、代表して矩形Ｒ１、Ｒ２，Ｒｎの３個のみ図示し、矩形Ｒ３からＲｎ−１については図示を省略する。矩形Ｒ１、Ｒ２，Ｒｎは、それぞれの中心Ｐ１，Ｐ２，Ｐｎがあり、また矩形Ｒ１、Ｒ２，Ｒｎは、次元iについての軸方向距離ｌ１ｉ、ｌ２ｉ、ｌｎｉが定まっている。
【００５８】
n個の矩形集合Rj = (Pj, Lj)（1≦j≦ｎ）があり、中心Pjの座標を(pj1, pj2, … , pjD)とし、Ljの各軸の辺長を (lj1, lj2, … , ljD)とするとき、次元i（1≦ｉ≦Ｄ）におけるRｊの最大値、最小値はそれぞれ
【００５９】
【数７】
2011081554.tif 000009
【００６０】
【数８】
2011081554.tif 000010
【００６１】
となる。 
【００６２】
あとは葉ノードのときと同様の手順で、上記数式[数２]及び[数３]に示した算出式によりこの算出対象ノードの矩形の中心と各次元の長さを計算することにより、計算対象ノードの矩形を定めることができる。
【００６３】
[５．４．葉ノード以外のノードにおける球の中心と半径]
次に、葉ノード以外のノードにおける第２の包囲図形である球の中心Ｃｓと半径ｒの決定方法について述べる。
【００６４】
葉ノード以外のノードにおいても、矩形の中心Ｃｒを球の中心Ｃｓとする。矩形の中心Ｃｒの算出処理については先に述べたとおりである。葉ノード以外のノードにおける球の半径ｒは従来手法と同様に、その中心Ｃｓから子ノードの球までの距離と半径とを加算した値のなかでの最大値となる。
【００６５】
図９に、Ｄ次元空間におけるある算出対象ノードに対応する第２の包囲図形である球とそれに包含されるノードに対応する球の例を示す。計算対象ノードに対応する球Ｓはｎ個の球Ｓ１、Ｓ２，…、Ｓｎを包含している。但し、図９では代表して球Ｓ１、球Ｓ２，球Ｓｎの３個のみ図示し、球Ｓ３からＳｎ−１については図示を省略した。球Ｓ１、Ｓ２，Ｓｎは、それぞれの中心Ｐ１，Ｐ２，Ｐｎがあり、また球Ｓ１、Ｓ２，Ｓｎは、半径ｒ１、ｒ２、ｒｎが定まっている。n個の子ノード球S1〜Snの包囲球Sの中心をCSとしたとき、球Sの半径ｒは次の式により決定される。
【００６６】
【数９】
2011081554.tif 000011
【００６７】
なお、上記式[数９]での
【００６８】
【数１０】
2011081554.tif 000012
【００６９】
の計算方法について本実施の形態では前掲の[数５]に示したユーグリット距離の計算方法を用いるものとするが、マンハッタン距離やその他の距離計算方法によって、これらの計算をおこなうようにしても本発明は成立する。
【００７０】
本実施の形態においては、データ構造を以上のように変更すると、データの登録・削除・検索アルゴリズムも従来手法とは変更する必要がある。変更する処理は、データとセルの距離計算、セルの位置や大きさの調整である。従来手法とは異なり、球の中心は矩形の中心に合わせるため、セルの大きさを調整するときはまず矩形から行う必要がある。
【００７１】
[６．セル外部の点から矩形までの最短距離の計算]
セルの外部に位置する所定の点からSR-treeのセルまでの最短距離は、データ（所定点）から矩形までの最短距離と、データ（所定点）から球までの最短距離のうち、どちらか長い方を採用する。本発明では、データ（所定点）から矩形までの距離の算出方法が従来手法とは若干異なるので、本発明のデータ（所定点）から矩形までの距離の算出方法について以下に述べる。
【００７２】
セルの外部にある所定点の座標をP (p1, … , pD)とするとき、点Pから矩形Ｒまでの最短距離drは、
【００７３】
【数１１】
2011081554.tif 000013
【００７４】
と表される。上記[数１１]において、diは特定の軸i（ただし１≦ｉ≦Ｄ；Ｄは次元数）についての距離であり、矩形の中心座標をC(c1, c2, … , cD)、各軸方向の辺長ベクトルをL (l1, l2, … , lD)とするとき、diは次のようにして計算される。
（ａ）ｃｉ−ｌｉ≦ｐｉ≦ｃｉ＋ｌｉならばdi= 0
（ｂ）ｐｉ＜ｃｉ−ｌｉならばdi＝ci-li- pi
（ｃ）ｃｉ＋ｌｉ≦ｐｉならばdi = pi - (ci - li)
上記ｄｉの計算方法について図１０（Ａ）から図１０（Ｃ）に示す。図１０（Ａ）は上記（ａ）の場合の所定点Ｐと矩形の関係を示し、図１０（Ｂ）は上記（ｂ）の場合の所定点Ｐと矩形の関係を示し、図１０（Ｃ）は上記（ｃ）の場合の所定点Ｐと矩形の関係を示す。
【００７５】
[７．セル拡張(調整)方法]
次に、本実施の形態におけるセル拡張（調整）方法について説明する。セルの外部に位置する点（実データ）をセルに挿入するには、セルを拡張して点を内部に取り込むものとする。ここでは、セルの拡張すなわち矩形と球の大きさを調整するときの方法についてそれぞれ述べる。
このセル拡張(調整)方法は、多次元インデックスのデータ構造において、葉ノードの外に位置する所定の点を新たにインデックスに格納するために、その点からみて最近傍の葉ノードが持つ矩形および球の領域を拡張するインデックスのセル拡張（調整）方法であって、前記葉ノードの矩形の中心および長さをその点を包含するように変更するステップと、前記葉ノードの球の中心を前記矩形の新たな中心とし、前記球の半径をその点を包含するように変更するステップと、前記葉ノードが親ノードの領域外に出た場合は、この親ノードも葉ノードを完全に包含するように領域を変更し、包含関係を根ノードまで保つように変更するステップとを有する多次元インデックスのセル拡張（調整）方法である。
以下に、上記セル拡張方法をより詳細に説明する。
【００７６】
[７．１．セルの拡張（調整）：矩形の場合]
まず、セルのうち、矩形の拡張(調整)について説明する。  
ある実データである点を矩形に取り込むときの方針は、各次元において、点の座標が矩形の最大点の座標よりも大きければ矩形の位置を右にずらし、同時に矩形の長さを長くすることで体積の増加を最小限にするものである。同様に、点の座標が矩形の最小点の座標よりも小さければ、矩形の位置を左にずらし、矩形の長さを長くする。
【００７７】
以下に、矩形の調整の具体例を説明する。ある軸xにおける矩形の中心をcx、長さをlx、取り込む点Ｐの座標をpxとする。
【００７８】
点Ｐが矩形の右側外部にあるとき、すなわちcx+lx<pxであるとき、取り込んだ後の矩形の長さl’xは
【数１２】
2011081554.tif 000014
【００７９】
矩形の中心c’xは
【数１３】
2011081554.tif 000015
となる。
【００８０】
逆に点Ｐが左側外部にあるとき、すなわちpx<cx−lxであるとき、取り込んだ後の矩形の長さl’xは
【数１４】
2011081554.tif 000016
【００８１】
矩形の中心c’xは
【数１５】
2011081554.tif 000017
となる。
【００８２】
図１１（Ａ）から図１１（Ｃ）に1次元空間において点Ｐを取り込んだときの矩形の調整例を示す。図１１（Ａ）は調整前の矩形を示す図であり、図１１（Ｂ）は点Ｐが矩形の右側にあるとき、すなわちcx+lx<pxであるときに、中心c’x、長さ長さl’xとなるように調整された矩形を示し、図１１（Ｃ）は点Ｐが矩形の左側にあるとき、すなわちcx+lx<pxであるときに、中心c’x、長さ長さl’xとなるように調整された矩形を示している。
【００８３】
図１１（Ａ）はx軸において、矩形の中心cxと長さlxによって矩形の範囲を表している。図１１（Ｂ）では矩形の右隣の点pxを矩形に取り込んだときの矩形の中心c’xはcxより右にずれ、長さl’xはlxより長い。図１１（Ｃ）では矩形の左隣の点pxを取り込んだときの矩形の中心c’xはcxより左にずれ、長さl’xはlxより長い。
【００８４】
[７．２．セルの拡張（調整）：球の場合]
次に、セルのうち、球の調整について説明する。  
【００８５】
近傍探索装置２０、より詳しくはインデックス管理部２７は、球の外部にある新たな点を球に取り込むときは、矩形の中心の変更に伴って球の中心Ｃも矩形の新たな中心C’にずれるため、球の半径rも変更する。すなわち、変更後の球の中心C’から内部の点P1〜Pnと球の外側にある点Pまでの距離で最大となる値が半径r'となる。半径ｒ'は以下の式で決定される。
【００８６】
【数１６】
2011081554.tif 000018
【００８７】
球の外側にある点Pを取り込んで球が調整される例を図１２に示す。調整前の球Ｓ（点線で表示）は、中心Ｃ，半径ｒであって、内部にｎ個の実データに相当する点Ｐ１，Ｐ２，…、Ｐｎを有している（但し、図１１において点Ｐ３〜Ｐｎ−1は図示省略）。ここで球Ｓの外部にある点Ｐを取り込むよう調整をおこなうと、中心Ｃ’、半径ｒ’である球Ｓ’(実践で表示)となり、球Ｓ’は座標点Ｐ１，Ｐ２，…、Ｐｎに加えて点Ｐを取り込む包囲図形となる。
【００８８】
[８．セルの分割]
近傍探索装置２０、より詳しくはインデックス管理部２７は、再挿入後に、セル内の点の個数が上限値を超えたためにセルを分割するときは、一般的にはセルの「種」となる距離が離れた2点を選び、種に1点ずつ追加していきグループを作る。この手順に関して本発明での変更点はない。点集合を2個のグループに分割したら、そこから新しくセルを作り直すときに、前述のセルの拡張（調整）と同じ方法をとる。
【００８９】
[９．本発明にかかる多次元インデックスを利用した検索方法]
本発明にかかる多次元インデックスを利用した検索(近傍探索）方法は、基本的には従来の検索（近傍探索）方法と同様であるが、ある点(クエリ点など)とセルとの最短距離の計算方法は、前述の[セル外部の点から矩形までの最短距離の計算]の項で述べた計算方法により行う。具体的には図５に示したフローチャート中、ステップＳ１０２及びステップＳ１１０で行う距離計算を本発明の最短距離計算方法（[６．セル外部の点から矩形までの最短距離の計算]の項参照）で行うことにより、本発明にかかる多次元インデックスを利用した検索(近傍探索）方法の実行が可能となる。
【００９０】
[１０．本発明にかかる多次元インデックスにおいての点の登録（挿入）方法]
本発明にかかる多次元インデックスにおいての点の挿入方法は、基本的には従来の方法と同様であるが、図６に示す登録（挿入）方法においてステップＳ２０１、Ｓ２０４、Ｓ２０６，Ｓ２０７で、ある点(クエリ点など)とセルとの最短距離の計算方法は、前述の[セル外部の点から矩形までの最短距離の計算]の項で述べた計算方法により行い、また、ステップＳ２０６、Ｓ２０７においてはセルの拡張(調整)を行うことになる。
【００９１】
[１１．好適な実施例]
本発明により、球の半径が従来手法と異なることで球の体積も変化し、検索効率に影響を与える可能性もある。
従来手法によって作成されるはずのセルの球S（半径r）が本発明によってS’（半径r’）へと変化したとき、D次元超球の体積は（ｒ’／ｒ）Ｄの割合で増加する。したがって、従来手法の球の半径が最大かつ本発明での球の半径が最小であるときに最も効果的となる。
【００９２】
ある軸に沿って十分離れた位置に小さいセルが2個存在し、これらのセル内部に含まれる点集合の個数に大きく差がある場合を考える。このとき、従来手法での球の中心は限りなく点の個数が多い集合に引き寄せられるのに対して、本発明では2個のセルを最小限の大きさで囲む矩形の中心となる。
【００９３】
したがって、本発明での球の半径は従来手法の約１／２倍となり、Ｄ次元超球の体積は(１／２）Ｄ倍となる。図１３は２次元空間での実施例を示している。点線で囲まれた球Sと点CSは、それぞれ従来手法での包含球とその中心である。実線で囲まれた球S’と点CS’は、それぞれ本発明での包含球とその中心であり、半径をr’とする。このときSの半径は2r’となる。
【００９４】
[１２．本発明の利点]
（１）本発明によれば、データの次元数が上がってもデータ量の増加はR-treeと同じで済み、SR-tree の特徴とアルゴリズムを引き継ぐため、近傍検索の効率は矩形や球を単独で用いるR-treeやSS-treeなどより高いままである。したがって、本発明により検索精度を維持しつつ省メモリを実現することが可能である。
（２）本発明によれば、新たに所定の点を葉ノードに取り込むときには、矩形を先に処理することによって、矩形の利点である体積の増加を最小限に保つことができる。
【００９５】
仮に球を先に処理すると、新しい球の中心は新しい点を加えた重心（平均値）によって決定される。すると、点の個数が多い古い球の中心からあまり動かないため、点Ｐまでの距離すなわち新しい球の半径も長くなり、同時に矩形の長さも長くなるからである。
【図面の簡単な説明】
【００９６】
【図１】B-treeのインデックス構造を示す図
【図２】R-treeのインデックスの例を示した図
【図３】図２に示したR-treeの包含関係を示した図
【図４】近傍探索装置の構成例を示した機能ブロック図
【図５】多次元インデックスを用いた一般的な近傍探索処理の例を示したフローチャート
【図６】従来の一般的な多次元インデックスに新たなデータを登録（挿入）する登録処理の一般的な例を示したフローチャート
【図７】（Ａ）は２次元の特徴量空間における本発明のセルの例を示す図、（Ｂ)は３次元の特徴量空間における本発明にかかるセルの例を示す図
【図８】Ｄ次元空間におけるある算出対象ノードに対応する矩形Ｒとそれに包含される矩形の例を示す図
【図９】Ｄ次元空間におけるある算出対象ノードに対応する第２の包囲図形である球とそれに包含されるノードに対応する球の例を示す図
【図１０】（Ａ）は最短距離の計算における第１の場合の所定点Ｐと矩形の関係を示す図、（Ｂ）は最短距離の計算における第２の場合の所定点Ｐと矩形の関係を示す図、（Ｃ）は最短距離の計算における第３の場合の所定点Ｐと矩形の関係を示す図
【図１１】（Ａ）は調整前の矩形を示す図、（Ｂ）は点Ｐが矩形の右側にあるときの調整後の矩形を示す図、（Ｃ）は点Ｐが矩形の左側にあるときの調整後の矩形を示す図
【図１２】球の外側にある点Pを取り込んで球が調整される例を示す図
【図１３】２次元空間での本発明の好適な実施例を示した図
【符号の説明】
【００９７】
２０…近傍探索装置；  ２１…データ記憶部；  ２２…探索実行部；  ２３…入力部；  ２４…出力部；  ２５…データ；  ２６…インデックス；  ２７…インデックス管理部
【図１】
2011081554.tif 000019
【図２】
2011081554.tif 000020
【図３】
2011081554.tif 000021
【図４】
2011081554.tif 000022
【図５】
2011081554.tif 000023
【図６】
2011081554.tif 000024
【図７】
2011081554.tif 000025
【図８】
2011081554.tif 000026
【図９】
2011081554.tif 000027
【図１０】
2011081554.tif 000028
【図１１】
2011081554.tif 000029
【図１２】
2011081554.tif 000030
【図１３】
2011081554.tif 000031