一种新的基于主分量排序的高维索引结构  

New high-dimensional indexing structure based on principal component sorting

作　　者：崔江涛[1] 付少锋[1] 詹海生[1] 周利华[1] 

机构地区：[1]西安电子科技大学计算机学院,陕西西安710071

出　　处：《系统工程与电子技术》2006年第12期1927-1931,共5页Systems Engineering and Electronics

基　　金："十五"国防科技(电子)预研基金资助课题(413160501)

摘　　要：利用KL变换的能量集中特性,改进了向量近似方法中的索引结构。在KL变换域上建立近似向量,选择能量最大的分量作为主分量,根据主分量值对近似向量进行顺序排列,并且用B+树存储每个数据页面中主分量值的范围。在k近邻搜索过程中,采用变换域部分失真搜索算法,从初始访问数据页面开始在升序和降序两个方向上顺序访问近似向量。改进的索引结构既保持了顺序访问特性,又大幅度降低了数据页面访问数量。在大型高维图像特征库上的实验表明,新的索引结构不仅降低了搜索过程的I/O时间,而且提高了CPU搜索速度。The vector approximation approach is an efficient high-dimensional indexing method to overcome the difficulty of ‘curse of dimensionality＇. A new high-dimensional indexing structure based on vector approximation method is introduced. The approximate vector is built at the KL transform domain, and the first component is chosen as the principal component. A sequence index is built based on the principal component, which uses B^＋ tree to manage the approximate vectors. In the k-nearest neighbor search, the partial distortion searching algorithm is used to reject the improper approximate vectors. Only a small set of approximate vectors are ac cessed during the search, which reduces the computational complexity and I/O cost. The experimental results on large image databases show that the new approach renders a higher search speed than the well-known VA^＋ -file approach.

关 键 词：高维索引 向量近似 近邻搜索 KL变换 主分量排序 

分 类 号：TP311.134.3[自动化与计算机技术—计算机软件与理论]