ボールツリー

コンピュータサイエンスにおいて、ボールツリー、ボールツリー^[1]、またはメトリックツリーは、多次元空間内の点を整理するための空間分割 データ構造です。ボールツリーは、データポイントをネストされたボールのセットに分割します。結果として得られるデータ構造は、多くのアプリケーション、特に最近傍検索に役立つ特性を備えています。

ボール ツリーは、各ノードが検索対象のポイントのサブセットを含む D 次元のボールを定義するバイナリ ツリーです。ツリーの各内部ノードは、データ ポイントを異なるボールに関連付けられた 2 つの互いに素なセットに分割します。ボール自体は交差する場合がありますが、各ポイントは、ボールの中心からの距離に応じて、パーティション内のいずれかのボールに割り当てられます。ツリーの各リーフ ノードはボールを定義し、そのボール内のすべてのデータ ポイントを列挙します。

ツリー内の各ノードは、そのサブツリー内のすべてのデータポイントを含む最小のボールを定義します。これにより、ボールの外側の特定のテストポイントtに対して、ツリー内のボールBの任意のポイントまでの距離が、 tからボールの表面までの距離以上であるという便利な特性が生じます。正式には、次のようになります。 ^[2]

${\displaystyle D^{B}(t)={\begin{cases}\max(|t-{\textit {B.pivot}}|-{\textit {B.radius}},D^{\textit {B.parent}}),&{\text{if }}B\neq Root\\\max(|t-{\textit {B.pivot}}|-{\textit {B.radius}},0),&{\text{if }}B=Root\\\end{cases}}}$

球B内の任意の点から任意の点tまでの最短距離はどこにあるでしょうか。 ${\displaystyle D^{B}(t)}$

ボールツリーはM ツリーに関連していますが、バイナリ分割のみをサポートしています。一方、M ツリーでは各レベルが折りたたまれるように分割されるため、ツリー構造が浅くなり、距離の計算が少なくて済み、通常はクエリが高速になります。さらに、M ツリーは、ページに編成されているディスク に保存する方が適しています。M ツリーでは、クエリを高速化するために、親ノードからの距離も事前に計算されています。 ${\displaystyle m}$${\displaystyle 2m}$

ヴァンテージポイントツリーも同様ですが、2 つのボールを使用する代わりに、1 つのボールと残りのデータにバイナリ分割します。

ボールツリー構築アルゴリズムは数多く存在します。^[1]このようなアルゴリズムの目標は、平均的なケースで、望ましいタイプのクエリ (最近傍など) を効率的にサポートするツリーを作成することです。理想的なツリーの具体的な基準は、回答する質問のタイプと基礎となるデータの分布によって異なります。ただし、効率的なツリーの一般的な基準は、内部ノードの総量を最小化するものです。実際のデータセットの分布はさまざまであるため、これは困難な作業ですが、実際にはデータを適切に分割するヒューリスティックがいくつかあります。一般に、ツリー構築のコストとこの基準によって達成される効率性の間にはトレードオフがあります。 ^[2]

このセクションでは、これらのアルゴリズムの中で最も単純なものについて簡単に説明します。5つのアルゴリズムについてのより詳細な説明は、Stephen Omohundroによって行われました。^[1]

最も単純な手順は、 k -d ツリーの構築に使用されるプロセスに倣って、「k -d 構築アルゴリズム」と呼ばれます。これはオフライン アルゴリズム、つまり、データ セット全体を一度に処理するアルゴリズムです。ツリーは、データ ポイントを 2 つのセットに再帰的に分割することによってトップダウンで構築されます。分割は、ポイントが最も広く分散している単一の次元に沿って選択され、セットはその次元に沿ったすべてのポイントの中央値によって分割されます。各内部ノードの分割を見つけるには、そのノードに含まれるサンプルの数に比例した時間が必要であり、時間複雑度のアルゴリズムが生成されます。ここで、nはデータ ポイントの数です。 ${\displaystyle O(n\,\log \,n)}$

関数construct_balltreeの入力は、データポイントの配列で
    あるDです。
    出力は、構築されたボールツリーのルートであるBです。  

    1つの点が残っている場合は、D内の1つの点を含む
        葉Bを作成し、 Bを返します。そうでない場合は、cを最大広がりの次元と
        します。
         
    cを考慮して選択された中心点をpと
        するL、R を、 c次元に沿って中央値の左側と右側にある点の集合とし、
        2つの子を持つ B を作成します: 
             B .pivot 
        : = p B 
            .child1 :=construct_balltree(L),
             B .child2 :=construct_balltree(R),B .radiusをpから子の中で
        の最大距離と
            するBを返す end if関数終了
    

ボール ツリーの重要な用途は、最近傍検索クエリの高速化です。このクエリの目的は、特定のテスト ポイントに何らかの距離メトリック (ユークリッド距離など) で最も近いツリー内の k 個のポイントを見つけることです。KNS1 と呼ばれることもある単純な検索アルゴリズムは、ボール ツリーの距離特性を活用します。特に、アルゴリズムがテスト ポイントtを使用してデータ構造を検索し、これまでに遭遇したポイントの中でtに最も近いポイントp を既に見つけた場合、ボールがtからpよりも遠いサブツリーは、残りの検索では無視できます。

ボールツリーの最近傍アルゴリズムは、ルートから始めて深さ優先順にノードを調べます。検索中、アルゴリズムは、これまでに遭遇した k 個の最近傍点の最大優先キュー(多くの場合、ヒープで実装されます) (ここではQで示されます) を維持します。各ノードBでは、3 つの操作のいずれかを実行してから、最終的に更新されたバージョンの優先キューを返します。

1. テストポイントtから現在のノードBまでの距離がQ内の最も遠いポイントよりも大きい場合は、Bを無視してQを返します。
2. Bがリーフ ノードの場合、 Bに列挙されているすべてのポイントをスキャンし、最も近い隣接キューを適切に更新します。更新されたキューを返します。
3. B が内部ノードである場合、 Bの 2 つの子に対してアルゴリズムを再帰的に呼び出し、最初に中心がtに近い子を検索します。これらの呼び出しが順番に更新された後、キューを返します。

上記のポイント 3 で説明した順序で再帰検索を実行すると、検索中にそれ以降の子要素が完全に削除される可能性が高まります。

関数knn_searchが入力されます
    : 
        t、クエリのターゲットポイント
        k、探索するtの最も近い近傍の数
        Q、最大kポイントを含む最大優先キュー
        B、ツリー内のノードまたはボール
    出力： 
        QはB内のk個の最も近い近傍を含む

    距離(t, B.pivot) - B.radius ≥ distance(t, Q.first)の場合、
         Qを変更せず
    に返します。そうでない場合、 Bがリーフノードの場合、 Bの
        各ポイントpに対して、距離(t, p) < distance(t, Q.first)の場合、
            
                Qにpを加える
                サイズ(Q) > kの場合
                    Qから最も遠い隣人を削除する
                終了 if
            終了 if
        繰り返し
    else
        child1をtに最も近い子ノードとする
        child2をtから最も遠い子ノードとする
        knn_search(t, k, Q, 子1)
        knn_search(t, k, Q, 子2)
    終了 if
     Qを
返す関数終了[2]

他のいくつかのデータ構造と比較して、ボールツリーは、特に次元数が増えるにつれて、最近傍探索問題でかなり優れたパフォーマンスを発揮することが示されています。^{[3] [4]} ただし、特定のアプリケーションに最適な最近傍データ構造は、次元数、データポイントの数、およびデータの基礎となる構造によって異なります。