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

arXiv: https://arxiv.org/abs/2401.02116 · HTML: https://mlsanity.com/paper/2401.02116/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jan 2024.

## Built on by (most cited first, 17 of 17)

- [TFB: Towards Comprehensive and Fair Benchmarking of Time Series Forecasting Methods](https://mlsanity.com/paper/2403.20150/) (2024)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [An Interactive Multi-modal Query Answering System with Retrieval-Augmented Large Language Models](https://mlsanity.com/paper/2407.04217/) (2024)
- [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025)
- [Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search](https://mlsanity.com/paper/2508.01405/) (2025)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [HAKES: Scalable Vector Database for Embedding Search Service](https://mlsanity.com/paper/2505.12524/) (2025)
- [Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph](https://mlsanity.com/paper/2509.25487/) (2025)
- [CaGR-RAG: Context-aware Query Grouping for Disk-based Vector Search in RAG Systems](https://mlsanity.com/paper/2505.01164/) (2025)
- [GEM: A Native Graph-based Index for Multi-Vector Retrieval](https://mlsanity.com/paper/2603.20336/) (2026)
- [All-in-one Graph-based Indexing for Hybrid Search on GPUs](https://mlsanity.com/paper/2511.00855/) (2025)
- [Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN](https://mlsanity.com/paper/2512.09331/) (2025)
- [Efficient K-generalizable Learned Search](https://mlsanity.com/paper/2603.06159/) (2026)
- [CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data](https://mlsanity.com/paper/2604.06616/) (2026)
- [Stellar: Scalable Multimodal Document Retrieval for Natural Language Queries](https://mlsanity.com/paper/2606.19960/) (2026)
- [Akashic: A Low-Overhead LLM Inference Service with MemAttention](https://mlsanity.com/paper/2607.05708/) (2026)

## Abstract (arXiv)

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.9× higher throughput with 98% lower query latency compared to state-of-the-art methods while maintaining the same level of accuracy.