在互联网时代，大规模近似最近邻检索方法在海量多媒体数据检索，人脸识别等领域具有广泛应用。如何快速、准确、高效地对大规模(十亿级别)多媒体数据进行近似最近邻检索成为当前检索技术方向研究的热点和难点。
　　目前主流的大规模近似最近邻检索方法主要采用基于量化方法的索引结构和压缩编码方法来提高检索准确率和速度，并利用图形处理器(GPU)强大的并行计算能力对检索方法进行加速。由于GPU的内存空间有限与不同于CPU的运算机制，使得一些基于量化的近似最近邻检索方法无法在GPU上有效地运行，在GPU上的检索准确率和速度仍有很大的提升潜力。本文旨在研究如何将新的量化索引结构和量化编码方法与GPU相结合，提升近似最近邻检索方法的检索准确率和速度。
　　本文针对现有量化方法中存在的索引存储开销和压缩编码误差大以及检索准确率和速度之间存在矛盾等问题，提出了三个新的基于GPU量化的近似最近邻检索方法。
　　(1)针对乘积量化方法的索引利用率低和压缩编码量化误差大的问题，提出了矢量乘积量化树索引结构和面量化编码。矢量乘积量化树索引是矢量量化和乘积量化所组成的两层索引结构，首先使用少量的矢量量化索引将高维空间划分成若干个索引区域，然后在各索引区域内使用不同的乘积量化索引将一级索引区域进一步分成二级索引区域。一级索引区域内数据的均匀分布可以有效地提高二级索引区域的利用率，二级索引利用乘积量化方法可以用较小的存储开销产生数量巨大的索引区域。面量化编码通过将高维向量中每个子向量投影到最近的超平面上，最后将每个子向量的编码连接在一起表示该向量。由于每个超平面上的投影点都比乘积量化编码中任何一个中心点更靠近子向量，所以面量化编码相比乘积量化编码有更低的量化误差。实验结果表明，矢量乘积量化树索引较乘积量化索引的空索引区域数量减少了80%，而面量化编码的量化误差比乘积量化编码误差降低了98%。基于矢量乘积量化树索引和面量化编码的近似最近邻检索方法相比基准方法在两个10亿级别公共数据集SIFT1B和DEEP1B上的检索准确率分别提升了34%和68%。
　　(2)针对矢量量化索引结构内存开销大的问题，提出了矢量线量化索引。该索引结构在矢量量化索引的基础上引入了线量化索引，矢量量化索引将高维空间划分成一级索引区域，而第二层线量化索引能够将索引区域数量扩大数十倍，这样矢量线量化索引可以用较少的存储开销产生数量巨大的索引区域。实验结果表明，矢量线量化索引仅需要矢量量化索引1/4的存储开销就能达到更好索引质量。基于矢量线量化索引的近似最近邻检索方法比基于矢量索引的近似最近邻检索方法在准确率方面提升了14%，平均检索速度方面提升了5倍。
　　(3)针对GPU上的近似最近邻检索方法中存在的检索准确性和速度之间的矛盾性问题，提出了基于层次化量化索引的近似最近邻检索方法。检索方法通过提升量化索引的索引质量和降低距离计算的复杂度来缓解检索准确率和速度之间的矛盾。层次化量化索引是一个三层量化索引结构，通过一层矢量量化索引和两层线量化索引相结合，进一步减少了量化误差。该检索方法通过层次化量化索引结构和简化的非对称距离计算算法在一定程度上缓解了在GPU上检索方法中检索准确率和检索速度之间的矛盾。实验结果表明，与基准方法相比，基于层次化量化索引的检索方法用不到3%的准确率损失换取了100%的检索速度提升。
　　综上，本文主要研究大规模高维数据相似性检索中的GPU量化方法，提出了三种基于GPU量化的近似最近邻检索方法：基于矢量乘积量化树索引结构和面量化编码，基于矢量线量化索引和基于层次化量化索引的检索方法。在两个公共的十亿级别的数据集SIFT1B和DEEP1B上的实验表明，所提出的检索方法对比现有的近似最近邻检索方法获得了检索性能的大幅提升。