メトリックツリー

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

距離ツリーは、距離空間のデータにインデックスを付けることに特化したツリーデータ 構造です。距離ツリーは、三角不等式などの距離空間のプロパティを利用して、データへのアクセスをより効率的にします。例としては、MツリーvpツリーカバーツリーMVPツリーBKツリーなどがあります。[1]

多次元検索

データセットを検索するためのほとんどのアルゴリズムとデータ構造は、従来のバイナリ検索アルゴリズムに基づいており、 kdツリー範囲ツリーなどの一般化は、バイナリ検索アルゴリズムを個別の座標にインターリーブし、各空間座標を独立した検索制約として扱うことで機能します。これらのデータ構造は、すべてのポイントを要求する範囲クエリの問題に最適です。満足する

これらの多次元検索構造の制限は、ベクトルとして扱うことができるオブジェクトを検索するためにのみ定義されていることです。これらは、アルゴリズムにオブジェクトのコレクションと2つのオブジェクト間の距離または類似性を測定する関数のみが与えられるより一般的なケースには適用できません。たとえば、ある画像が別の画像にどれだけ類似しているかを示す値を返す関数を誰かが作成した場合、自然なアルゴリズムの問​​題は、画像のデータセットを取得し、その関数に従って特定の画像に類似している画像を見つけることです。クエリ画像。

メトリックデータ構造

類似性測度の構造がない場合は、クエリ画像をデータセット内のすべての画像と比較する必要のあるブルートフォース検索が最善の方法です[要出典]ただし、類似度関数が三角不等式を満たす場合は、各比較の結果を使用して、調査する候補のセットを整理することができます。

公開文献に掲載されたメトリックツリーに関する最初の記事、および「メトリックツリー」という用語の最初の使用は、1991年にJeffreyUhlmannによって作成されました。 [2]他の研究者は同様のデータ構造に独自に取り組んでいました。特に、Peter Yianilosは、彼が見晴らしの良いポイントツリー(VPツリー)と呼んだ同じ方法を独自に発見したと主張しました。[3] メトリックツリーのデータ構造に関する研究は、1990年代後半に開花し、Googleの共同創設者であるSergeyBrinによる非常に大規模なデータベースへの使用の調査が含まれていました。[4]メトリックデータ構造に関する最初の教科書は2006年に発行されました。[1]

オープンソースの実装

参照

  1. ^ a b サメット、ハナン(2006)。多次元およびメトリックデータ構造の基盤モーガンカウフマン。ISBN 978-0-12-369446-1
  2. ^ Uhlmann、Jeffrey(1991)。「メトリックツリーによる一般的な近接性/類似性クエリの満足」。情報処理レター40(4)。土井10.1016 / 0020-0190(91)90074-r
  3. ^ Yianilos、Peter N.(1993)。「一般的な距離空間での最近傍探索のデータ構造とアルゴリズム」離散アルゴリズムに関する第4回ACM-SIAMシンポジウムの議事録Society for Industrial and Applied Mathematicsフィラデルフィア、ペンシルベニア州、米国。pp。311–321。pny93 2019年3月7日取得
  4. ^ ブリン、セルゲイ(1995)。「大きな距離空間での近傍検索」(PDF)第21回超大規模データベースに関する国際会議(VLDB)
  5. ^ 「トラッカーコンポーネントライブラリ」Matlabリポジトリ2019年1月5日取得