カバーツリー

カバーツリーは、コンピュータサイエンスにおけるデータ構造の一種で、特に最近傍検索の高速化を目的として設計されています。これは、Navigating Netデータ構造を改良したもので、本質的に低次元のデータをインデックスするために開発されたさまざまな他のデータ構造に関連しています。^[1]

ツリーは、最上位レベルにルートポイントが含まれ、最下位レベルにメトリック空間内のすべてのポイントが含まれる階層構造として考えることができます。各レベルCには整数値iが関連付けられており、ツリーが下がっていくにつれて 1 ずつ減少します。カバー ツリーの各レベルCには、3 つの重要なプロパティがあります。

• ネスト: ${\displaystyle C_{i}\subseteq C_{i-1}}$
• 被覆:あらゆる点 に対して、から までの距離が 以下となる点が存在し、そのような点のうち 1 つが の親となります。${\displaystyle p\in C_{i-1}}$${\displaystyle q\in C_{i}}$${\displaystyle p}$${\displaystyle q}$${\displaystyle 2^{i}}$${\displaystyle q}$${\displaystyle p}$
• 分離:すべての点 について、から までの距離は よりも大きくなります。${\displaystyle p,q\in C_{i}}$${\displaystyle p}$${\displaystyle q}$${\displaystyle 2^{i}}$

他のメトリック ツリーと同様に、カバー ツリーでは、 での最近傍検索が可能です。ここで、はデータ セットの次元に関連付けられた定数で、n は基数です。比較すると、基本的な線形検索では が必要であり、これは への依存度がはるかに高くなります。ただし、高次元のメトリック空間では、定数は重要であり、複雑性分析で無視することはできません。他のメトリック ツリーとは異なり、カバー ツリーには、データ セットの拡張定数または倍増定数 (近似 NN 検索の場合) に基づく理論的な上限があります。検索時間の上限は で、はデータ セットの拡張定数です。 ${\displaystyle O(\eta *\log {n})}$${\displaystyle \eta}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle \eta}$${\displaystyle O(c^{12}\log {n})}$${\displaystyle c}$

カバーツリーはナイーブなアプローチよりも高速な検索を提供しますが、この利点はデータ構造を維持するための追加コストと比較検討する必要があります。ナイーブなアプローチでは、順序を維持する必要がないため、データセットに新しいポイントを追加するのは簡単ですが、カバーツリーでは時間がかかることがあります。ただし、これは上限であり、実際にはパフォーマンスを向上させると思われるいくつかの手法が実装されています。^[2]${\displaystyle O(c^{6}\log {n})}$

カバーツリーは暗黙的な表現を使用して繰り返しポイントを追跡します。したがって、必要なスペースは O(n) のみです。

• 最近傍探索
• kdツリー
• Mツリー

注記

文献

• Alina Beygelzimer、Sham Kakade、John Langford。「Nearest Neighbor のカバー ツリー」。国際機械学習会議 (ICML) の Proc.、2006 年。
• JL の Cover Tree ページ。John Langford のページには論文とコードへのリンクがあります。
• GitHub 上の C++ カバー ツリー実装。
• Java でのカバー ツリーの実装。