Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment
Top Cited Papers
Open Access
- 12 March 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (1) , 1-27
Abstract
High-dimensional vector similarity search (HVSS) is gaining prominence as a powerful tool for various data science and AI applications. As vector data scales up, in-memory indexes pose a significant challenge due to the substantial increase in main memory requirements. A potential solution involves leveraging disk-based implementation, which stores and searches vector data on high-performance devices like NVMe SSDs. However, implementing HVSS for data segments proves to be intricate in vector databases where a single machine comprises multiple segments for system scalability. In this context, each segment operates with limited memory and disk space, necessitating a delicate balance between accuracy, efficiency, and space cost. Existing disk-based methods fall short as they do not holistically address all these requirements simultaneously. In this paper, we present Starling, an I/O-efficient disk-resident graph index framework that optimizes data layout and search strategy within the segment. It has two primary components: (1) a data layout incorporating an in-memory navigation graph and a reordered disk-based graph with enhanced locality, reducing the search path length and minimizing disk bandwidth wastage; and (2) a block search strategy designed to minimize costly disk I/O operations during vector query execution. Through extensive experiments, we validate the effectiveness, efficiency, and scalability of Starling. On a data segment with 2GB memory and 10GB disk capacity, Starling can accommodate up to 33 million vectors in 128 dimensions, offering HVSS with over 0.9 average precision and top-10 recall rate, and latency under 1 millisecond. The results showcase Starling's superior performance, exhibiting 43.9x higher throughput with 98% lower query latency compared to state-of-the-art methods while maintaining the same level of accuracy.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (62025206,U23A20296)
- Primary Research and Development Plan of Zhejiang Province (2023C03198,2021C03156)
This publication has 48 references indexed in Scilit:
- 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
- Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and ImprovementIEEE Transactions on Knowledge and Data Engineering, 2019
- Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World GraphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2018
- Learning Cross-Modal Embeddings for Cooking Recipes and Food Images2017
- Reversed CF: A fast collaborative filtering algorithm using a k-nearest neighbor graphExpert Systems with Applications, 2015
- Scalable Nearest Neighbor Algorithms for High Dimensional DataIEEE Transactions on Pattern Analysis and Machine Intelligence, 2014
- Hashing Algorithms and Data Structures for Rapid Searches of Fingerprint VectorsJournal of Chemical Information and Modeling, 2010
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- Balanced graph partitioning2004