DiskANN 是一种基于图的算法，专为对无法放入内存的大型数据集进行近似最近邻 (ANN) 搜索而设计。 它通过将大部分索引存储在磁盘上，同时将一小部分频繁访问的部分保存在内存中，从而解决了高效搜索高维数据（如来自图像或文本嵌入的向量）的挑战。 与需要整个索引驻留在 RAM 中的内存 ANN 方法（例如，HNSW 或 FAISS）不同，DiskANN 利用磁盘存储来处理海量数据集。 其核心思想是将数据组织成图结构，其中节点表示数据点，边将每个节点连接到其最近邻。 在搜索期间，该算法会导航此图，根据需要从磁盘将必要的节点加载到内存中，从而最大限度地减少昂贵的磁盘读取。
该算法的工作原理是首先构建一个图，其中每个节点都链接到其近似最近邻。 在查询期间，搜索从一个或多个入口点开始并遍历该图，将查询向量与附近的节点进行比较。 由于图存储在磁盘上，DiskANN 使用缓存机制将最近访问的节点保存在内存中，从而减少重复的磁盘访问。 例如，在搜索十亿规模的图像数据集时，DiskANN 最初可能会将 1% 的图加载到内存中，然后随着遍历的进行从磁盘获取其他节点。 这种方法确保即使在 RAM 有限的情况下，系统也可以通过牺牲一些速度（由于磁盘延迟）来换取可扩展性来处理大型数据集。 优化（例如，优先考虑缓存中的高阶节点或使用 SSD 来加快磁盘访问速度）可以进一步提高性能。
DiskANN 通过可配置的参数来平衡准确性、速度和内存使用量。 例如，增加每个节点的边数可以提高搜索准确性，但需要更多的磁盘空间和 I/O 操作。 开发人员可以调整缓存大小以匹配可用内存：更大的缓存会减少磁盘读取，但会使用更多的 RAM。 一个实际的用例是推荐系统，其中嵌入数据集超过 TB 级别，DiskANN 允许查询这些数据集，而无需昂贵的 RAM 密集型服务器。 但是，其性能取决于磁盘速度，使其不太适合实时应用程序，除非与快速存储配对使用。 通过专注于磁盘友好的图遍历和智能缓存，DiskANN 能够为传统内存方法无法处理的数据集实现可扩展的 ANN 搜索。