ヒルベルトR木（Hilbert R-tree）とは？多次元空間インデックスの基本原理とHilbert-Packアルゴリズム

ヒルベルトR木（Hilbert R-tree）は、R木の変種の一つであり、線分、領域、3次元オブジェクト、あるいは高次元の特徴量に基づくパラメトリックなオブジェクトなど、多次元オブジェクトに対するインデックスとして定義されています。概念的には、B+木を多次元オブジェクト向けに拡張したものと捉えることができます。

R木の性能は、ノードに格納するデータ矩形をどの程度うまくクラスタリングできるかに大きく依存します。ヒルベルトR木では、空間充填曲線、特にヒルベルト曲線を用いてデータ矩形群に一次元的な順序付けを施すことで、この課題に取り組んでいます。

ヒルベルトR木には、静的データベース向けと動的データベース向けの2種類があります。いずれの場合も、ヒルベルトの空間充填曲線を利用することで、ノード内の多次元オブジェクトにより良い順序を持たせます。ここでいう「良い」順序とは、「類似した」データ矩形同士をグループ化し、結果として得られる最小外接矩形（MBR：Minimum Bounding Rectangle）の面積と周囲長を小さく抑えられるような順序を指します。パック型ヒルベルトR木は、更新がほとんど発生しないか、まったく行われない静的データベースにおいて特に有用です。

基本的な考え方

以下の例は静的な環境を想定したものですが、優れたR木設計のための直感的な原則を示しており、これらの原則は静的・動的の両方のデータベースに適用できます。

RoussopoulosとLeifkerは、空間利用率ほぼ100%を実現するパック型R木を構築する手法を提案しました。

そのアイデアは、矩形の四隅のうちいずれか一角のx座標またはy座標に基づいてデータをソートするというものです。四つの座標のどれでソートしても結果は同じになります。本稿では説明を簡単にするため、矩形（または点）を左下隅のx座標でソートする方式を「lowxパック型R木」と呼びます。ソート済みの矩形リストを走査し、連続する矩形を同じR木のリーフノードに割り当てていき、そのノードが満杯になった時点で新しいリーフノードを作成し、走査を継続します。こうして構築されたR木のノードは、各レベルの最後のノードを除いてすべて満杯に詰め込まれるため、空間利用率は約100%となります。より上位のレベルについても、同様の手順で構築していきます。

アルゴリズム Hilbert-Pack

（矩形をR木へパッキングする手順）

ステップ1. 各データ矩形のヒルベルト値を計算します。

ステップ2. データ矩形をヒルベルト値の昇順にソートします。

ステップ3. /* リーフノードの作成（レベル l = 0） */

• まだ処理すべき矩形が残っている間、
• 新規のR木ノードを生成し、
• 次のC個の矩形をそのノードに割り当てます。

ステップ4. /* より上位レベルのノード作成（レベル l + 1） */

• レベル l のノード数が1より大きい間、
• レベル l ≥ 0 のノードを生成時刻の昇順にソートし、
• ステップ3を繰り返します。

ここでの前提は、データが静的であるか、変更の頻度が低いということです。これは、空間利用率約100%を達成しつつ、良好な応答時間を維持できるR木を構築するための、シンプルで効果的な発見的手法と言えます。