Report ID
1998-10
Report Authors
K. V. Ravi Kanth, Divyakant Agrawal, Amr El Abbadi, and Ambuj Singh
Report Date
Abstract
Databases are increasingly being used to store multi-media objects such asmaps, images, audio and video. Storage and retrieval of these objects isaccomplished using multi-dimensional index structures such as R*-trees andSS-trees. As dimensionality increases, query performance in these indexstructures degrades. This phenomenon, generally referred to as thedimensionality curse, can be circumvented by reducing the dimensionality of thedata. Such a reduction is however accompanied by a loss of precision of queryresults. Current techniques such as QBIC use SVD transform-baseddimensionality reduction to ensure high query precision. The drawback of thisapproach is that SVD is expensive to compute, and therefore not readilyapplicable to dynamic databases.In this paper, we propose novel techniques for performing SVD-baseddimensionality reduction in dynamic databases. When the data distributionchanges considerably so as to degrade query precision, we recompute the SVDtransform and incorporate it in the existing index structure. For recomputingthe SVD-transform, we propose a novel technique that uses aggregate data fromthe existing index rather than the entire data. This technique reduces theSVD-computation time without compromising query precision. We then exploreefficient ways to incorporate the recomputed SVD-transform in the existingindex structure without degrading subsequent query response times. Thesetechniques reduce the computation time by a factor of 20 in experiments oncolor and texture image vectors. The error due to approximate computation ofSVD is less than 10%.
Document
1998-10.ps236.37 KB