[发明专利]基于混合向量量化的最近邻搜索方法

摘要

基于混合向量量化的最近邻搜索方法，涉及信息检索与多媒体检索。该类方法与现有向量量化方法不同的是，它对低阶余向量(一阶为原向量)采用传统余向量量化方式，而对高阶余向量，将它的方向向量和能量分别量化。一方面，向量量化后的低阶码将用来生成倒排索引结构的索引键值；另一方面，对每一高阶余向量进行分解。把一个向量分解为方向向量和能量。对方向向量和能量分别量化。与其他已有的量化方法相比，该方法训练码本以及量化过程都比目前的方法简单，同时取得较好的编码准确率。

主权项

基于混合向量量化的最近邻搜索方法，其特征在于包括以下步骤：1)混合向量量化的编码方法：给定一个向量v∈RD,对其前i阶的余向量(第一阶为向量本身)进行余向量量化，后面j阶的每阶余向量对其方向向量(归一化后的向量)和能量分别编码；假设i＝2，j＝2，则其编码形式如下：v≈ωi1(1)+ωi2(2)+e0·(p1·ωi3(3)+e1·(p2·ωi4(4)))---(1)]]>在公式(1)中，和分别是第一和第二阶码本中距离余向量最近的单词，e0和e1分别是后两阶能量码本中距离能量最近的单词，和分别是后两阶方向码本中距离方向向量最近的单词，p1和p2分别是后两阶的方向向量在其最近的单词上的投影；在编码中，设总的编码阶数为n，即n＝i+j，则其中i由具体的问题确定，若待检索的数据集很大，则i的值大；因为前面i阶将用作生成倒排索引结构的索引，i值越大所能生成的索引值越多，可以索引的数据量也越大；目的是把数据集尽量打散，保证每次最近邻查询都只访问少量的候选向量；2)基于低阶余向量量化编码的倒排索引结构：(1)设采用四阶编码，即n＝4，经过步骤1)，输入向量q将编码为c1c2c3h0c4h1；其中，c1c2为余向量量化后的编码，这两个编码将合并作为倒排表的索引键值，即I＝c1c2，而余下的编码将存放在倒排表该索引键值所对应的链表中；(2)链表的每一项存放了候选向量的标记和余下的高阶编码，例如n＝4情形下链表中每个候选项为＜ID,c3h0c4h1＞；3)基于层级剪枝的在线搜索策略：(1)给定查询点q，搜索过程首先计算查询点q到每一个倒排索引键值的距离，这时需要把键值I拆分为c1和c2，c1和c2分别对应第一阶码本中的向量和和第二阶码本中的向量计算查询q到I的距离，转化为计算q到合成向量之间的距离，即可以写为如下形式：在公式(2)的计算中，为了加快计算速度，可以先算q到的距离，即公式(2)中的term1，这样可以得到q到第一阶每个码的距离，根据q到每个码的距离排序；忽略排在后面95％的一阶码对对应的索引项，对于剩下的5％的一阶码，进一步计算q到两阶编码所得到组合向量VI的距离，同样地，当计算q到所有两阶编码之间的距离之后，可以根据这一距离排序，然后忽略排在后面90％的索引项，即只考虑倒排表中排在前面的链表，进行查找，这一方式可以扩展到i＞2的情形；在公式(2)的计算中，和可以预先计算，然后通过查表获得；因此公式(2)的计算可以快速实现；(2)经步骤(1)之后，查询计算q到候选链表中每一个候选项的距离，计算的公式如下，注意到公式(2)的计算结果可以加入到公式(3)的计算中以加快计算速度：d(q,v)=||q-v||22=q·qt-2·v·qt+v·vt=q·qt-2·(ωi1(1)·qt+ωi2(2)·qt+e0·(p1·ωi3(3)·qt+e1·p2·ωi4(4)·qt))+v·vt=q·qt+v·vt-2·(d(q,I)+e0·(p1·ωi3(3)·qt+e1·p2·ωi4(4)·qt))---(3)]]>(3)步骤(2)之后，查询将获得q到经过混合编码的候选向量的距离，查询对距离排序，然后输出。