Clustering and singular value decomposition for approximate indexing in high dimensional spaces-猫眼课题宝

DOI：

10.1145/288627.288658

发表时间：

1998-11

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Alexander Thomasian;Vittorio Castelli;Chung-Sheng Li

特征空间的高维索引对于许多数据密集型应用至关重要，例如从多媒体数据库中基于内容的图像或视频检索以及数据挖掘中模式的相似性检索。不幸的是，最近邻（NN）查询，这是相似性搜索所需的性能，迅速恶化的维数的增加。我们提出了聚类与奇异值分解（CSVD）方法，它结合了聚类和奇异值分解（SVD），以减少索引维度的数量，同时保持一个合理的高精度为一个给定的召回值。在所提出的CSVD方法中，同质点被分组到聚类中，使得每个聚类中的点比原始数据集更适合降维。对卫星图像纹理矢量的实验表明，在保持相同总方差的情况下，CSVD比SVD具有更高的降维效果。相反，对于相同的压缩比，CSVD导致相对于SVD的保留总方差的增加（例如，对于20：1的压缩比增加70%）。这转化为更高的效率，在处理近似NN查询，量化艾德通过实验结果。

High-dimensionality indexing of feature spaces is critical for many data-intensive applications such as content-based retrieval of images or video from multimedia databases and similarity retrieval of patterns in data mining. Unfortunately, the performance of nearest neighbor (NN) queries, which are required for similarity search, deteriorates rapidly with the increase in the number of dimensions. We propose the Clustering with Singular Value Decomposition (CSVD) method, which combines clustering and singular value decomposition (SVD) to reduce the number of index dimensions, while maintaining a reasonably high precision for a given value of recall. In the proposed CSVD method, homogeneous points are grouped into clusters such that the points in each cluster are more amenable to dimensionality reduction than the original dataset. Experiments with texture vectors extracted from satellite images show that CSVD achieves signi cantly higher dimensionality reduction than SVD 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., a 70% increase for a 20:1 compression ratio). This translates to a higher e ciency in processing approximate NN queries, as quanti ed through experimental results.

Clustering and singular value decomposition for approximate indexing in high dimensional spaces

文献摘要

被引文献

相似文献