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个召回率，并具有小于1毫秒的延迟。结果展示了Starling的卓越性能，相比于最先进的方法，它展示了43.9倍的吞吐量和98%的查询延迟降低，同时保持相同的准确性。

Starling论文旨在解决高维向量相似性搜索(HVSS)中内存索引所面临的主内存需求过高的问题，提出了一种基于磁盘的实现方案。同时，该论文也解决了在向量数据库中，单个机器包含多个数据段的情况下，如何在有限的内存和磁盘空间内实现高效率的搜索。

Starling提出了一种数据布局方案，其中包括一个内存导航图和一个重新排序的基于磁盘的图形，以增强局部性，减少搜索路径长度和最小化磁盘带宽浪费。此外，它还提出了一种块搜索策略，旨在在向量查询执行期间最小化昂贵的磁盘I/O操作。

论文通过实验验证了Starling的有效性、效率和可扩展性。在具有2GB内存和10GB磁盘容量的数据段上，Starling可以容纳多达3300万个128维向量，提供平均精度超过0.9和前10个召回率，并且延迟低于1毫秒。与现有方法相比，Starling具有更高的吞吐量和更低的查询延迟，同时保持相同的准确性。

近期的相关研究包括：'Efficient kNN Search on Streaming Data with Approximate Metric'、'Fast Similarity Search in Large Databases Using Neural Networks'、'Deep Metric Learning for Similarity Search and Person Re-Identification'等。