Vantage point tree
Un arbre à points de vue (ou vp-tree, abréviation de l'appellation anglaise vantage point tree) est un arbre métrique permettant de partitionner n'importe quel espace de données pourvu d'une métrique, c'est-à-dire d'une mesure de distance entre les nœuds ou points représentant les données. Le processus de construction de l'arbre consiste à sélectionner un point privilégié (ledit point de vue ou point d'observation / de référence, vantage point en anglais), puis à diviser l'espace en deux sous-espaces : un sous-espace gauche (ou intérieur) contenant l'ensemble des points à une distance du point privilégié inférieure à un certain seuil, et un sous-espace droit (ou extérieur) contenant l'ensemble des points ne remplissant pas cette condition. Le processus est appliqué de manière récursive, produisant des sous-espaces de plus en plus petits. Le vp-tree résultant est une structure de données arborescente telle qu'une proximité dans l'arbre est représentative de la proximité dans l'espace de données ainsi partitionné.
Ce processus de partitionnement itératif est similaire à celui d'un k-d tree, mais utilise des partitions circulaires (ou sphériques, hypersphériques, etc. selon la dimension de l'espace) plutôt que rectilignes. Dans un espace euclidien bidimensionnel, il produit un découpage en régions dont la forme ressemble à des coquilles sphériques[1].
Histoire
modifierLa 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, vps-tree, vpsb-tree)[3].
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[4],[5].
En 2009, Nielsen et des collabrateurs 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[6].
Construction
modifierLa construction la plus simple d'un vp-tree consiste à partitionner l'espace à l'aide de coupes sphériques, au sens de la distance choisie, c'est-à-dire qu'on s'intéresse aux points à une certaine distance d'un point privilégié, donc dans une sphère centrée en ce point.
On sélectionne d'abord un point pivot (vantage point) correspondant à un nœud de l'arbre.
On calcule ensuite les distances de tous les autres points (c.-à-d. les points qui seront indexés sous ce nœud) au point pivot.
La valeur médiane de ces distances est utilisée comme distance-seuil, de sorte que la moitié des points se trouve à l'intérieur de la boule de centre et de rayon , et l'autre moitié à l'extérieur.
On associe 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.
On construit ensuite 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 l'évaluation de la fonction de distance[7]. Cette méthode d'indexation basée uniquement sur la distance peut donc aussi être utilisée dans des espaces métriques non standards (en particulier non euclidiens). Elle n'exige aucune hypothèse sur la géométrie de l'espace de données.
Recherche du plus proche voisin
modifierUn vp-tree peut être utilisé pour trouver le plus proche voisin d'un point . Cette recherche peut être couplée à une condition sur la distance maximale entre deux points pour qu'ils soient considérés comme suffisamment proches.
L'algorithme de recherche est récursif. Une implémentation possible est la suivante[2],[4] :
À chaque nœud, de point pivot (vantage point) et de distance-seuil (la lettre étant choisie à cause de l'anglais threshold, seuil), on calcule la distance de à ;
Si , on stocke les nouvelles valeurs : , .
Si , alors tous les points du sous-arbre de gauche sont à une distance inférieure ou égale à de . On continue la recherche de manière récursive dans le sous-arbre de gauche (intérieur de la boule).
Si , on cherche de manière récursive dans le sous-arbre de gauche (intérieur de la boule) ; si , on cherche de manière récursive dans le sous-arbre de droite (extérieur de la boule).
Le pire des cas se produit lorsque , c'est-à-dire lorsque l'ensemble des points 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.
Complexité
modifierLa méthode de construction la plus simple a une complexité de . Pour chaque élément, niveaux sont parcourus pour trouver son emplacement[3].
La temps d'exécution de la recherche d'un plus proche voisin unique est d'environ [3].
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. S. Brin a détaillé 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[5] . 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 ). Chaque point de données est stocké et chaque élément de chaque nœud interne (c'est-à-dire qui n'est pas une feuille) nécessite un pointeur vers ses nœuds descendants[8].
Certains outils d'espace métrique nécessitent le calcul d'une matrice de distances par paires, de coût . Ce n'est pas nécessaire avec les vp-trees.
Références
modifier- Voir Figure 1. et Figure 2. dans (en) Peter Yianilos, « Data structures and algorithms for nearest neighbor search in general metric spaces », dans Fourth annual ACM-SIAM symposium on Discrete algorithms, Philadelphie, PA, USA, Society for Industrial and Applied Mathematics, (lire en ligne), p. 311–321.
- (en) Jeffrey Uhlmann, « Satisfying General Proximity/Similarity Queries with Metric Trees », Information Processing Letters, vol. 40, , p. 175–179 (DOI 10.1016/0020-0190(91)90074-r).
- (en) Peter Yianilos, « Data structures and algorithms for nearest neighbor search in general metric spaces », dans Fourth annual ACM-SIAM symposium on Discrete algorithms, Philadelphie, PA, USA, Society for Industrial and Applied Mathematics, (lire en ligne), p. 311–321.
- (en) Tolga Bozkaya et Meral Ozsoyoglu, « Indexing Large Metric Spaces for Similarity Search Queries », ACM Trans. Database Syst., vol. 24, no 3, , p. 361–404 (ISSN 0362-5915, DOI 10.1145/328939.328959, S2CID 6486308).
- (en) Sergey Brin, « Near Neighbor Search in Large Metric Spaces », dans VLDB '95 Proceedings of the 21th International Conference on Very Large Data Bases, Zurich, Morgan Kaufmann Publishers Inc., (ISBN 9781558603790, lire en ligne), p. 574–584.
- Frank Nielsen, « Bregman vantage point trees for efficient nearest Neighbor Queries », dans Proceedings of Multimedia and Exp (ICME), IEEE, , p. 878–881.
- (en) Ada Wai-chee Fu, Polly Mei-shuen Chan, Yin-Ling Cheung et Yiu Sang Moon, « Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances », The VLDB Journal — The International Journal on Very Large Data Bases, , p. 154–173 (lire en ligne, consulté le ).
- Voir l'article S. Brin 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.
