Kd-Tree
kd木（k次元木、Bentley 1975）は、上の点に対する二分空間分割構造であり、最近傍問い合わせを平均的に準線形にする。これは、低次元の幾何データ——何よりも3D点群——において「最も近い点を見つける」という問いに対する標準的な解答であり、ランダム化フォレスト形式においては高次元の浮動小数点記述子の近似マッチングにも実用的なツールとなる。
構築
各内部ノードは、軸に沿った超平面で点集合を分割する。
- 分割次元を選ぶ——古典的には深さに応じて次元を巡回させる（）か、より良くはノード内の点の分散・広がりが最大の次元を選ぶ。
- 分割値を選ぶ——典型的には座標の中央値であり、これは深さ のバランスの取れた木を保証する。
- ノードが持つ点の数がリーフサイズの閾値未満になるまで、両半分に対して再帰する。
構築コストは、中央値のメディアンまたは事前ソートを用いて である。木は各点を1回ずつ保持する。
最近傍探索
クエリ はまずそれを含むリーフに降りていき（回の比較）、そこで見つかった最良の点を距離 の現在の候補とする。その後、探索はバックトラックする。上へ戻る途中の各ノードで、分割平面が現在の最良候補より近い場合、すなわち
（ここで はノードの分割次元 におけるクエリの座標、 は分割値である）の場合にのみ、もう一方の部分木を訪れる必要がある——幾何的には、を中心とする半径 の超球が分割平面と交差する場合にのみである。そうでなければ、その部分木全体は刈り取られる。同じ仕組みでk最近傍問い合わせ（最良の個のヒープを保持する）や半径探索も得られる。
低次元（）では刈り取りが効果的であり、平均的な問い合わせコストは となる。
次元の呪い
が大きくなるにつれて距離は集中し——最近傍と最遠傍の距離が相対的に似通ってくる——刈り取りの球はほぼすべての分割平面と交差するようになり、探索は木の走査オーバーヘッドを払いながら完全な線形スキャンへと退化していく。目安として、厳密なkd木探索がブルートフォースに勝つには が必要であり、SIFTの128次元は厳密探索の適用範囲を遥かに超えている。2つの対策が現代の実務を定義している。
- Best-bin-first（BBF）（Beis & Lowe, 1997）：優先度キューを用いてクエリへの距離順にノードを探索し、固定された予算のリーフ検査後に停止し、見つかった最良の候補を返す。これはkd木を、精度/速度を調整可能なダイヤルを持つ近似手法に変える——まさにSIFTマッチングのために導入された。
- ランダム化kd木フォレスト：（上位分散の次元の中から）分割次元をランダムに選んだ複数の木を構築し、1つの共有優先度キューを通じて探索する。ある木の悪い分割の裏に「隠れた」近傍点は、別の木を通じて見つかる。これはFLANNの中核インデックスの一つである。
kd木は生のベクトルをL2の下で比較することに注意すること——ハミング距離の下でのバイナリ記述子には、LSHやHBSTが適切な構造である。
SLAMにおけるkd木の出現場所
- ICPと点群レジストレーション：対応点探索ステップ——各シーン点に対する最も近いモデル点を、各反復で——は3D最近傍問い合わせのバッチである。PCL、Open3D、libpointmatcherはすべてkd木を使用する（FAST-LIO2は、地図が成長するにつれての再構築を避けるため、増分更新可能な変種であるikd-Treeを構築する）。
- 記述子マッチング：SfMや再位置推定パイプラインにおけるSIFT/SuperPoint風記述子に対する近似最近傍（FLANN経由）。
- 地図問い合わせ：局所地図抽出のための半径探索、法線推定の近傍、キーフレーム位置の検索、メッシュ/サーフェル近傍探索。
SLAMにおける意義
最近傍探索は、SLAMシステムにおいて最も頻繁に実行される基本演算の一つである——LiDARやRGB-Dパイプラインの各ICP反復の内部、特徴点パイプラインの各マッチング段階の内部、法線推定やダウンサンプリングのようなマッピング演算の内部。kd木の仕組みを知ることで、それがいつ正しいツールなのか（3D点：非常に優れている、128次元記述子：近似/フォレスト形式でのみ、バイナリ記述子：間違ったツール）がわかり、その上に構築されたライブラリの設計（FLANNのインデックス、PCLの探索モジュール、ikd-Tree）も理解できるようになる。また、これは繰り返し現れるシステムのボトルネックでもある。成長する地図に対する再構築か更新かの戦略は、リアルタイムLiDARオドメトリのアーキテクチャを直接形作る。