Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment
Authors:
- Mengzhao WangMWMengzhao Wang
- Weizhi XuWXWeizhi Xu
- Xiaomeng YiXYXiaomeng Yi
- Songlin WuSWSonglin Wu
- Zhangyang PengZPZhangyang Peng
- Xiangyu KeXKXiangyu Ke
- Yunjun GaoYGYunjun Gao
- Xiaoliang XuXXXiaoliang Xu
- Rentong GuoRGRentong Guo
- Charles XieCXCharles Xie
Preprint
Abstract
High-dimensional vector similarity search (HVSS) is receiving a spotlight as a powerful tool for various data science and AI applications. As vector data grows larger, in-memory indexes become extremely expensive because they necessitate substantial expansion of main memory resources. One possible solution is to use disk-based implementation, which stores and searches vector data in high-performance devices like NVMe SSDs. However, HVSS for data segments is still challenging in vector databases, where one machine has multiple segments for system features (like scaling) purposes. In this setting, each segment has limited memory and disk space, so HVSS on the data segment needs to balance accuracy, efficiency, and space cost. Existing disk-based methods are sub-optimal because they do not consider all these requirements together. In this paper, we present Starling, an I/O-efficient disk-resident graph index framework that optimizes data layout and search strategy in the segment. It has two main components: (1) a data layout that includes an in-memory navigation graph and a reordered disk-based graph with locality enhancement, which reduces the search path length and disk bandwidth wastage; and (2) a block search strategy that minimizes expensive disk I/Os when executing a vector query. We conduct extensive experiments to verify Starling's effectiveness, efficiency, and scalability. On a data segment with 2GB memory and 10GB disk capacity, Starling can maintain up to 33 million vectors in 128 dimensions, and serve HVSS with more than 0.9 average precision and top-10 recall rate, and latency of under 1 millisecond. The results show that Starling exhibits 43.9$\times$ higher throughput with 98% lower query latency than state-of-the-art methods under the same accuracy.Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- Learning-based query optimization for multi-probe approximate nearest neighbor searchThe VLDB Journal, 2022
- ProMIPS: Efficient High-Dimensional c-Approximate Maximum Inner Product Search with a Lightweight Index2021
- Benchmark on Indexing Algorithms for Accelerating Molecular Similarity SearchJournal of Chemical Information and Modeling, 2020
- A novel density-based clustering algorithm using nearest neighbor graphPattern Recognition, 2020
- I/O Efficient Approximate Nearest Neighbour Search based on Learned Functions2020
- GPH: Similarity Search in Hamming Space2018
- FaceNet: A unified embedding for face recognition and clustering2015
- Reversed CF: A fast collaborative filtering algorithm using a k-nearest neighbor graphExpert Systems with Applications, 2015
- Optimized Product Quantization for Approximate Nearest Neighbor Search2013
- Hashing Algorithms and Data Structures for Rapid Searches of Fingerprint VectorsJournal of Chemical Information and Modeling, 2010