計量木とは、計量空間におけるデータのインデックス作成に特化した木構造のことである。計量木は、三角不等式などの計量空間の特性を利用して、データへのアクセス効率を高める。例としては、M木、VP木、被覆木、MVP木、BK木などが挙げられる。[ 1 ]
多次元検索
データセットを検索するためのアルゴリズムとデータ構造のほとんどは、古典的な二分探索アルゴリズムに基づいています。kd木や範囲木などの一般化は、二分探索アルゴリズムを個別の座標にインターリーブし、各空間座標を独立した探索制約として扱うことで機能します。これらのデータ構造は、およびを満たすすべての点を求める範囲クエリ問題に適しています。
これらの多次元探索構造の限界は、ベクトルとして扱えるオブジェクトのみを対象とした探索に定義されていることです。より一般的なケース、つまりオブジェクトの集合と2つのオブジェクト間の距離または類似度を測定する関数のみがアルゴリズムに与えられるようなケースには適用できません。例えば、ある画像が別の画像にどれほど類似しているかを示す値を返す関数を誰かが作成したとしたら、自然なアルゴリズム上の問題は、画像のデータセットを受け取り、その関数に基づいて与えられたクエリ画像に類似する画像を見つけることでしょう。
メトリックデータ構造
類似度測定に構造がない場合、クエリ画像とデータセット内のすべての画像を比較する総当たり検索が最善の策となります。しかし、類似度関数が三角不等式を満たす場合は、各比較の結果を用いて、検査対象となる候補集合を絞り込むことが可能です。
メトリックツリーに関する最初の論文、そして「メトリックツリー」という用語が初めて公開文献に掲載されたのは、1991年のジェフリー・ウルマンによるものでした。 [ 2 ]他の研究者も同様のデータ構造について独立して研究していました。特にピーター・ヤニロスは、同じ手法を独自に発見したと主張し、それをヴァンテージポイントツリー（VPツリー）と呼びました。[ 3 ] メトリックツリーデータ構造の研究は1990年代後半に開花し、Googleの共同創設者であるセルゲイ・ブリンによる大規模データベースへの応用に関する調査も行われました。[ 4 ]メトリックデータ構造に関する最初の教科書は2006年に出版されました。[ 1 ]
オープンソース実装
参考文献
- ^ a bサメット、ハナン（2006年）『多次元および計量データ構造の基礎』モーガン・カウフマン、ISBN 978-0-12-369446-1。
- ^ Uhlmann, Jeffrey (1991). 「メトリックツリーによる一般的な近接性/類似性クエリの満足」.情報処理レター. 40 (4): 175– 179. doi : 10.1016/0020-0190(91)90074-r .
- ^ Yianilos, Peter N. (1993). 「一般距離空間における最近傍探索のためのデータ構造とアルゴリズム」 .第4回ACM-SIAM離散アルゴリズムシンポジウム議事録. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. pp. 311– 321. pny93 . 2019年3月7日閲覧。
- ^ Brin, Sergey (1995). 「大規模距離空間における近傍探索」(PDF) .第21回国際超大規模データベース会議 (VLDB) .
- ^ 「Trackerコンポーネントライブラリ」 . MATLABリポジトリ. 2019年1月5日閲覧。
