Recherche par similarités dans les bases de données multidimensionnelles : panorama des techniques d'indexation
Résumé
Content-based retrieval systems become increasingly popular. It is therefore crucial to understand how multidimensional indexing techniques work, and why they fail in highdimensional spaces. This is the rational for this survey. It first describes the specific properties of high-dimensional spaces. It then moves to the description of exact nearest neighbor searches before presenting the most recent techniques performing approximate searches.
La popularité croissante des systèmes de recherche de similarités par le contenu exploitant de larges bases de données multimédias demande de comprendre le fonctionnement et les dysfonctionnements des techniques d'indexation multidimensionnelles sous-jacentes. Faire le point sur les techniques les plus récentes est l'objet de ce panorama. Celui-ci détaille d'abord les difficultés auxquelles sont confrontées toutes les techniques d'indexation et qui sont, pour la plupart, dues aux particularités des espaces de grande dimension. Ce panorama présente alors les principales techniques pour la recherche exacte de plus proches voisins et se penche ensuite sur les techniques de recherches approximatives pour lesquelles la diminution de la précision du résultat se traduit par une forte diminution du temps de réponse.