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

New high-dimensional indexing structure based on principal component sorting

利用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.