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

Authors:
  • MWMengzhao Wang
    Mengzhao Wang
  • WXWeizhi Xu
    Weizhi Xu
  • XYXiaomeng Yi
    Xiaomeng Yi
  • SWSonglin Wu
    Songlin Wu
  • ZPZhangyang Peng
    Zhangyang Peng
  • XKXiangyu Ke
    Xiangyu Ke
  • YGYunjun Gao
    Yunjun Gao
  • XXXiaoliang Xu
    Xiaoliang Xu
  • RGRentong Guo
    Rentong Guo
  • CXCharles Xie
    Charles Xie

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.

This publication has 35 references indexed in Scilit: