张万麒，王永利，陈广生

(1.南京理工大学 计算机科学与工程学院， 江苏 南京 210094；2.华电能源股份有限公司 佳木斯热电厂， 黑龙江 佳木斯 154000)

0 引 言

相似性查询，亦称为最近邻(NN)查询，由于维数灾难，对于高维数据而言，准确的最近邻查询是极具挑战的问题。为了尽可能用较少的查询时间和内存损耗发现最近邻，从而解决高维数据的最近邻查询问题，相关领域出现许多有关近似最近邻(ANN)查询方法的研究，例如哈希、基于树方法、矢量量化等方法。

本文研究的是近似最近邻查询中的矢量量化(VQ)方法，对于ANN查询来说是一个典型高效的数据编码方法。VQ需要更多位数来减少量化误差。但随着编码位数增加，码本大小也呈指数级增长，基于VQ的方法对于高维数据来说作用效果不明显。为了解决这个问题，乘积量化(PQ)[1]给出一个高效索引高维图像特征的范例。采取将高维特征空间分解成低维特征子空间的笛卡尔积的形式，然后分别进行量化。因为每个子空间维数相对较小，使用一个小尺寸码本很容易获取到令人满意的查询效果。尽管将长矢量分解成子部分的形式会使计算损耗明显减少，但由于高量化误差，PQ不能在高精准度情况下检索一个查询值的确切最近邻。目前已有一些方法来解决这个问题。Gong和Lazebnik[2]提出一种迭代量化的方法，将数据映射成二进制编码来进行快速检索。Cartesian K-means[3]和Optimized Product Quantization[4]两种方法采用了旋转原始数据的方法来减小量化误差。但包括PQ在内的这些方法均遵循着VQ的基本原理，都不可避免地造成了高量化误差。……