一种高维矢量数据快速相似检索方法

摘要

本发明为一种高维矢量数据的快速相似性检索算法。在本发明中，提出了一种新的高维数据索引结构Ordered VA-File，它对VA-File中的近似矢量进行排序重组，将在高维空间中聚集在一起的数据尽量存储在文件的相邻位置中，并根据实际应用将Ordered VA-File自适应分割为一定数量的类，每一类的数据在文件中是连续存储的。查询时，仅选择距离查询矢量最近的几类数据进行查询处理，从而大大提高查询的效率，而且可根据实际应用对查询结果精度的不同要求调整需要查询的类数量。本发明方法可大大减少磁盘访问代价，提高查询效率。

主权项

1、一种实现高维矢量数据快速相似检索的方法，其特征在于具体步骤如下：(1)按照一定的规则将矢量近似文件中的近似矢量排序重组，该规则就是将待插入近似矢量数据插入到这样的位置：待插入的近似矢量与该位置前后各m个近似矢量的平均距离最小，称这种排序后的矢量近似文件为有序化矢量近似文件；(2)对有序化矢量近似文件中进行聚类分割，每一类的近似矢量数据在有序化矢量近似文件中是连续存储的，类内近似矢量数据的距离比较近，类间近似矢量数据的距离较远，取每一类数据的均值为类中心矢量，并将所有类中心矢量存放在主存中；(3)检索时首先计算待查询矢量和每个类中心矢量之间的距离；(4)选择距离最小的L类，计算查询矢量与上面选择的L类中的近似矢量之间的距离，选择距离最小的k个近似矢量所对应的对象作为近似k近邻查询的结果集，步骤(2)中，有序化矢量近似文件进行聚类分割采用如下算法：设包含n个矢量的有序化矢量近似文件记为将其分隔为N类的方法如下：A、计算每个近似矢量与其前一个位置的近似矢量之间的距离，记为(dist₁，dist₂，...，dist_n-1)，其中 ${\mathrm{dist}}_i=D({\overrightarrow{v}}_i,{\overrightarrow{v}}_{i-1}),$i＞0，D为矢量之间距离度量方法；B、对每个矢量，计算上面得到的距离与其前后各m个距离平均值之间的比例，记为(ratio₁，ratio₂，...，ratio_n-1)，其中 ${\mathrm{ratio}}_i={\mathrm{dist}}_i/,\underset{\max (i-m,0)\le j\le \min (i+m,n-1),j\ne i}{\Sigma {\mathrm{dist}}_j},$其中i＞0；C、选择上一步中计算得到的最大的N-1个比例对应的位置，以这N-1个位置为分割点，将整个有序化矢量近似文件分割为N类；D、求每个类中近似矢量的均值作为类中心。