多次元二分探索木(k-d木)とは?基本概念と構築アルゴリズムを解説

k-d木(多次元二分探索木)の基本概念

多次元二分探索木(略してk-d木)は、複数のキーを持つレコードを格納するためのデータ構造として定義されます。この構造は、統計学やデータ分析において数多くの「幾何学的」問題を解決するために実装されてきました。

k-d木(k-dimensional tree の略)は、k次元空間内の点を整理するための空間分割データ構造です。k-d木は、多次元検索キーを用いた検索(例えば範囲検索や最近傍探索)など、さまざまな用途に活用されています。また、k-d木は二分空間分割木(BSP木)の特殊なケースとして扱われます。

非形式的な説明:k-d木の仕組み

k-d木は、すべての葉ノードがk次元の点として扱われる二分木です。各非葉ノードは、空間を「半空間」と呼ばれる2つの領域に分割する分割超平面(中央値として使用)を暗黙的に生成していると考えることができます。

この超平面の左側にある点はそのノードの左部分木で処理され、右側にある点は右部分木で処理されます。超平面の方向は次のように決定します。木の中の各ノードはk個の次元のいずれか1つに関連付けられ、その次元の軸に垂直な超平面とともに扱われます。

例えば、ある特定の分割で「x」軸が選択された場合を考えてみましょう。このとき、ノードよりも小さい「x」値を持つ点はすべて左部分木に配置され、「x」値が大きい点はすべて右部分木に配置されます。このケースでは、超平面はその点のx値によって設定され、その法線ベクトルは単位x軸方向を示します。

実務ではよく使われる手法として、ランダムに選択した固定数の点をソートし、それらの中央値を分割平面として採用する方法があります。

バランスの取れたk-d木を構築するアルゴリズム

n個の点からなるリストが与えられたとき、以下のアルゴリズムは中央値探索ソートを利用して、それらの点を含むバランスの取れたk-d木を構築します。

function KDtree (list of points PointList, int Depth) {
   // Choose axis based on Depth so that axis cycles through all valid values
   var int axis := Depth mod k;
   // Sort point list and select median as pivot element
   choose median by axis from PointList;
   // Node is created as node1 and construct subtree
   node1.location := median;
   node1.leftChild := KDtree(points in PointList before median, Depth+1);
   node1.rightChild := KDtree(points in PointList after median, Depth+1);
   return node1;
}

このアルゴリズムでは、再帰の深さ(Depth)に基づいて軸を選択し、すべての有効な次元が順番に巡回するように設計されています。各ステップで点のリストを軸に沿ってソートし、中央値をピボット要素として採用することで、左右の部分木にデータが均等に分配され、結果としてバランスの良い木構造が得られます。