Vantage point tree

La première mention de cette méthode remonte à 1991 : elle est présentée sous le nom d'arbre métrique dans un article publié par Jeffrey Uhlmann[2]. Toutefois, on doit l'appellation vantage point tree à Peter Yianilos, qui affirme dans un papier datant de 1993 avoir formalisé cette méthode indépendamment des recherches de J. K. Uhlmann. Dans cette publication, il introduit trois versions du vp-tree (vp-tree, vp^s-tree, vp^sb-tree)[1].

En 1999, T. Bozkaya et M. Ozsoyoglu proposent les arbres à points de vue multiples (ou mvp-tree, abréviation de l'appellation anglaise multivantage point tree). Les mvp-trees sont une généralisation des vp-trees. Cette approche a été développée afin d'améliorer les propriétés des vp-trees lors de requêtes de recherche de similarité sur de grands espaces métriques. La différence majeure est l'utilisation de plus d'un point de référence pour partitionner l'espace à chaque niveau[3] - [4].

En 2009, Nielsen et al créent les bvp-trees (ou Bregman ventage point trees) et étendent ainsi les vp-trees à des espaces non métriques en utilisant les divergences de Bregman[5].

La construction la plus simple d'un vp-tree consiste à partitionner l'espace à l'aide de coupes sphériques de la façon suivante :

À chaque nouveau nœud, sélectionner un point pivot v ("vantage point") parmi les points du nœud ;

Calculer les distances de tous les autres points (c.-à-d. les points qui seront indexés sous ce nœud) au point pivot ;

Calculer la distance médiane ${\displaystyle dist_{m}}$ et l'utiliser comme distance seuil, de façon à ce que la moitié des points se trouve à l'intérieur de la boule de centre v et de rayon ${\displaystyle dist_{m}}$, et l'autre moitié à l'extérieur ;

Associer les points qui se trouvent à l'intérieur de la boule au sous-arbre de gauche, et ceux se trouvant à l'extérieur au sous-arbre de droite ;

Construire de manière récursive les branches de niveau inférieur.

Le vp-tree est une structure de données intéressante car elle ne nécessite aucune connaissance des points autre que le résultat de l'évaluation de la fonction de distance qui satisfait les propriétés de l'espace métrique[6]. Cette méthode d'indexation basée uniquement sur la distance peut donc aussi être utilisée dans des espaces métriques non standards (et notamment : non euclidens). Elle ne fait aucune hypothèse sur la géométrie de l'espace de données.

Un vp-tree peut être utilisé pour trouver le plus proche voisin ${\displaystyle {x}_{best}}$ d'un point ${\displaystyle x_{1}}$. Cette recherche peut être couplée à une condition de distance maximale ${\displaystyle \tau }$ qu'un point voisin doit respecter pour être considéré comme "suffisamment proche".

L'algorithme de recherche est récursif. Une implémentation possible est la suivante[2] - [3] :

À chaque nœud, de point pivot v ("vantage point") et de distance seuil t ("threshold"), calculer la distance ${\displaystyle dist(x_{1},v)}$ de ${\displaystyle x_{1}}$ à v ;

Si ${\displaystyle dist(x_{1},v)\leq \tau }$, stocker les nouvelles valeurs : ${\displaystyle {x}_{best}=v}$, ${\displaystyle \tau =dist(x_{1},{x}_{best})}$ ;

Si ${\displaystyle dist(x_{1},v)+t\leq \tau }$, alors tous les points du sous-arbre de gauche sont à une distance inférieure ou égale à ${\displaystyle \tau }$ de ${\displaystyle x_{1}}$. Chercher de manière récursive dans le sous-arbre de gauche (intérieur de la boule) ;

Si ${\displaystyle dist(x_{1},v)\leq t+\tau }$, chercher de manière récursive dans le sous-arbre de gauche (intérieur de la boule) ;

Si ${\displaystyle dist(x_{1},v)\geq t-\tau }$, chercher de manière récursive dans le sous-arbre de droite (extérieur de la boule).

Le pire des cas arrive lorsque ${\displaystyle t-\tau \leq dist(x_{1},v)\leq t+\tau }$, c'est-à-dire lorsque l'ensemble des points candidats (i.e qui pourraient satisfaire la requête) intersecte à la fois la boule associée au sous-arbre gauche et la boule associée au sous-arbre droit. Dans ce cas, il faut chercher de manière récursive dans les deux sous-arbres : aucun élagage de l'arbre n'est possible.

La méthode de construction la plus simple a une complexité de O(n log n). Pour chaque élément, log n niveaux sont parcourus pour trouver son emplacement[1].

La temps d'exécution d'une recherche d'un unique plus proche voisin est d'environ O(log n)[1].

Le temps nécessaire au parcours d'un vp-tree pour un ensemble de données, peut varier considérablement en fonction des spécificités de l'algorithme utilisé et du choix des paramètres. L'article de S. Brin[4] détaille les performances de plusieurs variantes algorithmiques du vp-tree, pour plusieurs valeurs de paramètres, afin d'étudier le coût de chacune d'entre elles. Le coût est mesuré en nombre de calculs de distance.

Le coût en termes d'espace de stockage pour un vp-tree est linéaire (environ n). Chaque point de données est stocké et chaque élément de chaque nœud interne (c.-à-d. non feuille) nécessite un pointeur vers ses nœuds descendants. (Voir S. Brin[4] pour plus de détails sur le choix de l'implémentation. Le paramètre codant pour le nombre d'éléments à chaque nœud joue un rôle important. )

Notez que certains outils d'espace métrique nécessitent le calcul d'une matrice de distances par paires, de coût O(n²). Ce n'est pas nécessaire avec les vp-trees.

• "VP trees: A data structure for finding stuff fast" - Steve Hanov's Blog