Stratégies alternatives pour la recherche des plus proches voisins dans les espaces multidimensionnels

摘要

Cet article s'intéresse à l'accélération de la recherche par similarité dans les espaces à grande dimension. Les méthodes exactes de recherche de tous les plus proches voisins d'un point requête ont des performances qui se dégradent avec la dimension de l'espace (malédiction de la dimension). D'où l'êclosion cette dernière décennie de solutions alternatives pour accélérer la recherche par similarité. Après avoir dressé un panorama de nouvelles solutions, classées en trois catégories, nous proposons et évaluons trois nouvelles approches permettant d'accélérer la recherche des plus proches voisins selon la classification présentée : nous proposons d'abord une approche progressive exacte appelée HiPeR, indépendante des données et de l'index, que nous illustrons avec l'index VA-fde. Ensuite nous étudions l'adaptation d'HiPeR à la recherche approximative en utilisant un modèle probabiliste de contr?le de la précision. Enfin nous présentons des stratégies de traitement efficace des requêtes multiples avec application aux index arborescents ainsi qu 'à HiPeR.%In this article, we are interested in accelerating similarity search in high dimensional spaces. The performance of exact nearest neighbors search rapidly decays with the increase of the space dimension (curse of dimensionality effect). This justified a significant effort toward alternate solutions for accelerating similarity search in the past ten years. After a short survey of these new solutions organized into three categories, we describe and evaluate three new strategies: first we propose a progressive exact approach, called HiPeR which is independent of the data as well as of the multidimensional index. We illustrate this approach with the VA-file. Then we study the adaptation of HiPeR to approximate search, using a probabilistic model for precision control. Last we present strategies for efficient processing of multiple queries with application to tree indices as well as HiPeR.