近年来,近似最近邻检索成为数据挖掘领域的重点研究问题。近似最近邻检索是指在一定的检索精度损失范围内,尽可能高效地在数据集中找到与给定查询向量相近的数据,其中采用向量之间欧氏距离作为度量标准。近似最近邻检索分为量化和二值哈希的检索算法。本文主要研究了基于量化的检索算法的优化问题,主要内容包含:首先,本文研究了基于倒排索引的检索算法的优化方法,提出了邻居极性的概念和局部分区再分割算法。局部分区再分割算法利用邻居极性作为判定标准,解决了基于倒排索引的检索算法在面对海量高维数据集时为了维持检索精度需要耗费大量时间成本的问题,提高了基于倒排索引算法的近似最近邻检索效率。实验表明,局部分区再分割算法在对检索精度无影响的前提下,明显地提升了近似最近邻的检索效率。其次,本文研究了基于乘积量化子码本生成过程的优化算法,提出了基于误差平方和的子码本生成算法以及基于层次化聚类的子码本生成算法。基于误差平方和的子码本生成算法中引入滑动窗口的思想,通过计算乘积量化算法子码本生成过程中使用的K-Means聚类算法的误差平方和,确定合适的子码本大小。基于层次化聚类的子码本生成算法中通过对子空间进行一次层次化预聚类,确定后续子码本生成过程中K-Means聚类算法的K值以及初始簇心。实验表明,基于误差平方和的子码本生成算法能够在保证近似最近邻检索准确率前提下,尽可能地减小码本的大小,从而能够降低时间成本。基于层次化聚类的子码本生成算法通过预聚类确定初始簇心后,近似最近邻检索准确率明显高于同样子码本大小的经典乘积量化算法。再次,本文研究了基于乘积量化的子空间划分过程的优化算法。子空间划分过程的优化算法致力于寻找总体离散程度较小的子空间划分方式,离散程度较小的子空间在进行K-Means聚类算法时能够获得误差平方和较小的类簇,进而使得子码本能够实现更好的量化效果。优化的子空间划分算法利用方差找到整体离散程度最小的子空间组合,将重新组合的子空间进行乘积量化。实验表明,优化的子空间划分算法能够明显地提升近似最近邻检索准确率。最后,我们在真实数据集上对本文提出的子码本生成优化算法以及优化的子空间划分算法进行了结合实验。实验结果表明:基于层次化聚类的子码本生成算法与优化的子空间划分算法结合后,近似最近邻检索准确率高于单一的任意一种优化算法,并且明显优于经典乘积量化算法。