(57)【特許請求の範囲】
【請求項１】
データベースに格納されるマルチメディアデータを組織する多次元空間データ構造を記録した記録媒体であって、
前記多次元空間データ構造が、
仮想包囲矩形と重心とを格納する根ノードと、この根ノードに対して子ノードとしてリンクし、最小包囲矩形を近似する仮想包囲矩形、最小包囲矩形、および配下のデータオブジェクトの重心とを格納する中間ノードと、この中間ノードに子ノードとしてリンクし、データオブジェクトを近似する相対セルと最小包囲矩形とを格納するリーフノードの３種類のノードを有する索引ノードと、
前記リーフノードに１対１の関係でリンクし、データオブジェクトを格納するデータノードと
から構成されることを特徴とする多次元空間データ構造を記録した記録媒体。
【請求項２】
請求項１記載の記録媒体に記録される多次元空間データ構造における多次元空間データ更新方法であって、
データノードに格納されているデータオブジェクトと当該データノードの親ノードに格納されている最小包囲矩形から相対セルの部分空間符号を計算し、根ノード以外の索引ノードに格納されている最小包囲矩形と当該索引ノードの親ノードに格納されている最小包囲矩形から仮想包囲矩形の部分空間符号を計算することを特徴とする多次元空間データ更新方法。
【請求項３】
請求項１記載の記録媒体に記録される多次元空間データ構造における多次元空間データ探索方法であって、
根ノードおよび中間ノードでは最小包囲矩形と部分空間符号から仮想包囲矩形を計算し、リーフノードでは最小包囲矩形と部分空間符号から相対セルを計算し、データノードのアクセスにおいてデータオブジェクトを取得することを特徴とする多次元空間データ探索方法。
【請求項４】
請求項１記載の記録媒体に記録される多次元空間データ構造における多次元空間データ更新方法をコンピュータに実行させるプログラムを記録した記録媒体であって、
データノードに格納されているデータオブジェクトと当該データノードの親ノードに格納されている最小包囲矩形から相対セルの部分空間符号を計算し、根ノード以外の索引ノードに格納されている最小包囲矩形と当該索引ノードの親ノードに格納されている最小包囲矩形から仮想包囲矩形の部分空間符号を計算することを特徴とする多次元空間データ更新プログラムを記録した記録媒体。
【請求項５】
請求項１記載の記録媒体に記録される多次元空間データ構造における多次元空間データ探索方法をコンピュータに実行させるプログラムを記録した記録媒体であって、
根ノードおよび中間ノードでは最小包囲矩形と部分空間符号から仮想包囲矩形を計算し、リーフノードでは最小包囲矩形と部分空間符号から相対セルを計算し、データノードのアクセスにおいてデータオブジェクトを取得することを特徴とする多次元空間データ探索プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データベースに格納される多次元空間データの探索技術に関し、特に多次元空間データ構造を記録した記録媒体、多次元空間データ更新方法、多次元空間データ探索方法および前記方法を実施するプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
従来の空間アクセス法の中で、高次元空間の探索に有用な手法としてＲ−ｔｒｅｅとその派生手法がある（以下、Ｒ−ｔｒｅｅファミリーと呼ぶ）。Ｒ−ｔｒｅｅファミリーには、Ｒ−ｔｒｅｅ，Ｒ*−ｔｒｅｅ，Ｈilbert Ｒ−ｔｒｅｅ，ＳＳ−ｔｒｅｅ，ＳＲ−ｔｒｅｅなどがあり、いずれもデータオブジェクトは最小包囲領域、つまり最小包囲矩形（ＭＢＲ；Minimum Bounding Rectangle）もしくは最小包囲球（ＭＢＳ；Minimum Bounding Sphere）に梱包され、更に階層構 造をなしている。
【０００３】
ＳＲ−ｔｒｅｅは、図７に示すように、ＭＢＲとＭＢＳを用いる木構造である。探索においては、問い合わせ点とＭＢＲとの距離、問い合わせ点とＭＢＳとの距離を計算し、距離の長い方をエントリと問い合わせ点との距離とする。ＭＢＲとＭＢＳを探索に用いることにより、枝刈り処理の効率化を図っている。
【０００４】
ＭＢＲの位置座標の符号化を用いた手法としてＶＲ−ｔｒｅｅ（特願２０００−８０５６）がある。仮想包囲矩形（ＶＢＲ；Virtual Bounding Rectangle）によってＭＢＲは近似され、相対セル（relative cell）によってデータオブジェ クトは近似され、ＶＢＲと相対セルは部分空間符号により表現される。
【０００５】
図８は、部分空間符号を計算する方法について簡単に例示したものである。ｎ次元空間内のｉ次元座標において、包囲矩形Ａが座標値として（３，１９）を、そして包囲矩形Ｂが同様に座標値として（６，８）を占めている。このとき、長さｌの符号を用いて、Ａのｉ次元座標範囲を２lの部分区間に等分割することに より、Ｂの始点をそれが存在する部分区間によって近似的に表現することができる。これは、Ｂの終点についても同様である。例えば、長さ３の符号を用いて、Ａの領域を８つの部分区間に分割した場合、ＢはＡの始点から数えて前から２番目と３番目の部分区間を占めていることになる。それゆえ、ｉ次元座標におけるＢの領域は８元符号（１，２）、もしくは２進符号では（００１，０１０）のように近似的に表現することが可能である。この場合、２進符号において必要な符号長は、Ｂの始点、終点それぞれに３であるため、次元あたり合計６となる。
【０００６】
ＶＲ−ｔｒｅｅでは、２種類の木構造索引を構築する。絶対的位置表現を用いる木構造である実部分、部分空間符号に基づいた相対的位置表現を用いる木構造である仮想部分によって成り立っている。図９に索引構造の例を示す。図９（ａ）において、全体空間をＲとする。ＭＢＲ Ｍ１，Ｍ２はＲに包含されており、 Ｖ１，Ｖ２は各々Ｒに基づいて、Ｍ１とＭ２を近似している。Ｖ１，Ｖ２は各々ＲにおけるＭ１のＶＢＲ、ＲにおけるＭ２のＶＢＲである。また同様に、図９（ｂ）において、Ｖ３，Ｖ４は各々Ｖ１におけるＭ３のＶＢＲ、Ｖ１におけるＭ４のＶＢＲである。更に図９（ｃ）に示すように、データオブジェクトＰ１，Ｐ２はＭ３に包含されている。Ｃ１，Ｃ２は各々Ｖ３に基づいてＰ１とＰ２を近似している。Ｃ１，Ｃ２は各々Ｖ３におけるＰ１の相対セル、Ｖ３におけるＰ２の相対セルである。図９（ａ），（ｂ），（ｃ）に示したＭＢＲ，ＶＢＲ、データオブジェクト、相対セルは、図９（ｄ）のように構成される。実部分のノードにはＭＢＲとデータオブジェクトが格納され、仮想部分のノードにはＶＢＲあるいは相対セルの部分空間符号が格納される。仮想部分のノードと実部分のノードは１対１の関係を保つ。
【０００７】
【発明が解決しようとする課題】
上述した従来のＶＲ−ｔｒｅｅは、次に示すような問題がある。
【０００８】
データオブジェクトが索引へ新たに挿入する場合、もしくは削除する場合、索引の更新処理が発生する。ＶＲ−ｔｒｅｅでは実部分のみならず、仮想部分についても更新する必要があるため、従来手法より多くの更新コストが発生する。実用においては、更新が頻繁に発生するケースも考えられるため、更新コストを低減化することが望まれる。
【０００９】
具体的に、ＶＲ−ｔｒｅｅにおける更新処理の概要、多くの更新コストが発生する理由について説明する。実部分におけるＭＢＲの修正処理は上向きに伝播するが、仮想部分における部分空間符号の修正は下向きに伝播する。実部分においてＭＢＲやデータオブジェクトが更新されると、対応するＶＢＲや相対セルの符号についても更新する。更に、更新した符号のエントリを頂点として、その配下に位置するすべてのノードにアクセスし、ノードが保有する部分空間符号を検査する必要がある。そして、必要があれば更新する。手順は以下の通りである。
【００１０】
（１）更新したＭＢＲに対応するＶＢＲの符号、もしくは更新したデータオブジェクトに対応する相対セルの符号を更新するため、仮想部分において根ノードから下位ノードに向かってＶＢＲを計算していく。
【００１１】
（２）更新したＭＢＲやデータオブジェクトに対応する符号を計算し、更新する。
【００１２】
（３）更新したエントリを頂点とする配下の部分木内のすべてのノードにアクセスし、ノードに格納されている符号を検査し、必要があれば更新する。
【００１３】
（３）において記述されているように、ＶＲ−ｔｒｅｅでは、部分空間符号に修正を必要としないノードに達しても終了せず、引き続き下位ノードへ処理を伝播させ、部分木内のすべてのノードにアクセスする。何故なら、部分空間符号は相対的位置を用いているためにＶＢＲには幾分かの誤差が含まれており、現ノードにおいて更新の必要が無い場合でも下位ノードでは修正を必要とする可能性があるためである。図１０を用いてこの理由について説明する。図９において矩形Ａ，Ｂ，Ｃを各々全体空間、子ノードのＭＢＲ、孫ノードのＭＢＲとする。また、Ｖbを基数４のＡにおけるＢのＶＢＲとし、Ｖcを基数４のＶbにおけるＣのＶ ＢＲとする。データオブジェクトの挿入により、図９（ａ）から図９（ｂ）のように矩形Ａのみがｘ軸方向に拡張したとする。このとき、Ｂのサイズに変動はないが、Ａの拡張によってＶbは拡張する。そして、サイズに変動のないＣに関し ては、Ｖbのサイズ変動によりＣのＶＢＲ Ｖcは縮小する。この場合、Ｖbの部分空間符号に修正の必要はないが、Ｖcの部分空間符号には修正が必要である。
【００１４】
ＶＲ−ｔｒｅｅは上述のように付加的な更新コストを必要とする。木構造の上部のレベルのＭＢＲが変更された場合、特に多くのコストを必要とする。
【００１５】
本発明は、上記に鑑みてなされたもので、その目的とするところは、少ない時間でオブジェクトを検索でき、高い探索性能を有する多次元空間データ構造を記録した記録媒体、多次元空間データ更新方法、多次元空間データ探索方法および前記方法を実施するプログラムを記録した記録媒体を提供することにある。
【００１６】
【課題を解決するための手段】
上記目的を達成するため、請求項１記載の本発明の多次元空間データ構造を記録した記録媒体は、データベースに格納されるマルチメディアデータを組織する多次元空間データ構造を記録した記録媒体であって、前記多次元空間データ構造が、仮想包囲矩形と重心とを格納する根ノードと、この根ノードに対して子ノードとしてリンクし、最小包囲矩形を近似する仮想包囲矩形、最小包囲矩形、および配下のデータオブジェクトの重心とを格納する中間ノードと、この中間ノードに子ノードとしてリンクし、データオブジェクトを近似する相対セルと最小包囲矩形とを格納するリーフノードの３種類のノードを有する索引ノードと、前記リーフノードに１対１の関係でリンクし、データオブジェクトを格納するデータノードとから構成されることを要旨とする。
【００１７】
請求項１記載の本発明にあっては、データノードにデータオブジェクトを格納し、リーフノードにデータオブジェクトを近似する相対セルと最小包囲矩形を格納し、中間ノードに最小包囲矩形を近似する仮想包囲矩形、最小包囲矩形、配下のデータオブジェクトの重心を格納し、根ノードに仮想包囲矩形と重心を格納するように構成した多次元空間データ構造を記録媒体に記録しているため、該記録媒体を用いて、データベースに格納されるマルチメディアデータを組織する多次元空間データ構造の流通性を高めることができる。
【００１８】
また、請求項２記載の本発明の多次元空間データ更新方法は、請求項１記載の記録媒体に記録される多次元空間データ構造における多次元空間データ更新方法であって、データノードに格納されているデータオブジェクトと当該データノードの親ノードに格納されている最小包囲矩形から相対セルの部分空間符号を計算し、根ノード以外の索引ノードに格納されている最小包囲矩形と当該索引ノードの親ノードに格納されている最小包囲矩形から仮想包囲矩形の部分空間符号を計算することを要旨とする。
【００１９】
請求項２記載の本発明にあっては、データノードに格納されているデータオブジェクトと親ノードに格納されている最小包囲矩形から相対セルの部分空間符号を計算し、根ノード以外の索引ノードに格納されている最小包囲矩形と親ノードに格納されている最小包囲矩形から仮想包囲矩形の部分空間符号を計算することでデータオブジェクトの挿入や削減に伴う索引の更新を低コストで実施する。
【００２０】
更に、請求項３記載の本発明の多次元空間データ探索方法は、請求項１記載の記録媒体に記録される多次元空間データ構造における多次元空間データ探索方法であって、根ノードおよび中間ノードでは最小包囲矩形と部分空間符号から仮想包囲矩形を計算し、リーフノードでは最小包囲矩形と部分空間符号から相対セルを計算し、データノードのアクセスにおいてデータオブジェクトを取得することを要旨とする。
【００２１】
請求項３記載の本発明にあっては、根ノードおよび中間ノードでは最小包囲矩形と部分空間符号から仮想包囲矩形を計算し、リーフノードでは最小包囲矩形と部分空間符号から相対セルを計算し、データノードのアクセスにおいてデータオブジェクトを取得することで短時間でオブジェクトを検出することが可能となり、高い探索性能を実現する。
【００２２】
請求項４記載の本発明の多次元空間データ更新プログラムを記録した記録媒体は、請求項１記載の記録媒体に記録される多次元空間データ構造における多次元空間データ更新方法をコンピュータに実行させるプログラムを記録した記録媒体であって、データノードに格納されているデータオブジェクトと当該データノードの親ノードに格納されている最小包囲矩形から相対セルの部分空間符号を計算し、根ノード以外の索引ノードに格納されている最小包囲矩形と当該索引ノードの親ノードに格納されている最小包囲矩形から仮想包囲矩形の部分空間符号を計算することを要旨とする。
【００２３】
請求項４記載の本発明にあっては、データノードに格納されているデータオブジェクトと親ノードに格納されている最小包囲矩形から相対セルの部分空間符号を計算し、根ノード以外の索引ノードに格納されている最小包囲矩形と親ノードに格納されている最小包囲矩形から仮想包囲矩形の部分空間符号を計算する多次元空間データのデータ更新プログラムを記録媒体に記録しているため、該記録媒体を用いて、データオブジェクトの挿入や削減に伴う索引の更新を低コストで実施する多次元空間データ更新プログラムの流通性を高めることができる。
【００２４】
また、請求項５記載の本発明の多次元空間データ探索プログラムを記録した記録媒体は、請求項１記載の記録媒体に記録される多次元空間データ構造における多次元空間データ探索方法をコンピュータに実行させるプログラムを記録した記録媒体であって、根ノードおよび中間ノードでは最小包囲矩形と部分空間符号から仮想包囲矩形を計算し、リーフノードでは最小包囲矩形と部分空間符号から相対セルを計算し、データノードのアクセスにおいてデータオブジェクトを取得することを要旨とする。
【００２５】
請求項５記載の本発明にあっては、根ノードおよび中間ノードでは最小包囲矩形と部分空間符号から仮想包囲矩形を計算し、リーフノードでは最小包囲矩形と部分空間符号から相対セルを計算し、データノードのアクセスにおいてデータオブジェクトを取得する多次元空間データ探索プログラムを記録媒体に記録しているため、該記録媒体を用いて、短時間でオブジェクトを検出し、高い探索性能を実現する多次元空間データ探索プログラムの流通性を高めることができる。
【００２６】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態を説明する。本発明では、上述したＶＲ−ｔｒｅｅが有する問題から鑑みて、（１）更新処理では、親ノードのＶＢＲではなく、親ノードのＭＢＲから部分空間符号を計算し、（２）探索処理では、少ないページアクセスでＭＢＲと部分空間符号のデータを取得するという特質を有するデータ構造およびアルゴリズムを有する新たな索引手法であるＶＲ−ｔｒｅｅを改良したＡ−ｔｒｅｅ（Approximation Tree）を提案している。
【００２７】
このＡ−ｔｒｅｅでは、上位のノードのＭＢＲから相対的にＶＢＲや相対セルの部分空間符号を計算する。また、部分空間符号と親ノードのＭＢＲを同一のノードに格納する。
【００２８】
図１は、このＡ−ｔｒｅｅの構造の一例を示す図である。図１（ａ）において、全体空間をＲとする。ＭＢＲ Ｍ１，Ｍ２はＲに包含されており、ＭＢＲ Ｍ３，Ｍ４はＭ１に包含されている。更にデータオブジェクトＰ１，Ｐ２はＭ３に包含されている。この構造において、Ｖ１，Ｖ２，Ｖ３，Ｖ４は各々ＲにおけるＭ１のＶＢＲ、ＲにおけるＭ２のＶＢＲ、Ｍ１におけるＭ３のＶＢＲ、Ｍ１におけるＭ４のＶＢＲである。また、Ｃ１，Ｃ２は各々Ｍ３におけるＰ１の相対セル、Ｍ３におけるＰ２の相対セルである。ＭＢＲ、ＶＢＲ、データオブジェクト、相対セルは図１（ｂ）のように格納され、木構造が作られる。
【００２９】
図１（ｂ）に示すように、Ａ−ｔｒｅｅのノードは索引ノード（index node）とデータノード（data node）に分類できる。根ノード以外の索引ノードは１つ のＭＢＲ（Ｍとする）、子ノードに関するＭＢＲ（もしくはデータオブジェクト）を近似するＶＢＲ（もしくは相対セル）の部分空間符号を保有している。Ｍは子ノードに格納されているＭＢＲ（もしくはデータオブジェクト）を包含するＭＢＲである。根ノードではＭＢＲは格納しない。根ノードでは全体空間から子ノードのＶＢＲを計算することができる。Ａ−ｔｒｅｅを構築するとき、あるノードに格納されている子のＶＢＲ（もしくは相対セル）の符号は、子のＭＢＲ（もしくはデータオブジェクト）と同じノードに格納されている親のＭＢＲから計算される。根ノードにおいては、子のＶＢＲの符号は、子のＭＢＲと全体空間から計算される。
【００３０】
Ａ−ｔｒｅｅでは索引ノードは、リーフノード、中間ノード、根ノードに分類される。
【００３１】
１．データノード
データノードはエントリ、（Ｐ1 ，ｏ1），（Ｐ2 ，ｏ2），…，（Ｐm ，ｏm）を含んでいる。ここで、Ｐi（ｉ＝１，２，…，ｍ）はデータオブジェクトの空間ベクトルであり、ｏi（ｉ＝１，２，…，ｍ）はオブジェクト記述レコード へのポインタである。エントリ数ｍは最大値と最小値によって制限されている。
【００３２】
２．リーフノード
リーフノードはデータノードと１対１の関係があり、データノードＮ（（Ｐ1 ，ｏ1），（Ｐ2 ，ｏ2），…，（Ｐm ，ｏm））と対応するリーフノードは、 ｉ）Ｐ1 ，Ｐ2 ，…，ＰmのＭＢＲであるＭ、ii）ポインタＮ、iii）エントリのリストｓｃ（Ｖ1），ｓｃ（Ｖ2），…，ｓｃ（Ｖm）から構成される。ここで、 ＶiはＭにおけるＰi（ｉ＝１，２，…，ｍ）の相対セルであり、ＳＣ（Ｖi）は Ｖiの部分空間符号である。
【００３３】
３．中間ノード
根ノードとリーフノードを除く索引ノードが中間ノードであり、ｉ）子ノードのＭＢＲを包含するＭＢＲ Ｍ、ii）エントリ（ｐｔｒ，ｓｃ（Ｖ），ｗ，Ｐcentroid）のリストから構成される。ここで、ｐｔｒは子ノードＣへのポインタ 、ＶはＣに格納されているＭＢＲを近似するＶＢＲ、ｗはＣを頂点とする部分木内のデータオブジェクトの総数、Ｐcentroidはその部分木内のすべてのデータオブジェクトの重心である。
【００３４】
ｗとＰcentroidは、データオブジェクトの挿入と削除の際に用いられる。探索アルゴリズムではＭ，ｐｔｒ，ｓｃ（Ｖ）のみが用いられるため、実装においては、ｐｔｒとｓｃ（Ｖ）のデータを同じページに格納する。
【００３５】
４．根ノード
根ノードはエントリ（ｐｔｒ，ｓｃ（Ｖ），ｗ，Ｐcentroid）のリストから構成される。
【００３６】
次に、上述したＡ−ｔｒｅｅの更新アルゴリズムについて説明する。Ａ−ｔｒｅｅの更新アルゴリズムは、ＳＲ−ｔｒｅｅに基づいている。データオブジェクトの挿入もしくは削除から始まり、中間ノードにおけるＭＢＲと重心の調整処理は上位ノードに伝播する。Ａ−ｔｒｅｅとＳＲ−ｔｒｅｅの違いは、Ａ−ｔｒｅｅアルゴリズムがＶＢＲや相対セルの計算を必要とすることである。具体的にＡ−ｔｒｅｅ構造は以下のように更新される。
【００３７】
（１）Ｎをデータノード、ＭをＮのＭＢＲとする。そのとき、ＭはＮの親ノードに格納されている。Ｎにおいてデータオブジェクトの挿入もしくは削除が発生した場合、Ｍを調整し、Ｎに格納されているすべてのデータオブジェクトの重心を計算し、更新する。
【００３８】
（２）Ｍが変化しなかった場合、挿入オブジェクトを近似する相対セルの符号をＭから計算し、更新する。さもなければ、Ｎの親ノードに格納されているすべての符号を更新する。
【００３９】
（３）Ｎを根ノードを除く索引ノードの１つであるとし、ＭをＮのＭＢＲとする。そのとき、ＭはＮの親ノードに格納されている。データオブジェクトの挿入もしくは削除がＮを頂点とする部分木内で発生した場合、Ｎの親ノードに蓄積されているすべての重心点を更新する。更に、挿入もしくは削除が、子のＭＢＲを変更させた場合はＭを調整する。
【００４０】
（４）Ｍが変化しなかった場合、更新したＭＢＲを近似するＶＢＲの符号をＭから計算する。そして更新する。さもなければ、Ｎの親ノードに格納されているすべてのＶＢＲの符号を更新する。
【００４１】
次に、図２に示すフローチャートを参照して、上述したＡ−ｔｒｅｅを用いて近傍探索アルゴリズムについて説明する。この探索アルゴリズムは、ＶＲ−ｔｒｅｅに準じている。相違点は、ＶＲ−ｔｒｅｅがＶＢＲや相対セルの座標値を親ノードのＶＢＲから計算するのに対して、Ａ−ｔｒｅｅでは親ノードのＭＢＲから計算することである。
【００４２】
図２に示す探索アルゴリズムでは、木構造を幅優先で探索する。現ノードのＭＢＲと子ノードの部分空間符号を基にして、根ノードと中間ノードでは子ノードのＶＢＲを計算し、リーフノードでは子ノードの相対セルを計算する。そして、データノードに到達すると、オブジェクトの位置情報を収集し、候補オブジェクトとする。
【００４３】
図２においては、まずキューの先頭に根ノードを設定し（ステップＳ１１）、ステップＳ１３〜Ｓ３９のループ１の処理をキューが空きになるまで繰り返し実行する。このループ１では、まずノードへのポインタをＮに設定し、このポインタＮでキューの先頭データを指定し、問い合わせ点から最も近いノードに関するデータとしてキューから取り出すとともに、ポインタＮで示されるノード内のエントリ番号をｅに設定する（ステップＳ１５）。それから、このポインタＮで指し示されているノードがデータノードか索引ノードかを判定する（ステップＳ１７）。
【００４４】
Ｎで指し示されているノードがデータノードである場合、データノードは複数ページを占めているため、指し示されているエントリ、すなわちデータオブジェクトに関するページにのみアクセスする。具体的には、Ｎで指し示されているノード内に格納されているｅ番目のエントリをＥとし、このエントリＥであるデータオブジェクトと問い合わせ点との距離を計算して、この計算した値をＤとする（ステップＳ１９）。
【００４５】
この計算した距離Ｄを第１リストのｋ近傍距離と比較し、距離Ｄが第１リストのｋ近傍距離以下であるか否かをチェックする（ステップＳ２１）。距離Ｄが小さい場合には、この計算した距離ＤとデータオブジェクトＥを最近傍の候補として第１リストに格納しソートする（ステップＳ２３）。それから、第１リストによるキューのフィルタリングを行う（ステップＳ２５）。このフィルタリングでは、第１リストに格納されている候補のデータオブジェクトを用いて、キューの中でアクセスする必要のないデータを削除する。
【００４６】
それから、キューの先頭データを削除して、キュー内のデータを前詰めし（ステップＳ２７）、以上の処理をキューが空きになるまでループ１として繰り返し行う。
【００４７】
また、上記ステップＳ１７の判定において、Ｎによって示されるノードが索引ノードである場合には、ステップＳ３１に進み、ここでＮで示されるノードに格納されているエントリの数をｅｎｔとして設定するとともに、Ｎの仮想包囲矩形ＭＢＲをＲに設定する。それから、Ｎで示されるノードがリーフノードであるか否かを判定する（ステップＳ３３）。
【００４８】
Ｎで示されるノードがリーフノードでなく、中間ノードまたは根ノードである場合には、図３に示す処理Ａが実行され（ステップＳ３５）、リーフノードである場合には、図４に示す処理Ｂが実行される（ステップＳ３７）。
【００４９】
図３に示す処理Ａでは、まずパラメータｉが０に設定され（ステップＳ５１）、以下に続くステップＳ５３からＳ６５までのループ２で示す処理をパラメータｉが前記エントリ数ｅｎｔ以上になるまで繰り返し実行する。ループ２では、まず前記パラメータｉを＋１インクリメントし（ステップＳ５５）、ノードＮにおいてｉ番目のエントリとして格納されている部分空間符号と親ノードの矩形Ｒから子ノードのＶＢＲ（仮想包囲矩形）Ｖを計算する（ステップＳ５７）。そして、この計算したＶと問い合わせ点との最小距離Ｄを算出し（ステップＳ５９）、この距離Ｄを第１、第２リストのｋ近傍距離と比較し、距離Ｄが第１リストのｋ近傍距離以下であり、かつ第２リストのｋ近傍距離以下であるか否かを判定する（ステップＳ６１）。
【００５０】
この判定の結果、距離Ｄが第１リストのｋ近傍距離以下であり、かつ第２リストのｋ近傍距離以下である場合に限り、ノードＮのｉ番目のエントリに格納されている子ポインタ、距離Ｄをキューに格納する（ステップＳ６３）。以上のループ２の処理をノードに格納されている全エントリに対して行い、ループ２が終了すると、キューの先頭データを削除して、データを前詰めし、キュー内のデータを距離の昇順にソートし（ステップＳ６７）、図３の処理Ａから図２に示すステップＳ３９に戻って、ループ１の処理をキューが空きになるまで繰り返し行う。
【００５１】
次に、図４に示す処理Ｂでは、まずパラメータｉが０に設定され（ステップＳ８１）、以下に続くステップＳ８３からＳ１０１までのループ３で示す処理をパラメータｉが前記エントリ数ｅｎｔ以上になるまで繰り返し実行する。ループ３では、まず前記パラメータｉを＋１インクリメントし（ステップＳ８５）、ノードＮにおいてｉ番目のエントリとして格納している部分空間符号と現ノードの矩形Ｒから子ノードの相対セルＣを計算する（ステップＳ８７）。そして、この計算した相対セルＣと問い合わせ点との最小距離Ｄを算出し（ステップＳ８９）、この距離Ｄを第１、第２リストのｋ近傍距離と比較し、距離Ｄが第１リストのｋ近傍距離以下であり、かつ第２リストのｋ近傍距離以下であるか否かを判定する（ステップＳ９０）。
【００５２】
この判定の結果、距離Ｄが第１リストのｋ近傍距離以下であり、かつ第２リストのｋ近傍距離以下である場合、ノードＮのｉ番目のエントリに格納されている子ポインタ、エントリ番号ｉ、距離Ｄをキューに格納しソートする（ステップＳ９１）。
【００５３】
次に、前記計算した相対セルＣと問い合わせ点との最大距離であるＤmaxを計 算する（ステップＳ９３）。この計算した最大距離Ｄmaxが第２リストのｋ近傍 距離未満であるか否かを判定し（ステップＳ９５）、最大距離Ｄmaxが第２リス トのｋ近傍距離未満である場合には、最大距離Ｄmaxを第２リストに格納し、ソ ートする（ステップＳ９７）。それから、第２リストを用いて、キューのフィルタリングを行う（ステップＳ９９）。このフィルタリングでは、第２リストに格納されている候補オブジェクトを用いて、キューの中でアクセスする必要のないデータを削除し、これによりキューのデータ量を削減する。以上のループ３の処理をノードに格納されている全エントリに対して行い、ループ２が終了すると、キューの先頭データを削除して、データを前詰めし、キュー内のデータを距離の昇順にソートし（ステップＳ６７）、図４の処理Ｂから図２に示すステップＳ３９に戻って、ループ１の処理をキューが空きになるまで繰り返し行う。
【００５４】
このようにしてループ１の処理をキューが空きになるまで繰り返し実行し、ループ１の処理が終了すると、第１リストに格納されている候補オブジェクトを最終的な近傍オブジェクトとして出力する（ステップＳ４１）。
【００５５】
上述した多次元空間データ更新処理および多次元空間データ探索処理は、図５（ａ）に示すようにＣＰＵ１、メモリ３、Ｉ／Ｏ５、入力手段７、表示手段９、外部記憶手段１１からなる計算機のメモリ３または外部記憶手段１１に記憶された多次元空間データ更新プログラムおよび多次元空間データ探索プログラムをＣＰＵ１で実行することにより達成される。
【００５６】
更に詳しくは、図５（ａ）に示す計算機は、前記多次元空間データ更新プログラムおよび多次元空間データ探索プログラムおよびＣＰＵ１によりソフトウェア機能として構成される図５（ｂ）に示すように索引更新処理部２１および探索処理部２３を有し、索引更新処理部２１がメモリ３内に構成される索引記憶部２５にアクセスして索引記憶部２５の内部に格納されている索引を更新し、また探索処理部２３が索引記憶部２５にアクセスしながら探索を実施するようになっている。
【００５７】
ここで、探索アルゴリズムを例として、図１（ａ）を用いて説明する。Ｒの矩形位置とＶ１とＶ２の部分空間符号によって、Ｖ１とＶ２を求め、ＶＢＲと問い合わせ点との距離を計算し、キューに格納する。Ｖ１が枝刈り対象にならなかった場合、同様にＭ１の位置とＶ３とＶ４の部分空間符号によってＶ３とＶ４を求め、ＶＢＲと問い合わせ点との距離を計算する。計算によって求めた距離をキューに格納する。Ｖ３が枝刈り対象にならなかった場合、Ｍ３の位置とＣ１とＣ２の部分空間符号によって、Ｃ１とＣ２を計算する。計算によって求めた相対セルと問い合わせ点との距離をキューに格納する。また、問い合わせ点とＣ１間の最大距離、および問い合わせ点とＣ２間の最大距離は第２リストに格納され、キューのフィルタリングが行われる。そして、Ｃ１が枝刈り対象にならなかった場合、Ｐ１にアクセスする。
【００５８】
次に、本発明の多次元空間データ探索方法による探索時間を調査した実験結果について図６を参照して説明する。この実験における本発明に対する比較対象として既存手法のＳＲ−ｔｒｅｅ，ＶＡ−Ｆｉｌｅを用いた。このＳＲ−ｔｒｅｅ，ＶＡ−Ｆｉｌｅは、高次元空間探索において優れた手法である。実験条件として、オブジェクトデータは画像の色相ヒストグラムに基づく点データを用い、データ集合サイズは１００，０００件、探索数は２０である。空間次元数は４次元から６４次元まで変化させた。ディスクページは８ＫＢ（８１９２ｂｙｔｅ）を基にした。
【００５９】
図６（ａ）からわかるように、Ａ−ｔｒｅｅは、探索コストに関して全次元数においてＶＡ−ＦｉｌｅおよびＳＲ−ｔｒｅｅよりも優れている。具体的には、１００，０００件、６４次元の場合において、ＶＡ−Ｆｉｌｅに対して７７．７％のディスクアクセスの削減を達成し、またＳＲ−ｔｒｅｅに対して７７．３％のディスクアクセスの削減を達成している。ＶＲ−ｔｒｅｅとは同等の性能を示している。
【００６０】
また、図６（ｂ）からわかるように、索引の更新コストについては、ＶＲ−ｔｒｅｅよりもコストを低減している。具体的には、１００，０００件、６４次元の場合において、ＶＲ−ｔｒｅｅに対して６８．２％のディスクアクセスの削減を達成している。
【００６１】
なお、上記実施形態の空間探索方法および索引更新方法の処理手順をプログラムとして記録媒体に記録して、この記録媒体をコンピュータシステムに組み込むとともに、該記録媒体に記録されたプログラムをコンピュータシステムにダウンロードまたはインストールし、該プログラムでコンピュータシステムを作動させることにより、空間探索方法および索引更新方法を実施するシステムとして機能させることができることは勿論であり、このような記録媒体を用いることにより、その流通性を高めることができるものである。
【００６２】
【発明の効果】
以上説明したように、本発明によれば、高次元空間探索において少ない時間でオブジェクトを検出することが可能となり、高い探索性能を実現することができる。また、データオブジェクトの挿入や削減に伴う索引の更新を低コストで実施することができる。更に、本発明は多次元空間データとして表現することができる画像、映像、音声、文書等を対象とする広範囲な情報検索に適用することが可能である。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る多次元空間データ構造であるＡ−ｔｒｅｅの構造の一例を示す図である。
【図２】本発明の他の実施形態に係る多次元空間データ探索方法の作用を示すフローチャートである。
【図３】図２に示すフローチャートにおけるステップＳ３５の処理Ａの手順を示すフローチャートである。
【図４】図２に示すフローチャートにおけるステップＳ３７の処理Ｂの手順を示すフローチャートである。
【図５】本発明の実施形態である多次元空間データ更新処理および多次元空間データ探索処理を実施するシステム構成を示す図である。
【図６】本発明の多次元空間データ探索方法による探索時間を調査した実験結果を従来技術と比較して示すグラフである。
【図７】従来技術におけるＳＲ−ｔｒｅｅの構造を示す図である。
【図８】従来技術における部分空間符号の計算方法を示す図である。
【図９】従来技術におけるＶＲ−ｔｒｅｅの構造を示す図である。
【図１０】従来技術におけるＶＲ−ｔｒｅｅの更新処理を説明するための図である。
【符号の説明】
１  ＣＰＵ
３  メモリ
１１  外部記憶手段
２１  索引更新処理部
２３  探索処理部
２５  探索記憶部
Ｃ１，Ｃ２  相対セル
Ｍ１，Ｍ２，Ｍ３，Ｍ４  ＭＢＲ（最小包囲矩形）
Ｐ１，Ｐ２  データオブジェクト
Ｖ１，Ｖ２，Ｖ３，Ｖ４  ＶＢＲ（仮想包囲矩形）
【図１】
0003708809.tif 000002
【図２】
0003708809.tif 000003
【図３】
0003708809.tif 000004
【図４】
0003708809.tif 000005
【図５】
0003708809.tif 000006
【図６】
0003708809.tif 000007
【図７】
0003708809.tif 000008
【図８】
0003708809.tif 000009
【図９】
0003708809.tif 000010
【図１０】
0003708809.tif 000011