随着互联网的高速发展,产生了数量庞大的多媒体信息,对数据挖掘技术提出更高的要求。近似最近邻检索（Approximate Nearest Neighbor,ANN）作为数据挖掘中的一个基本问题也是热门问题,旨在从海量数据中快速检索到最相似的数据。但是随着数据维度的增长,传统的基于树的检索方法和基于哈希的检索方法的检索速度和精度,已经不能满足要求。目前基于图的检索方法有着不错的表现,但是仍存在索引构建时间长,索引结构大等问题。本文对基于图的检索方法进行深入研究,提高近邻检索的效率。传统的基于图的检索方法在面对大规模高维数据时,存在索引构建时间长,索引结构庞大的问题。本文提出先对数据进行快速粗略的划分,再对聚簇中心建图的方法,避免直接在原始数据集上建立图索引,可以显著降低索引的构建时间和缩小索引结构。为了提高图索引的质量,采用在预先构建好的knn图上创建新的图索引的方式,用新建的图索引逐步替换掉knn图,索引的结构更加紧凑,可以提高检索精度,并且缩短了检索路径,使得检索速度可以提高。传统的基于图的检索方法都是直接使用原始数据进行距离计算,对候选结果排序,计算量大,并且占用较多的内存空间。采用二次线量化的方式,对原始向量进行量化,压缩了原始数据,可以减少内存空间的占用,降低向量之间距离计算复杂度,并且不依赖查询向量的计算可以提前算出来,提高检索时的速度。在不同数据集上的测试结果表明,论文中设计的算法在保证高检索精度的同时,检索速度更快,索引结构更小。该算法在SIFT1M数据集上的表现,相比于分层可导航小世界图算法,在相同精度下,查询时间降低30%,索引结构缩小45%。