Kd木

kd木とは

kd木（k-dimensional tree）は、k次元のユークリッド空間における点を分類するための空間分割データ構造です。このデータ構造は、多次元の探索キーを用いた検索、特に範囲検索や最近傍探索といった用途で非常に有効です。kd木は、より一般的な空間分割データ構造であるBSP木（Binary Space Partitioning tree）の特殊なケースであり、分割面が座標軸のいずれかに垂直な平面に限定される点が特徴です。

kd木とBSP木の違い

• - 分割平面: kd木では、分割平面は常に座標軸に垂直ですが、BSP木では分割平面の角度は任意です。
• - ノードのデータ: kd木では、根ノードから葉ノードまでの各ノードに点が格納されます。一方、BSP木では、一般的に葉ノードのみが点やその他の幾何学的プリミティブを格納します。つまり、kd木の各分割平面は必ず1つの点を通過します。
• - kdトライ: kd木の派生データ構造として、葉ノードのみがデータを格納するkdトライがあります。

また、kd木の別の定義として、各分割平面が点を通るように決定されるが、点を葉ノードでのみ記憶するというものもあります。

kd木の構築

kd木の構築方法はいくつか存在しますが、一般的な方法は以下の通りです。

1. 軸の選択: 木構造を下降するにつれて、分割平面を選択する軸を巡回します。例えば、根ではx軸、その子ではy軸、孫ではz軸といったように、各レベルで異なる軸を使用します。
2. 分割点の選択: 各ステップで、分割平面を生成するために選ばれる点は、その軸における全て点の座標値の中央値とします。これにより、平衡なkd木を構築することができ、根から各葉ノードまでの距離がほぼ等しくなります。

中央値の代わりに他の点を使用することも可能ですが、その場合、必ずしも平衡木となるとは限りません。中央値を選択しない場合、固定数の点をランダムに選び、それらの中央値で分割する方法も実用的です。

擬似コード

function kdtree (list of points pointList, int depth)
{
if pointList is empty
return nil;
else
{
// 深さに応じて軸を選択し、軸が順次選択されるようにする
var int axis := depth mod k;

// 点のリストをソートし、中央値の点を選択する
select median from pointList;

// ノードを作成し、部分木を構築する
var tree_node node;
node.location := median;
node.leftChild := kdtree(points in pointList before median, depth+1);
node.rightChild := kdtree(points in pointList after median, depth+1);
return node;
}
}


中央値より後ろ（after）の点には、中央値以上の座標値の点を含ませるのが一般的です。また、他の次元で点を比較する「スーパーキー」関数を使用したり、中央値に等しい点を両側に属させることもあります。

kd木の操作

要素の追加

kd木への点の追加は、他の木構造と同様に、根から走査を開始し、追加する点の座標値に応じて左右の子ノードに移ることで行います。葉ノードに到達したら、そのノードの点の座標値と比較し、左右いずれかに新しい子ノードを追加します。

要素の削除

kd木から点を削除する場合、木の構造を維持するために、削除する点を含むノード以下の部分木全体を再構築する必要がある場合があります。これにより、不変量（木の構造が持つべき性質）を保つことができます。

平衡化

kd木は多次元でソートされているため、一般的な木の回転操作を用いて平衡化することはできません。平衡化には特別な注意が必要です。

kd木での最近傍探索

最近傍探索は、与えられた点に最も近いkd木上の点を見つける問題です。kd木の特性を活かすことで、効率的な探索が可能です。

1. 初期化: まず、最短距離を無限大として、根ノードから探索を開始します。
2. 探索: 与えられた点を含む領域（超矩形）を木構造を下降しながら特定します。
3. 再帰的探索: 葉ノードに到達したら、親ノードのもう一方の領域に、より近い点が存在しないかを再帰的に調べます。この際、探索点からの距離が現在の最近傍までの距離となる超球（球）と、各領域の超矩形が重なるかどうかを判定し、重ならない場合は探索を打ち切ります。

このアルゴリズムの時間計算量はO(logN)であり、高速な探索が可能です。

近似最近傍探索

近似最近傍探索は、探索する点の個数や時間を制限することで、さらなる高速化を図る手法です。この手法は、リアルタイム性が求められるロボット工学などの分野でよく使用されます。

高次元データにおけるkd木

kd木は、高次元データにおける最近傍探索には適していない場合があります。次元をDとした場合、データの個数NがN >> 2^Dを満たさないと、探索時にほとんどの点を調べることになり、効率が低下します。高次元データにおける最近傍探索はNP困難問題に類似しており、近似最近傍探索がよく利用されます。

計算量

• - 静的なkd木の構築: 中央値探索アルゴリズムによって異なりますが、O(n log n) の計算量で構築可能です。
• - 要素の挿入/削除: 平衡kd木の場合、O(log n) の時間がかかります。
• - 範囲探索: 平衡kd木で、軸に平行な範囲にある点を求める場合、O(n^(1-1/d) + k) の時間がかかります。ここで、k は報告される点の個数、d は kd木の次元です。

派生

kd木は、点だけでなく、矩形や超矩形を格納する用途にも用いられます。矩形範囲探索では、与えられた矩形範囲と重なる全ての矩形を探索します。このとき、比較に用いる座標値は、分割軸と反対の座標値を使用します。この拡張により、区間木などの他のデータ構造を構築することもできます。

まとめ

kd木は、多次元データを効率的に管理・探索するための強力なデータ構造です。範囲探索や最近傍探索などの応用範囲が広く、様々な分野で活用されています。ただし、高次元データでは効率が低下する可能性があるため、近似最近傍探索などの他の手法と組み合わせて利用することが推奨されます。

参考文献

• - Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching.
• - Bentley, J. L. (1990). K-d Trees for Semidynamic Point Sets.
• - H. Samet (1990). The Design and Analysis of Spatial Data Structures.
• - Mark de Berg, et al. (2000). Computational Geometry.

外部リンク

• - libkdtree++ - C++で実装されたオープンソースのkd木ライブラリ

もう一度検索