刘丹青，李明勇

（1东华大学 计算机科学与技术学院，上海 201620；2上海市计算机软件评测重点实验室，上海 200235）

0 引 言

随着互联网的快速发展，计算机技术已渗入到社会的各种行业。因此，高维的文本、图片、视频等多媒体数据呈现爆炸式的增长趋势［1］。传统的暴力搜索方法是通过遍历所有的数据点进行查询，随着数据集的增大，这种暴力搜索方法需要巨大的存储空间，并且每次检索的时间很长。因此，该方法只适用于小规模的数据集。针对大规模高维数据集的查询问题，研究者们提出了近似最近邻搜索方法，在可接受一定精度损失的情况下，查询到尽可能精确的结果。其中，基于向量量化的近似最近邻搜索方法是比较有效和受关注较多的方法之一。该方法可以有效地降低空间存储，提高检索速度。

向量量化［2］的基本思想是，仅用数据集特征向量空间中的一个有限子集，表示该数据集特征向量空间中所有数据集特征向量，因而大大减少了数据的内存存储。常用的向量量化方法有树搜索向量量化方法、乘积量化方法［3］和多阶段向量量化方法［4-5］等。本文着重研究多阶段向量量化方法，并对基于多阶段向量量化的近似最近邻搜索方法提出改进。在训练码本过程中，通过优化初始聚类中心，减小重构向量的均方误差，改善码本质量，进一步减小向量的量化误差，以此提高实验召回率。

1 相关工作

1.1 最近邻搜索

最近邻搜索在计算机视觉、多媒体搜索、机器学习等领域里应用非常广泛。……