CSVD: approximate similarity searches in high-dimensional spaces using clustering and singular value decomposition

Alexander Thomasian; Vittorio Castelli; Chung-Sheng Li

doi:10.1117/12.325808

5 October 1998 CSVD: approximate similarity searches in high-dimensional spaces using clustering and singular value decomposition

Alexander Thomasian, Vittorio Castelli, Chung-Sheng Li

Author Affiliations +

Proceedings Volume 3527, Multimedia Storage and Archiving Systems III; (1998) https://doi.org/10.1117/12.325808
Event: Photonics East (ISAM, VVDC, IEMB), 1998, Boston, MA, United States

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.

Citation Download Citation

Alexander Thomasian, Vittorio Castelli, and Chung-Sheng Li "CSVD: approximate similarity searches in high-dimensional spaces using clustering and singular value decomposition", Proc. SPIE 3527, Multimedia Storage and Archiving Systems III, (5 October 1998); https://doi.org/10.1117/12.325808

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available