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

摘要

利用KL变换的能量集中特性,改进了向量近似方法中的索引结构.在KL变换域上建立近似向量,选择能量最大的分量作为主分量,根据主分量值对近似向量进行顺序排列,并且用B+树存储每个数据页面中主分量值的范围.在k近邻搜索过程中,采用变换域部分失真搜索算法,从初始访问数据页面开始在升序和降序两个方向上顺序访问近似向量.改进的索引结构既保持了顺序访问特性,又大幅度降低了数据页面访问数量.在大型高维图像特征库上的实验表明,新的索引结构不仅降低了搜索过程的I/O时间,而且提高了CPU搜索速度.