EUVIMEDEUVIMED entdecken
Crossref

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

Mengzhao Wang, Weizhi Xu, Xiaomeng Yi, Songlin Wu, Zhangyang Peng, Xiangyu Ke, Yunjun Gao, Xiaoliang Xu, Rentong Guo, Charles Xie

Proceedings of the ACM on Management of Data · 12.03.2024 · 2 (1) · 1-27

DOI: 10.1145/3639269 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 26.03.2024. Verfasst von Mengzhao Wang und 9 weiteren Autor:innen. Die Arbeit wurde bisher 72-mal zitiert (Crossref) und nennt 74 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Primary Research and Development Plan of Zhejiang Province.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • National Natural Science Foundation of China
  • Primary Research and Development Plan of Zhejiang Province

Zitieren

APA

Wang, M., Xu, W., Yi, X., Wu, S., Peng, Z., Ke, X., Gao, Y., Xu, X., Guo, R., & Xie, C. (2024). Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment. Proceedings of the ACM on Management of Data, 2(1), 1-27. https://doi.org/10.1145/3639269

Vancouver

Wang M, Xu W, Yi X, Wu S, Peng Z, Ke X, et al. Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment. Proceedings of the ACM on Management of Data. 2024;2(1):1-27. doi:10.1145/3639269

BibTeX
@article{Wang2024,
  author = {Wang, Mengzhao and Xu, Weizhi and Yi, Xiaomeng and Wu, Songlin and Peng, Zhangyang and Ke, Xiangyu and Gao, Yunjun and Xu, Xiaoliang and Guo, Rentong and Xie, Charles},
  title = {Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2024},
  volume = {2},
  number = {1},
  pages = {1--27},
  doi = {10.1145/3639269}
}
Kostenlos starten →