基于SVD的二次型距离相似索引层次算法  

Hierarchical similarity indexing for quadratic distance based on SVD technology

作　　者：罗明[1] 白雪生[1] 徐光祐[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《清华大学学报（自然科学版）》2002年第1期36-39,共4页Journal of Tsinghua University(Science and Technology)

基　　金：国家"八六三"高技术项目 ( 86 3-30 6 -ZT0 4-0 2 -0 1及86 3-30 6 -QN99-0 1)

摘　　要：大容量多媒体数据库的基于内容相似性的检索本质上是高维特征空间中一定距离函数的 K近邻问题。对适合人类视觉的二次型距离函数 ,即使采用相似索引 ,当特征空间维数较高时检索仍不能保证实时性。为了解决此问题 ,提出基于 SVD(Singular Value Decomposition)的二次型距离相似索引层次算法 ,先以相似索引为基础在主导特征的子空间上进行代价低的近似检索 ,再对过滤结果在高维特征空间中进行线性的精确检索。实验证明 :该方法具有正确性。Searches based on content similarities in large multimedia libraries are essentially K nearest neighbor searches in high dimensional spaces. The main issue influencing the real time property of similarity searches for quadratic distance, high dimensional feature spaces, is addressed using a hierarchical similarity indexing algorithm based on SVD (Singular Value Decomposition), which first does a low cost approximate search in the most significant subspace based on similarity indexing and then does the exact search in the high dimensional feature space on the results filtered through the first step. Experiments demonstrate the applicability, performance and real time effectiveness of our approach even in high dimensions such as 512.

关 键 词：特征空间 二次型距离相似索引层次算法 单值分解 多媒体数据库 二次型距离函数 近似检索 

分 类 号：TP311.134[自动化与计算机技术—计算机软件与理论] TP391.3[自动化与计算机技术—计算机科学与技术]