見晴らしの良い木

ヴァンテージポイントツリー（またはVPツリー）は、空間内の位置（「ヴァンテージポイント」）を選択し、データポイントを2つの部分に分割することによって、メトリック空間内のデータを分離するメトリックツリーです。しきい値よりもヴァンテージポイントに近いポイントと、そうでないポイントです。この手順を再帰的に適用してデータをより小さなセットに分割することで、ツリー内の隣接データが空間内の隣接データである可能性が高いツリーデータ構造が作成されます。^[1]

一般化の一つは、マルチバンテージポイントツリー（またはMVPツリー）と呼ばれるもので、類似性検索クエリのために大規模なメトリック空間からオブジェクトをインデックスするためのデータ構造です。各レベルを分割するために複数のポイントを使用します。^[2]^[3]

歴史

ピーター・ヤニロスは、ヴァンテージポイントツリーは彼（ピーター・ヤニロス）とジェフリー・ウルマンによって独立に発見されたと主張した。^[1] しかし、ウルマンは1991年にヤニロスより先にこの手法を発表した。 ^[4 ] ウルマンはこのデータ構造をメトリックツリーと呼び、VPツリーという名前はヤニロスによって提案された。ヴァンテージポイントツリーは、ニールセンらによってブレグマンダイバージェンスを使用して非メトリック空間に一般化された。 ^[5]

$この反復的な分割プロセスはk$ -d ツリーのプロセスに似ていますが、直線的な分割ではなく円形 (または球状、超球状など) の分割を使用します。2 次元ユークリッド空間では、これはデータを分離する一連の円として視覚化できます。

ヴァンテージポイントツリーは、非標準メトリック空間内のデータをメトリックツリーに分割する場合に特に役立ちます。

視点ツリーを理解する

ヴァンテージポイントツリーがデータを格納する方法は、円で表すことができます。^[6]まず、このツリーの各ノードには入力ポイントと半径が含まれていることを理解してください。特定のノードの左の子はすべて円の内側のポイントであり、特定のノードの右の子はすべて円の外側にあります。ツリー自体は、格納されているものに関するその他の情報を知る必要はありません。必要なのは、メトリック空間の特性を満たす距離関数だけです。^[6]

有利な位置にある木を探索する

$ヴァンテージポイントツリーは、ポイントx$ に最も近い近傍を見つけるために使用できます。検索アルゴリズムは再帰的です。任意のステップで、ヴァンテージポイント $v$ としきい値距離 $t$ を持つツリーのノードを操作しています。関心のあるポイント $x は、ヴァンテージポイント$ $v$ から少し離れています。その距離 $dが$ $t$ より小さい場合は、アルゴリズムを再帰的に使用して、しきい値 $t$ よりもヴァンテージポイントに近いポイントを含むノードのサブツリーを検索します。それ以外の場合は、しきい値 $t$ よりもヴァンテージポイントから遠いポイントを含むノードのサブツリーに再帰します。アルゴリズムの再帰的使用により、 $x$ までの距離が $|$ $t$ $-$ $d$ $|$ より小さい近傍ポイント $n が$ 見つかった場合、このノードの他のサブツリーを検索することはできません。発見されたノード $n$ が返されます。それ以外の場合は、他のサブツリーも再帰的に検索する必要があります。

同様のアプローチは、点 $xの$ $k$ 近傍点を見つける場合にも有効です。再帰では、これまでに見つかった近傍点のうち、距離が $|$ $t$ $-$ $d$ $|未満の$ $k'$ $(<$ $k$ $)$ のみである場合に限り、点 $xの$ $k$ $-$ $k'$ 近傍点について他のサブツリーが検索されます。

見晴らしの良い木の利点

インデックスを構築する前にドメインの多次元ポイントを推測する代わりに、距離に基づいて直接インデックスを構築します。^[6]これにより、前処理手順が回避されます。
ヴァンテージポイントツリーの更新は、FastMapアプローチに比べると比較的簡単です。FastMapの場合、データを挿入または削除した後、FastMap自体を再スキャンする必要があります。これには時間がかかりすぎ、再スキャンがいつ開始されるかは不明です。^[6]
距離ベースの方法は柔軟性があり、「固定数の次元の特徴ベクトルとして表現されるオブジェクトをインデックス化することができます。」^[6]

複雑

ヴァンテージポイントツリーを構築するのにかかる時間は、およそ $O (n log n)$ です。各要素について、ツリーは $log n$ レベル降下して配置場所を見つけます。ただし、定数 $k$ があり、 $k$ はツリーノードあたりのヴァンテージポイントの数です。^[3]

$ヴァンテージ$ ポイントツリーを検索して、最も近い単一の近傍を見つけるのにかかる時間コストは、 $O (log n)です。log$ $n$ レベルがあり、それぞれに $k$ 回の距離計算が含まれます。ここで、 $k は$ ツリー内のその位置にあるヴァンテージポイント (要素) の数です。

最も重要な属性である範囲のヴァンテージポイントツリーを検索するための時間コストは、使用されるアルゴリズムの詳細とパラメータによって大きく異なります。Brinの論文^[3]では、さまざまなパラメータを持ついくつかのヴァンテージポイントアルゴリズムを使用して、距離計算の回数で測定されたコストを調査する実験の結果が示されています。

ヴァンテージポイントツリーのスペースコストはおよそ $n$ です。各要素が格納され、各非リーフノード内の各ツリー要素には、その子孫ノードへのポインタが必要です。(実装の選択肢の詳細については、Brin を参照してください。各ノードの要素数のパラメータが要因となります。)

$n$ 個の点がある場合、点間のペアワイズ距離は $O (n 2)$ です。ただし、ヴァンテージポイントツリーの作成には、明示的に $O (n log n)$ の距離のみを計算する必要があり、検索には $O (log n) の$ 距離計算のみが必要です。たとえば、 $x$ と $y$ が点で、距離 $d (x 、 y)$ が小さいことがわかっている場合、距離空間の $三角$ 不等式により $d$ $($ $y$ $、$ $z$ $) \geq$ $d$ $($ $x$ $、$ $z$ $) -$ $d$ $($ $x$ $、$ $y$ $)$ となるため、 $x$ から遠い点 z は必然的に $y$ からもほぼ同じくらい離れます。

参考文献

^ ab Yianilos (1993). 一般距離空間における最近傍探索のためのデータ構造とアルゴリズム。第 4 回 ACM-SIAM 離散アルゴリズムに関するシンポジウム。米国ペンシルバニア州フィラデルフィアの Society for Industrial and Applied Mathematics。pp. 311–321。
^ Bozkaya, Tolga; Ozsoyoglu, Meral (1999 年 9 月)。「類似性検索クエリのための大規模メトリック空間のインデックス作成」。ACM Trans. Database Syst . 24 (3): 361–404. doi : 10.1145/328939.328959 . ISSN 0362-5915. S2CID 6486308.
^ abc Brin, Sergey (1995 年 9 月)。「大規模メトリック空間における近傍検索」。VLDB '95 Proceedings of the 21th [sic] International Conference on Very Large Data Bases。チューリッヒ、スイス: Morgan Kaufmann Publishers Inc.: 574–584。ISBN 9781558603790。
^ Uhlmann, Jeffrey (1991). 「メトリックツリーによる一般的な近接/類似性クエリの満足」. Information Processing Letters . 40 (4): 175–179. doi :10.1016/0020-0190(91)90074-r.
^ Nielsen, Frank (2009). 「効率的な最近傍クエリのための Bregman ヴァンテージポイントツリー」。マルチメディアと実験 (ICME) の議事録。IEEE。pp. 878–881。
^ abcde Fu、Ada Wai-chee、Polly Mei-shuen Chan、Yin-Ling Cheung、Yiu Sang Moon (2000)。「ペアワイズ距離が与えられた場合のn近傍検索のための動的vp-treeインデックス作成」。The VLDB Journal — The International Journal on Very Large Data Bases。Springer -Verlag New York, Inc. Secaucus、NJ、USA。pp. 154–173。vp。2012年10月2日閲覧。

外部リンク

VPツリーを理解する

[pny93-1] Yianilos (1993). 一般距離空間における最近傍探索のためのデータ構造とアルゴリズム。第 4 回 ACM-SIAM 離散アルゴリズムに関するシンポジウム。米国ペンシルバニア州フィラデルフィアの Society for Industrial and Applied Mathematics。pp. 311–321。

[2] Bozkaya, Tolga; Ozsoyoglu, Meral (1999 年 9 月)。「類似性検索クエリのための大規模メトリック空間のインデックス作成」。ACM Trans. Database Syst . 24 (3): 361–404. doi : 10.1145/328939.328959 . ISSN 0362-5915. S2CID 6486308.

[brin-3] Brin, Sergey (1995 年 9 月)。「大規模メトリック空間における近傍検索」。VLDB '95 Proceedings of the 21th [sic] International Conference on Very Large Data Bases。チューリッヒ、スイス: Morgan Kaufmann Publishers Inc.: 574–584。ISBN 9781558603790。

[4] Uhlmann, Jeffrey (1991). 「メトリックツリーによる一般的な近接/類似性クエリの満足」. Information Processing Letters . 40 (4): 175–179. doi :10.1016/0020-0190(91)90074-r.

[nielsen2009-5] Nielsen, Frank (2009). 「効率的な最近傍クエリのための Bregman ヴァンテージポイントツリー」。マルチメディアと実験 (ICME) の議事録。IEEE。pp. 878–881。

[vp-6] Fu、Ada Wai-chee、Polly Mei-shuen Chan、Yin-Ling Cheung、Yiu Sang Moon (2000)。「ペアワイズ距離が与えられた場合のn近傍検索のための動的vp-treeインデックス作成」。The VLDB Journal — The International Journal on Very Large Data Bases。Springer -Verlag New York, Inc. Secaucus、NJ、USA。pp. 154–173。vp。2012年10月2日閲覧。