近似最近邻搜索问题是数据库、数据挖掘、人工智能等领域中的一个基本问题。一个具有实际应用价值的近似最近邻搜索算法必须同时具有极高的搜索速度以及合理的内存用量。相比于传统的基于树结构、基于哈希和基于量化的搜索算法,基于图索引的近似最近邻搜索算法因其搜索高且速度快的特点,吸引了来自学术界和工业界的大量关注。虽然许多早期的基于图结构的近似最近邻搜索算法算法在理论上具有十分低的搜索时间复杂度,但这些图结构索引的索引构建算法往往具有极高的时间复杂度,从而使其在目前的大数据时代场景中无法有效应用。因此近年来学界提出了诸多新的图结构索引,以期能够降低索引构建的时间复杂度。虽然这些方法取得了许多革命性的进步,但其仍旧不够高效从而限制了其在更大规模数据集上的应用。本文结合近年来的最新研究成果,对图结构索引进行了更深入的探究,以希望能够更有效地解决上述困难。具体来讲,本文从以下四个方面出发对用于近似最近邻搜索的图结构进行了探究:(1)保证图的连通性;(2)降低图中节点的平均出度已获得更快的遍历速度;(3)降低查询在图上的搜索路径长度;(4)减小基于图结构的索引的大小。基于以上四点,本文在理论上提出了一种全新的图结构——单调相对近邻图(Monotonic Relative Neighborhood Graph,MRNG),这种图结构在理论上具有极低的搜索复杂度(接近对数时间复杂度)。但直接构造MRNG的算法复杂度过高,使其在超大规模数据上不具有实际可行性。为此本文提出了另一种全新的称为“导向性分散伸展图(Navigating Spreading-out Graph,NSG)”的图结构用以近似MRNG,从而实现了一种同时具有高效索引构建与搜索性能的全新近似最近邻搜索算法。本文在SIFT1M、GIST1M等多个百万级数据集上对NSG算法进行了充分的实验验证,并在这些数据集上与现有主流算法进行横向对比试验,从而证明NSG在索引构建速度与搜索速度精度等具有巨大的优越性。最后本文提出了一种可用于工业场景的基于NSG的超大规模快速近似最近邻搜索系统设计方案,并在亿级数据集上对其可行性进行了初步验证。