量化编码的分层可通航小世界图算法

发布时间：2021-01-29 19:19

　　随着大数据和人工智能的高速发展,针对多媒体数据的结构化处理与基于内容的检索受到极大的关注,面对多媒体数据结构化后的海量高维特征向量,如何快速、准确地检索是人工智能处理大规模数据所必须解决的问题。最近提出的分层可通航小世界图HNSW检索算法在多个公开数据集取得了最佳的性能表现,但该算法存在内存开销大的问题。而基于量化编码的检索算法能够压缩数据集向量,大幅度降低内存占用。将量化编码和分层可通航小世界图算法结合,提出了2种基于量化编码改进的HNSW算法,分别是使用标量量化编码向量的HNSWSQ算法和使用乘积量化编码向量的HNSWPQ算法,2种算法使用不同的量化策略存储原始向量编码,以降低内存开销,再通过HNSW算法建立索引达到缩短检索耗时的目的。其中HNSWSQ算法在多个数据集上获得了与HNSW算法相近的查全率和平均检索耗时,而内存开销大幅降低。实验结果表明,HNSWSQ算法在SIFT-1M和GIST-1M数据集上的内存开销比HNSW算法分别降低了45.1%和70.4%。 

【文章来源】：计算机工程与科学. 2019,41(04)北大核心

【文章页数】：8 页

【部分图文】：

图１ＨＮＳＷ算法查找过程Ｆｉｇｕｒｅ１ＳｅａｒｃｈｐｒｏｃｅｓｓｏｆｔｈｅＨＮＳＷａｌｇｏｒｉｔｈｍ

１２８维，设置乘积量化的参数为ｍ＝１６，ｋ＊＝２５６，则每个向量被量化为１６个字节，相比于原始的１２８＊４＝５１２字节，理论上内存消耗最多降低为原来的１／３２，如图２所示。ＨＮＳＷＰＱ算法将ＨＮＳＷ算法作为索引算法，采用ＰＱ算法进行向量编码，由于使用ＰＱ算法对原始向量编码，需要将ＨＮＳＷ算法插入过程中与近邻点距离的计算相应地修改为ＰＱ的距离计算。Ｆｉｇｕｒｅ２ＡＰＱｑｕａｎｔｉｚａｔｉｏｎｅｘａｍｐｌｅ图２ＰＱ量化示例图数据集中的向量被编码后存储在内存中，每个向量根据子向量最近邻中心点的编号编码。李秋珍等：量化编码的分层可通航小世界图算法１２６

ＨＮＳＷ算法构建索引计算查询向量与图中点ｙ的距离时，首先计算查询向量每个子向量与对应分段中心点的距离表，然后根据ｙ的编码查表获得ｄ（ｘ，ｙ）的近似值。图３是向量维数ｄ＝１６，乘积量化参数ｍ＝４，ｋ＊＝８时计算查询向量ｘ与数据集中向量ｙ的距离的例子。Ｆｉｇｕｒｅ３ＡＰＱｄｉｓｔａｎｃｅｃｏｍｐｕｔｉｎｇｅｘａｍｐｌｅ图３ＰＱ距离计算示例图Ｆｉｇｕｒｅ４Ａｓｃａｌａｒｑｕａｎｔｉｚａｔｉｏｎｃｏｍｐｕｔｉｎｇｅｘａｍｐｌｅ图４标量量化计算示例图４．２ＨＮＳＷＳＱ算法标量量化（ＳＱ）对向量的每一维量化，分层可通航小世界标量量化ＨＮＳＷＳＱ（ＨｉｅｒａｒｃｈｉｃａｌＮａｖｉｇａ－ｂｌｅＳｍａｌｌＷｏｒｌｄＳｃａｌａｒＱｕａｎｔｉｚａｔｉｏｎ）算法采用最大最小量化。对于向量的第ｉ维，通过样本集训练获取该维出现的最大值ｖｍａｘ［ｉ］和最小值ｖｍｉｎ［ｉ］，然后将向量ｘ第ｉ维的值量化为（ｘｉ－ｖｍｉｎ［ｉ］）／（ｖｍａｘ［ｉ］），ｉ＝１，…，ｎ，量化后的值编码存储，假设每一维编码为１个字节，则进一步处理为：ｆ（ｘｉ）＝φｘｉ－ｖｍｉｎ［ｉ］ｖｍａｘ［ｉ（）］＊２５５（３）其中，φ（ｘ）＝１，ｘ≥１ｘ，０＜ｘ＜１０，ｘ≤烅烄烆０，·表示向下取整。标量量化计算示例如图４所示。从图４可以看到，对于４维的原始向量，每一维编码为１个字节，则编码后向量长度为４字节，相比于编码前的１６


本文编号：3007455