Refereed full papers (journals, book chapters, international conferences)

1999

@article{KAA1999,
	vgclass =	{refpap},
	vgproject =	{cbir},
	author =	{K. V. Ravi Kanth and Divyakant Agrawal and Amr El Abbadi
	and Ambuj Singh},
	title =	{Dimensionality Reduction for Similarity Searching in
	Dynamic Databases},
	journal =	{Computer Vision and Image Understanding (special issue on content-based access for image
	and video libraries)},
	volume =	{75},
	number =	{1/2},
	pages =	{59--72},
	month =	{July/August},
	year =	{1999},
	url =	{http://www.cs.ucsb.edu/\~{}kravi/dimred.ps},
	abstract =	{Databases are increasingly being used to store multimedia
	objects such as maps, images, audio, and video. Storage and retrieval
	of these objects is accomplished using multidimensional index
	structures such as $R^*$-trees and SS-trees. As dimensionality
	increases, query performance in these index structures degrades. This
	phenomenon, generally referred to as the dimensionality curse, can be
	circumvented by reducing the dimensionality of the data. Such a
	reduction is, however, accompanied by a loss of precision of query
	results. Current techniques such as QBIC use SVD transform-based
	dimensionality reduction to ensure high query precision. The drawback
	of this approach is that SVD is expensive to compute and, therefore,
	not readily applicable to dynamic databases. In this paper, we propose
	novel techniques for performing SVD-based dimensionality reduction in
	dynamic databases. When the data distribution changes considerably so
	as to degrade query precision, we recompute the SVD transform and
	incorporate it in the existing index structure. For recomputing the
	SVD-transform, we propose a novel technique that uses \emph{aggregate}
	data from the existing index rather than the entire data. This
	technique reduces the SVD-computation time without compromising query
	precision.  We then explore efficient ways to incorporate the
	recomputed SVD-transform in the existing index structure. These
	techniques reduce the computation time by a factor of 20 in experiments
	on color and texture image vectors. The error due to approximate
	computation of SVD is less than 10\%.},
}