ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Décisions, argumentation et traçabilité dans l’Ingénierie des Systèmes d’Information
En savoir plus >>
Autres revues >>

Ingénierie des Systèmes d'Information

Networking and Information Systems
1633-1311
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 15/1 - 2010  - pp.35-60  - doi:10.3166/isi.15.1.35-60
TITRE
Stratégies alternatives pour la recherche des plus proches voisins dans les espaces multidimensionnels

TITLE
Alternative strategies for nearest neighbour search in multidimensional spaces

RÉSUMÉ
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-file. 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.


ABSTRACT
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.


AUTEUR(S)
Nouha BOUTELDJA, Valérie GOUET-BRUNET, Michel SCHOLL

MOTS-CLÉS
indexation multidimensionnelle, recherche exacte et approximative, requêtes multiples.

KEYWORDS
multidimensional Indexing, exact and approximative retrieval, multiple queries.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (328 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier