Réduction de dimensionnalité pour la recherche de similarité dans les bases de données dynamiques

Les bases de données sont de plus en plus utilisées pour stocker des objets multimédias tels que des cartes, des images, de l'audio et de la vidéo. Le stockage et la récupération de ces objets se font à l'aide de structures d'index multidimensionnelles telles que les R*-arbres et les SS-arbres. À mesure que la dimensionnalité augmente, les performances des requêtes dans ces structures d'index se dégradent. Ce phénomène, généralement appelé malédiction de la dimensionnalité, peut être contourné en réduisant la dimensionnalité des données. Cependant, une telle réduction s'accompagne d'une perte de précision des résultats de requête. Les techniques actuelles telles que QBIC utilisent une réduction de dimensionnalité basée sur la transformation SVD pour garantir une haute précision des requêtes. L'inconvénient de cette approche est que le calcul de la SVD est coûteux et donc pas facilement applicable aux bases de données dynamiques. Dans cet article, nous proposons des techniques novatrices pour effectuer une réduction de dimensionnalité basée sur la SVD dans des bases de données dynamiques. Lorsque la distribution des données change considérablement au point de dégrader la précision des requêtes, nous recalculons la transformation SVD et l'incorporons dans la structure d'index existante. Pour le recalcul de la transformation SVD, nous proposons une technique novatrice qui utilise des données agrégées provenant de l'index existant plutôt que l'ensemble des données. Cette technique réduit le temps de calcul SVD sans compromettre la précision des requêtes. Nous explorons ensuite des moyens efficaces d'incorporer la transformation SVD recalculée dans la structure d'index existante sans dégrader les temps de réponse des requêtes suivantes. Ces techniques réduisent le temps de calcul d'un facteur 20 dans des expériences sur des vecteurs d'images de couleur et de texture. L'erreur due au calcul approximatif de la SVD est inférieure à 10%.