Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment

高维向量相似度搜索（HVSS）作为各种数据科学和人工智能应用的强大工具，正受到关注。随着向量数据的增长，内存索引变得极其昂贵，因为它们需要大量扩展主内存资源。一种可能的解决方案是使用基于磁盘的实现，它将向量数据存储在高性能设备（如NVMe SSD）中进行搜索。然而，在向量数据库中，数据片段的HVSS仍然具有挑战性，因为一个机器具有多个片段用于系统特征（如扩展）的目的。在这种情况下，每个片段的内存和磁盘空间都很有限，因此需要在数据片段上平衡准确性、效率和空间成本。现有的基于磁盘的方法是次优的，因为它们没有同时考虑所有这些要求。在本文中，我们提出了Starling，一种I/O高效的磁盘驻留图形索引框架，它优化了片段中的数据布局和搜索策略。它有两个主要组成部分：（1）数据布局，包括一个内存导航图和一个重新排序的基于磁盘的图形，具有局部增强功能，可以减少搜索路径长度和磁盘带宽浪费；（2）块搜索策略，可以在执行向量查询时最小化昂贵的磁盘I/O。我们进行了大量实验来验证Starling的有效性、效率和可扩展性。在具有2GB内存和10GB磁盘容量的数据片段上，Starling可以维护128维中高达3300万个向量，并提供平均精度超过0.9和前10个召回率的HVSS，延迟低于1毫秒。结果表明，与同等准确性的最先进方法相比，Starling表现出43.9倍的吞吐量和98%的查询延迟降低。

解决问题：论文提出了一种解决高维向量相似度搜索的问题的方法，针对数据量大、内存资源有限的情况，提出了一种基于磁盘的实现方案。

关键思路：论文提出了一种名为Starling的I/O-efficient磁盘图形索引框架，通过优化数据布局和搜索策略来实现高效的相似度搜索。其中数据布局包括内存导航图和重新排序的基于磁盘的图形，搜索策略则通过最小化昂贵的磁盘I/O来执行向量查询。

其他亮点：论文通过实验验证了Starling的有效性、效率和可扩展性，能够在内存为2GB、磁盘容量为10GB的数据段中维护多达3300万个128维向量，并以0.9以上的平均精度和Top-10召回率提供HVSS服务，延迟低于1毫秒。实验结果表明，Starling在相同准确性下，比同类方法表现出43.9倍的吞吐量和98%的查询延迟降低。

相关研究：近期的相关研究包括基于内存的高维向量索引方法（如FAISS和Annoy），以及基于磁盘的索引方法（如PQ索引和LSH索引）。