随着信息技术的不断发展,数据处理量不断增大,如何在海量、高维度的数据集中进行快速搜索显得越来越重要。数十年来,近似最近邻搜索（Approximate Nearest Neighbor,简称ANNS）一直是一个热门话题,它在数据挖掘,机器学习和人工智能的许多应用中发挥着重要作用。对于稀疏的离散数据（比如文档）,用户可以构建高级索引结构（比如倒排索引）来进行有效地最近邻搜索。但是对于密集的连续向量,目前主要有四种类型的方法:基于树结构的方法,基于哈希的方法,基于量化的方法和基于图的方法,其中基于图的方法因高准确度和低查询复杂度而备受关注。实验结果表明,基于图的方法在欧几里得空间中的性能要优于其它流行算法,原因是基于图的方法相比其它方法更能够准确的表达近邻关系。在达到相同搜索精度的情况下,非图的方法需要检查更多的邻居节点,从而使得搜索性能较差。由于图在ANNS的性能上表现突出,许多学者转向基于图的研究。不同的基于图的方法使用不同的构建策略,一种被广泛采用的构建理念就是使图尽可能的稀疏,从而来减少查询代价。本文通过研究发现稀疏图并不能保证查询的高精度（接近或等于100%）,或者在高精度区域需要高额计算的开销。为此,本文使用了一种新颖的边缘选择策略来构建图,并将之命名为查询导向稠密图（Query-Directed Dense Graph,简称QDG）,在该图的基础上使用基于查询导向的方法进行高效查询,极大地降低了查询开销。QDG的构建和查询过程详细介绍如下:（1）首先构建QDG索引需要初始化的k近邻（k-nearest neighbor,简称k NN）图,现如今这种k NN图有很多方法可以得到,例如NNdescent,KGraph或Faiss。在初始k NN图上,本文通过计算数据集的近似中心（称之为导航节点）得到初始节点,从初始节点开始使用贪婪搜索的方法为图上的每一个节点选择邻居候选集合。本文提出了一种新的边缘选择策略,通过调节节点邻居之间的最小角度来保证创建更稠密的图。根据图论知识可知,图的连通性和图的平均出度相关,尽管稠密图可能会导致搜索复杂度增大,但是它同样增大了图网络的连通性。（2）为了减少查询复杂度,本文采用了经典的K-means方法,对于图上的每一个节点利用余弦距离将其邻居集合进行聚类,这样角度相近的邻居便聚为一类。虽然图本身是稠密的,但是在查询过程中,算法仅仅去检查和查询点的角度接近的部分邻居,以减少查询代价。（3）由于聚类中心本身的存储代价较大,本文使用乘积量化（Product Quantization,简称PQ）的变体将K-means聚类得到的聚类中心以编码的形式存储,通过预计算表得到重构聚类中心来计算该聚类中心和查询点的角度,以此来优化空间和时间性能。通过在不同数据集（来源于真实生活中）上的实验发现,本文提出的方法在查询时间上最多提高了2.2倍。并且由于该方法基于贪婪搜索算法,它同样可以移植到大多数基于图的搜索算法上,并显示出良好的性能。