ヒルベルト R 木

R ツリーのバリエーションであるヒルベルト R ツリーは、線、領域、3D オブジェクト、高次元フィーチャベースのパラメトリック オブジェクトなどの多次元オブジェクトのインデックスです。多次元オブジェクト用の B+ ツリーの拡張と考えることができます。

R ツリーのパフォーマンスは、ノード上のデータ長方形をクラスタ化するアルゴリズムの品質に依存します。ヒルベルト R ツリーは、空間充填曲線、具体的にはヒルベルト曲線を使用して、データ長方形に線形順序付けを適用します。

ヒルベルト R ツリーには、静的データベース用と動的データベース用の 2 種類があります。どちらの場合も、ヒルベルト空間充填曲線を使用して、ノード内の多次元オブジェクトの順序付けを改善します。この順序付けは、「類似した」データ長方形をグループ化して、結果として得られる最小境界長方形 ( MBR ) の面積と周囲を最小化するという意味で「適切」である必要があります。パックされたヒルベルト R ツリーは、更新が非常にまれであるか、まったく更新されない静的データベースに適しています。

動的ヒルベルト R ツリーは、挿入、削除、または更新がリアルタイムで発生する可能性がある動的データベースに適しています。さらに、動的ヒルベルト R ツリーは、柔軟な遅延分割メカニズムを使用して、スペース利用率を高めます。すべてのノードには、明確に定義された兄弟ノードのセットがあります。これは、R ツリー ノードの順序付けを提案することによって行われます。ヒルベルト R ツリーは、長方形の中心のヒルベルト値 (つまり、MBR) に従って長方形をソートします。(ポイントのヒルベルト値は、原点からポイントまでのヒルベルト曲線の長さです。) 順序付けが与えられると、すべてのノードには明確に定義された兄弟ノードのセットがあるため、遅延分割を使用できます。分割ポリシーを調整することで、ヒルベルト R ツリーは、必要なだけ高いスペース利用率を実現できます。逆に、他の R ツリー バリアントは、スペース利用率を制御できません。

次の例は静的環境用ですが、適切な R ツリー設計の直感的な原則を説明しています。これらの原則は、静的データベースと動的データベースの両方に有効です。

Roussopoulos と Leifker は、ほぼ 100% のスペース利用率を実現するパックされた R ツリーを構築する方法を提案しました。その考え方は、長方形の角の 1 つである x または y 座標でデータをソートすることです。4 つの座標のいずれかでソートすると、同様の結果が得られます。この議論では、ポイントまたは長方形は長方形の左下隅の x 座標でソートされ、「lowx パックされた R ツリー」と呼ばれます。ソートされた長方形のリストがスキャンされ、そのノードがいっぱいになるまで、連続する長方形が同じ R ツリーのリーフ ノードに割り当てられます。その後、新しいリーフ ノードが作成され、ソートされたリストのスキャンが続行されます。したがって、結果の R ツリーのノードは、各レベルの最後のノードを除いて完全にパックされます。これにより、スペース利用率は ≈100% になります。ツリーの上位レベルも同様の方法で作成されます。

図 1 は、lowx パック R ツリーの問題を強調しています。図 1 [右] は、lowx パッキング メソッドが図 1 [左] のポイントに対して作成する R ツリーのリーフ ノードを示しています。結果として得られる父ノードがカバーする領域が小さいという事実は、lowx パック R ツリーがポイント クエリで優れたパフォーマンスを実現する理由を説明しています。ただし、父ノードの周囲が広いという事実は、領域クエリのパフォーマンスの低下を説明しています。これは、R ツリーのパフォーマンスの解析式と一致しています。^[1]直感的には、パッキング アルゴリズムは、理想的には近くのポイントを同じリーフ ノードに割り当てる必要があります。lowx パック R ツリーが y 座標を無視すると、この経験則に違反する傾向があります。

図 1: [左] 均一に分布した 200 個のポイント、[右] 「lowx パック R ツリー」アルゴリズムによって生成されたノードの MBR

以下のセクションでは、ヒルベルト R ツリーの 2 つのバリエーションについて説明します。最初のインデックスは、更新が非常にまれであるか、まったく更新されない静的データベースに適しています。結果の R ツリーのノードは、各レベルの最後のノードを除いて完全にパックされます。したがって、スペース使用率は ≈100% です。この構造はパックされたヒルベルト R ツリーと呼ばれます。2 番目のインデックスは動的ヒルベルト R ツリーと呼ばれ、挿入と削除をサポートし、動的環境に適しています。

以下ではヒルベルト曲線について簡単に紹介します。2x2 グリッド上の基本ヒルベルト曲線 (H ₁で表示)を図 2 に示します。i 次数の曲線を導出するには、基本曲線の各頂点を i – 1 次数の曲線に置き換えます。この曲線は、適切に回転および/または反転させることができます。図 2 には、2 次および 3 次数のヒルベルト曲線も示されています。曲線の次数が無限大に近づくと、他の空間充填曲線と同様に、結果として得られる曲線はフラクタルになり、フラクタル次元は 2 になります。^{[1] [2]ヒルベルト曲線は、より高次元に一般化できます。特定の次数の 2 次元曲線を描画するアルゴリズムは、[3]}および^[2]に記載されています。高次元のアルゴリズムは、^{[4]に記載されています。}

空間充填曲線のパスは、グリッド ポイントに線形順序を課します。このパスは、曲線の一方の端から始めて、パスをもう一方の端までたどることで計算できます。各ポイントの実際の座標値を計算できます。ただし、ヒルベルト曲線の場合、これはZ 順序曲線などよりもはるかに困難です。図 2 は、4x4 グリッドのそのような順序の 1 つを示しています (曲線 H _{2を参照)。たとえば、H 2}曲線上のポイント (0,0)のヒルベルト値は 0 ですが、ポイント (1,1) のヒルベルト値は 2 です。長方形のヒルベルト値は、その中心のヒルベルト値として定義されます。

図2: 1次、2次、3次のヒルベルト曲線

ヒルベルト曲線は、データ長方形に線形順序を課し、ソートされたリストをトラバースして、C 長方形の各セットを R ツリーのノードに割り当てます。最終結果として、同じノード上のデータ長方形のセットは、線形順序で互いに近くなり、ネイティブ空間でもよく近くなります。したがって、結果として得られる R ツリー ノードの領域は小さくなります。図 2 は、ヒルベルト ベースの方法で優れたパフォーマンスが得られる直感的な理由を示しています。データはポイント (図 1 に示されているのと同じポイント) で構成されています。ポイントをヒルベルト値に従ってグループ化すると、結果として得られる R ツリー ノードの MBR は、小さな正方形のような長方形になる傾向があります。これは、ノードの領域と周囲が小さくなる可能性が高いことを示しています。面積値が小さいと、ポイント クエリのパフォーマンスが良好になり、面積値と周囲が小さいと、大規模なクエリのパフォーマンスが良好になります。

(長方形を R ツリーにパックします)
ステップ 1. 各データ長方形のヒルベルト値を計算します
ステップ 2. ヒルベルト値の昇順でデータ長方形をソートします
ステップ 3. /* リーフ ノードを作成します (レベル l=0) */

• （長方形は他にもたくさんあります）
  • 新しいRツリーノードを生成する
  • 次のCの長方形をこのノードに割り当てる

ステップ 4. /* 上位レベル (l + 1) のノードを作成する */

• 一方（レベルlには1以上のノードがある）
  • レベル l ≥ 0 のノードを作成時刻の昇順でソートする
  • ステップ3を繰り返す

ここでの前提は、データが静的であるか、変更頻度が低いということです。これは、約 100% のスペース使用率で、同時に応答時間が良好な R ツリーを構築するための単純なヒューリスティックです。

R ツリーのパフォーマンスは、ノード上のデータ長方形をクラスタ化するアルゴリズムの品質に依存します。ヒルベルト R ツリーは、空間充填曲線、具体的にはヒルベルト曲線を使用して、データ長方形に線形順序付けを適用します。長方形のヒルベルト値は、その中心のヒルベルト値として定義されます。

ヒルベルトRツリーの構造は次のようになります。リーフノードには、最大でC _{l 個の}エントリが含まれます。各エントリの形式は(R, obj _id)で、C _lはリーフの容量、Rは実オブジェクトのMBR(x _low、x _high、y _low、y _high )、obj-idはオブジェクト記述レコードへのポインタです。ヒルベルトRツリーとR*ツリー^[5]の主な違いは、リーフ以外のノードにもLHV(最大ヒルベルト値)に関する情報が含まれていることです。したがって、ヒルベルト R ツリーの非リーフ ノードには、最大で(R, ptr, LHV) 形式のC _{nエントリが含まれます。ここで、C n}は非リーフ ノードの容量、R はそのノードのすべての子ノードを囲む MBR、ptr は子ノードへのポインタ、LHV は R で囲まれたデータ長方形の中で最大のヒルベルト値です。非リーフ ノードは、子ノードのヒルベルト値の 1 つを自身の LHV の値として選択するため、非リーフ ノードの MBR のヒルベルト値を計算するのに追加のコストはかからないことに注意してください。図 3 は、ヒルベルト R ツリーで編成された長方形をいくつか示しています。中心のヒルベルト値は、"x" 記号の近くの数字です (親ノード "II" についてのみ表示)。LHV は [かっこ] 内にあります。図 4 は、図 3 のツリーがディスクにどのように格納されるかを示しています。親ノード "II" の内容は、より詳細に示されています。ノード「I」内のすべてのデータ長方形のヒルベルト値は v ≤33 です。同様に、ノード「II」内のすべての長方形のヒルベルト値は 33 より大きく ≤ 107 です。

図 3: ヒルベルト R ツリーに整理されたデータ長方形 (ヒルベルト値と最大ヒルベルト値 (LHV) は括弧内に表示されます)

プレーン R ツリーは、オーバーフロー時にノードを分割し、元のノードから 2 つのノードを作成します。このポリシーは、1 対 2 分割ポリシーと呼ばれます。また、2 つのノードが 3 つに分割されるまで待って、分割を延期することもできます。これは、B* ツリー分割ポリシーに似ていることに注意してください。この方法は、2 対 3 分割ポリシーと呼ばれます。

一般的に、これは s から (s+1) への分割ポリシーに拡張できます。ここで、s は分割ポリシーの順序です。順序 s の分割ポリシーを実装するには、オーバーフローしたノードはエントリの一部を s - 1 個の兄弟の 1 つにプッシュしようとします。すべてがいっぱいの場合は、s から (s+1) への分割を行う必要があります。s -1 個の兄弟は、協調兄弟と呼ばれます。

次に、検索、挿入、オーバーフロー処理のアルゴリズムについて詳しく説明します。

検索アルゴリズムは、他の R ツリー バリアントで使用されるアルゴリズムに似ています。ルートから開始してツリーを下り、クエリ矩形と交差するすべてのノードを調べます。リーフ レベルでは、クエリ ウィンドウ w と交差するすべてのエントリを、修飾されたデータ項目として報告します。

アルゴリズム検索(ノード ルート、矩形 w):
S1. 非リーフノードを検索:

MBR がクエリ ウィンドウ w と交差するすべてのエントリの検索を呼び出します。

S2. リーフノードを検索:

クエリウィンドウ w と交差するすべてのエントリを候補として報告します。

図4: ヒルベルトRツリーのファイル構造

ヒルベルト R ツリーに新しい四角形 r を挿入するには、新しい四角形の中心のヒルベルト値 h がキーとして使用されます。各レベルで、すべての兄弟ノードの h より大きい最小の LHV 値を持つノードが選択されます。リーフ ノードに到達すると、四角形 r は h に従って正しい順序で挿入されます。新しい四角形がリーフ ノード N に挿入された後、AdjustTreeが呼び出され、上位レベルのノードの MBR と最大ヒルベルト値が修正されます。

アルゴリズム Insert(node Root, rect r): /* ヒルベルト R ツリーに新しい四角形 r を挿入します。h は四角形のヒルベルト値です。*/
I1. 適切なリーフ ノードを検索します。

ChooseLeaf(r, h) を呼び出して、r を配置するリーフ ノード L を選択します。

I2. リーフノードLにrを挿入する:

Lに空きスロットがある場合は、Lにrを挿入します。

ヒルベルト順序に従って適切な場所に配置し、戻ります。

Lがいっぱいの場合はHandleOverflow(L,r)を呼び出します。

分裂が避けられない場合は新しい葉を戻すだろう。

I3. 変更を上方に伝播する:

Lとその協力する兄弟を含む集合Sを形成する

そして新しい葉（もしあれば）

AdjustTree(S) を呼び出します。

I4. 木を高く育てる:

ノード分割の伝播によりルートが分割された場合は、

結果として得られる 2 つのノードを子とする新しいルート。

アルゴリズム ChooseLeaf(rect r, int h):
/* 新しい四角形 r を配置するリーフ ノードを返します。 */
C1. 初期化:

N をルート ノードに設定します。

C2. リーフチェック:

N が leaf_ の場合は N を返します。

C3. サブツリーを選択:

Nが非リーフノードの場合は、エントリ(R、ptr、LHV)を選択します。

最小 LHV 値が h より大きい。

C4. 葉に到達するまで下降します。

ptr が指すノードに N を設定し、C2 から繰り返します。

アルゴリズム AdjustTree(set S):
/* S は、更新されるノード、その協調する兄弟ノード (オーバーフローが発生した場合)、および新しく
作成されたノード NN (分割が発生した場合) を含むノードのセットです。ルーチンは、リーフ レベルからルートに向かって上昇し、S 内のノードをカバーするノードの MBR と LHV を調整します。分割がある場合は、それを伝播します */
A1. ルート レベルに達したら、停止します。A2
. ノードの分割を上方に伝播します。

Np を N の親ノードとします。

N が分割されている場合は、NN を新しいノードとします。

NNをヒルベルトに従って正しい順序でNpに挿入します。

余裕がある場合は値を返します。そうでない場合は、HandleOverflow(Np,NN) を呼び出します。

Np が分割された場合、PP を新しいノードにします。

A3. 親レベルの MBR と LHV を調整します。

P を S 内のノードの親ノードの集合とします。

P 内のノードの対応する MBR と LHV を適切に調整します。

A4. 次のレベルに進みます:

Sを親ノードPの集合とし、

Np が分割された場合、NN = PP になります。

A1から繰り返します。

ヒルベルト R ツリーでは、親ノードがアンダーフローするたびに孤立ノードを再挿入する必要はありません。代わりに、兄弟からキーを借りるか、アンダーフローするノードをその兄弟とマージすることができます。これは、ノードが明確な順序付け (最大ヒルベルト値 (LHV) に従って) を持っているために可能になります。対照的に、R ツリーでは兄弟ノードに関するそのような概念はありません。削除操作には s 個の協調する兄弟が必要であり、挿入操作には s - 1 個の兄弟が必要であることに注意してください。

アルゴリズム削除(r):
D1. ホストリーフを見つける:

完全一致検索を実行して、リーフノードLを見つけます。

r を含む。

D2. rを削除します:

ノードLからrを削除します。

D3. Lがアンダーフローした場合

協力的な兄弟からいくつかのエントリを借ります。

すべての兄弟がアンダーフローする準備ができている場合。

s + 1 を s ノードにマージし、

結果のノードを調整します。

D4. 親レベルの MBR と LHV を調整します。

Lとその協力者を含む集合Sを形成する

兄弟（アンダーフローが発生した場合）。

AdjustTree(S) を呼び出します。

ヒルベルト R ツリーのオーバーフロー処理アルゴリズムは、エントリの一部を s - 1 個の協調兄弟の 1 つに移動するか、s 個のノードを s +1 個のノードに分割することによって、オーバーフローしたノードを処理します。

アルゴリズムHandleOverflow(node N, rect r):
/* 分割が発生した場合は新しいノードを返します。 */
H1. εをNのすべてのエントリを含むセットとします。

およびその S - 1 協力兄弟。

H2. εにrを加える
。H3. s-1個の協力兄弟のうち少なくとも1つが完全でない場合、

ヒルベルト値に従って ε を s ノード間で均等に分配します。

H4. 協力する兄弟姉妹がすべて満員の場合、

新しいノードNNを作成し、

εをs + 1個のノードに均等に分配する。

ヒルベルト値に

NNを返します。

ウィキメディア・コモンズには、ヒルベルト R 木に関連するメディアがあります。

• I. Kamel および C. Faloutsos、「Parallel R-Trees」。ACM SIGMOD Conf. の Proc.、195 ～ 204 ページ、カリフォルニア州サンディエゴ、1992 年 6 月。Tech. Report UMIACS TR 92-1、CS-TR-2820 としても入手可能。
• I. Kamel および C. Faloutsos。ヒルベルト R ツリー: フラクタルを使用した改良型 R ツリー。VLDB Conf. の Proc.、500 ～ 509 ページ、チリ、サンティアゴ、1994 年 9 月。Tech_Report UMIACS TR 93-12.1 CS-TR-3032.1 としても入手可能。
• N. Koudas、C. Faloutsos、I. Kamel。「マルチコンピュータ アーキテクチャでの空間データベースのデクラスタリング」、International Conference on Extending Database Technology (EDBT)、592 ～ 614 ページ、1996 年。
• N. Roussopoulos と D. Leifker。Packed R-trees を使用した画像データベースの直接空間検索。ACM SIGMOD 論文集、17 ～ 31 ページ、テキサス州オースティン、1985 年 5 月。
• M. シュローダー。フラクタル、カオス、べき乗則: 無限の楽園からのほんの数分。WH フリーマン アンド カンパニー、ニューヨーク、1991 年。
• T. Sellis、N. Roussopoulos、C. Faloutsos。「R+-Tree: 多次元オブジェクトの動的インデックス」。第 13 回国際 VLDB 会議議事録、507 ～ 518 ページ、イギリス、1987 年 9 月。