Vantage-point tree とは

仮想ポイントツリー(またはVPツリー)は、メトリックスペース内の位置を選択し、データポイントを2つの部分に分割することによってメトリック空間内のデータを分離するメトリックツリーです。閾値よりも有利な点、そうでない点がある。この手順を再帰的に適用して、データをより小さい小さな集合に分割することにより、ツリー内の近傍が空間内の近傍になる可能性のあるツリーデータ構造が作成される。
1つの一般化は、マルチ・ポイント・ポイント・ツリー、つまりMVPツリーと呼ばれます。これは、類似検索クエリーのために大きなメトリック・スペースからオブジェクトを索引付けするためのデータ構造です。複数のポイントを使用して各レベルを分割します。