Arbre métrique

La plupart des algorithmes et des structures de données pour la recherche d'un ensemble de données sont basés sur la classique recherche dichotomique. Par exemple, un arbre kd ou un arbre de portée fonctionne en entrelacent la recherche dichotomique sur les coordonnées séparées et en traitant chaque coordonnée spatiale comme une indépendante contrainte de recherche. Ces structures de données sont bien adaptées aux problèmes de requête de portée qui demandent tous les points ${\displaystyle (x,y)}$ qui satisfont ${\displaystyle {\mbox{min}}_{x}\leq x\leq {\mbox{max}}_{x}}$ et ${\displaystyle {\mbox{min}}_{y}\leq y\leq {\mbox{max}}_{y}}$.

Une limite de ces structures de recherche multidimensionnelles est qu'elles ne sont définies que pour la recherche d'objets pouvant être traités comme des vecteurs.Ils ne s'appliquent pas au cas plus général dans lequel l'algorithme ne reçoit qu'une collection d'objets et une fonction pour mesurer la distance ou la similitude entre deux objets. Elles ne sont pas applicables pour le cas général où l'algorithme a seulement en entrée une collection d'objets et une fonction pour mesurer la différence ou la similarité entre deux objets. Si, par exemple, on possédait une fonction qui renvoie une valeur indiquant à quel point une image est similaire à une autre, un problème algorithmique naturel serait de prendre une base de données d'image et trouver celles qui sont similaires à une image suivant les résultats de la fonction.

S'il n'y a pas de structure pour la mesure de la similarité alors une recherche exhaustive qui requiert la comparaison de l'image de la requête à chaque image de l'ensemble de données est ce qui a de mieux à faire . Si, cependant, la fonction de similarité satisfait l'inégalité triangulaire alors il est possible d'utiliser le résultat de chaque comparaison pour diminuer l'ensemble de candidats à examiner.

Le premier article sur les arbres métriques, aussi le premier à utiliser le terme "arbre métrique", publié en libre consultation a été écrit par Jeffrey Uhlmann en 1991[1]. D'autres chercheurs ont travaillé indépendamment sur des structures de données similaires. EN particulier, Peter Yianilos a prétendu avoir découvert indépendamment la même technique, qu'il a appelé "arbre à point de vue"[2]. La recherche sur les structures de données d'arbres métriques s'est développée à la fin des années 1990, et a amené le cofondateur de Google Sergey Brin à examiner leur utilisation des très larges bases de données[3]. Le premier manuel sur les structures de données métriques a été publié en 2006.