Accélération de la recherche dans les espaces de grande dimension : Application à l'indexation d'images par contenu visuel
Institution:
Paris, CNAMDisciplines:
Directors:
Abstract EN:
In this thesis we are interested in accelerating retrieval in large databases where entities are described with high dimensional vectors (or multidimensional points). Several index structures have been already proposed to accelerate retrieval but a large number of these structures suffer from the well known Curse of Dimensionality phenomenon (CoD). In the first part of this thesis we revisited the CoD phenomenon with classical indices in order to determine from which dimension these indices does not work; Our study showed that classical indices still perform well with moderate dimensions (< 30) when dealing with real data. However, needs for accelerating retrieval are not satisfied when dealing with high dimensional spaces or with large databases. The latter observations motivated our main contribution called HiPeR. HiPeR is based on a hierarchy of subspaces and indexes: it performs nearest neighbors search across spaces of different dimensions, by beginning with the lowest dimensions up to the highest ones, aiming at minimizing the effects of curse of dimensionality. Scanning the hierarchy can be done according to several scenarios that are presented for retrieval of exact as well as approximate neighbors. In this work, HiPeR has been implemented on the classical index structure VA-File, providing VA-Hierarchies. For the approximate scenario, the model of precision loss defined is probabilistic and non parametric (very little assumptions are made on the data distribution) and quality of answers can be selected by user at query time. HiPeR is evaluated for range queries on 3 real data-sets of image descriptors varying from 500,000 vectors to 4 millions. The experiments demonstrate that the hierarchy of HiPeR improves the best index structure by significantly. Reducing CPU time, whatever the scenario of retrieval. Its approximate version improves even more retrieval by saving I/O access significantly. In the last part of our thesis, we studied the particular case of multiple queries where each database entity is represented with several vectors. To accelerate retrieval with such queries different strategies were proposed to reduce I/O and CPU times. The proposed strategies were applied both to simple indices as well as to HiPeR.
Abstract FR:
L'objectif des travaux de recherche présentés dans cette thèse est l'accélération de la recherche dans les grandes bases de données décrites par des vecteurs de grande dimension. Différentes structures ont déjà été proposées dans la littérature afin de réduire les temps de recherche mais plusieurs d'entre elles souffrent du problème de la malédiction de la dimension. Dans une première partie de cette thèse nous avons revisité le phénomène de la malédiction de la dimension avec les index classiques afin de déterminer à partir de quelle dimension ces index deviennent inefficaces. Cette première étude a montré que les index classiques fonctionnent bien avec des dimensions modérées (< 30) avec les bases réelles. Toutefois pour des dimensions plus importantes le problème de la malédiction de la dimension persiste. D'un autre coté avec l'augmentation des volumes des données ces dernières décennies vu la facilité de leur stockage, les besoins d'accélération de la recherche sont de plus en plus importants. Ces derniers points ont motivé la proposition de HiPeR notre principale contribution. HiPeR est un modèle hiérarchique qui assure la recherche exacte, progressive et approximative avec contrôle de précision. Elle est basée sur une hiérarchie d'espaces et d'index : la recherche commence par les espaces à faibles dimensions afin de réduire les effets de la malédiction de la dimension fournissant un premier résultat. Ce dernier sera amélioré progressivement en utilisant de plus grandes dimensions. Différentes stratégies sont proposées pour parcourir HiPeR en assurant la recherche exacte ou approximative. La qualité de la réponse approximative est fixée par l'utilisateur au moment de la recherche. Afin d'assurer la qualité escomptée, la méthode suit un modèle de précision probabiliste et non paramétrique. Les expériences, menées sur trois bases réelles de 4 millions de points, montrent qu'HiPeR améliore considérablement les index classiques en termes de temps CPU et d'accès I/O. Dans la dernière partie de cette thèse nous avons étudié le cas particulier des requêtes multiples où chaque entité de la base est décrite par plusieurs vecteurs. Afin d'accélérer la recherche dans une telle configuration, différentes stratégies ont été proposées et expérimentées avec les index classiques et HiPeR.