Share Email Print
cover

Proceedings Paper

CSVD: approximate similarity searches in high-dimensional spaces using clustering and singular value decomposition
Author(s): Alexander Thomasian; Vittorio Castelli; Chung-Sheng Li
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

Many data-intensive applications, such as content-based retrieval of images or video from multimedia databases and similarity retrieval of patterns in data mining, require the ability of efficiently performing similarity queries. Unfortunately, the performance of nearest neighbor (NN) algorithms, the basis for similarity search, quickly deteriorates with the number of dimensions. In this paper we propose a method called Clustering with Singular Value Decomposition (CSVD), combining clustering and singular value decomposition (SVD) to reduce the number of index dimensions. With CSVD, points are grouped into clusters that are more amenable to dimensionally reduction than the original dataset. Experiments with texture vectors extracted from satellite images show that CSVD achieves significantly higher dimensionality reduction than SVD along for the same fraction of total variance preserved. Conversely, for the same compression ratio CSVD results in an increase in preserved total variance with respect to SVD (e.g., at 70% increase for a 20:1 compression ratio). Then, approximate NN queries are more efficiently processed, as quantified through experimental results.

Paper Details

Date Published: 5 October 1998
PDF: 11 pages
Proc. SPIE 3527, Multimedia Storage and Archiving Systems III, (5 October 1998); doi: 10.1117/12.325808
Show Author Affiliations
Alexander Thomasian, IBM Thomas J. Watson Research Ctr. (United States)
Vittorio Castelli, IBM Thomas J. Watson Research Ctr. (United States)
Chung-Sheng Li, IBM Thomas J. Watson Research Ctr. (United States)


Published in SPIE Proceedings Vol. 3527:
Multimedia Storage and Archiving Systems III
C.-C. Jay Kuo; Shih-Fu Chang; Sethuraman Panchanathan, Editor(s)

© SPIE. Terms of Use
Back to Top