| 引用本文: | 周依杰,林圣原,巩树凤,余松,范书豪,张岩峰,于戈.GoVector: I/O-高效的高维向量近邻查询缓存策略.软件学报,2026,37(3):1021-1036 |
| |
|
| |
|
|
| 本文已被：浏览 1731次 下载 1177次 |
码上扫一扫！ |
|
|
| GoVector: I/O-高效的高维向量近邻查询缓存策略 |
|
周依杰, 林圣原, 巩树凤, 余松, 范书豪, 张岩峰, 于戈
|
|
东北大学 计算机科学与工程学院, 辽宁 沈阳 110819
|
|
| 摘要: |
| 基于图结构的高维向量索引 (索引图)因其高效的近似最近邻搜索能力, 已成为大规模向量检索的主流方法. 索引图执行近似最近邻搜索 (approximate nearest neighbor search, ANNS)的过程分为两个阶段: 第1阶段从入口点出发快速定位到查询向量附近区域; 第2阶段在查询向量附近搜索离其最近的k个向量. 然而, 由于索引图需存储大量邻接关系, 导致内存开销大, 因此实际部署时通常需将其存储于外存. 当执行近似最近邻搜索时, 按需加载索引图和向量数据会导致频繁发生I/O操作, 并成为检索性能的主要瓶颈 (I/O时间占90%以上). 现有系统利用入口点及其附近邻居被高频访问的特性, 采用静态缓存策略将入口点及其若干跳邻居预先缓存在内存中, 以减少第1阶段的I/O访问. 然而分析发现, 第2阶段为了获取更高精度的检索结果, 需访问大量与查询向量相关的图顶点, 成为I/O开销的主要来源. 由于第2阶段的访问顶点随查询向量动态变化, 现有静态缓存策略难以有效命中, 导致其在此阶段几乎失效. 针对此问题, 设计了一个静态-动态混合缓存策略GoVector, 其核心设计体现在: (1) 静态缓存区预加载入口点及其高频近邻; (2) 动态缓存区自适应地缓存第2阶段中空间局部性高的顶点. 为了进一步适配第2阶段中以向量相似性为导向的搜索过程, 设计了基于向量空间相似性磁盘布局策略, 通过重排顶点存储顺序, 使相似向量在物理存储上聚集于相同或相邻磁盘页, 从而显著提升数据访问的局部性. 这种双重优化机制使得缓存命中率得到显著提升, 有效降低了整体I/O开销. 在多个公开数据集上的实验结果表明, 当召回率为90%时, 相较于当前最先进的基于磁盘的索引图系统, GoVector实现I/O次数平均降低46%、查询吞吐率提升1.73倍、延迟下降42%. |
| 关键词: 高维向量 近似最近邻搜索 索引图 |
| DOI：10.13328/j.cnki.jos.007518 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金 (U2241212, 62461146205); 国家社会科学基金 (21&ZD124); 中央高校基本科研业务费专项资金 (N2116005, N2116008, N2416003); CCF-华为胡杨林基金 |
|
| GoVector: I/O-efficient Caching Strategy for High-dimensional Vector Nearest Neighbor Search |
|
ZHOU Yi-Jie, LIN Sheng-Yuan, GONG Shu-Feng, YU Song, FAN Shu-Hao, ZHANG Yan-Feng, YU Ge
|
|
School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
|
| Abstract: |
| Graph-based indexes for high-dimensional vectors have become the mainstream solution for large-scale approximate nearest neighbor search (ANNS) due to their high efficiency. The search process over graph-based indexes typically consists of two stages: the first stage rapidly navigates from an entry point to a region near the query vector, while the second stage searches for the k nearest vectors within the localized region. However, due to the need to store a large number of adjacency relationships, graph-based indexes often incur high memory overhead. In practice, this leads to storing the index in external memory, where vector and graph data are loaded on demand during ANNS. This results in frequent I/O operations, which have become the primary bottleneck, accounting for over 90% of total query time. Existing systems exploit the fact that entry points and their nearby neighbors are frequently accessed, and adopt static caching strategies that preload these points and their multi-hop neighbors into memory to reduce I/O during the first stage. However, this study finds that the second stage contributes the majority of I/O cost, as it involves accessing a large number of graph vertices related to the query vector to ensure high recall. Since the accessed vertices in this stage vary dynamically with each query, static caching strategies fail to capture them effectively and thus become nearly ineffective. To address this issue, a hybrid caching strategy termed GoVector is proposed, which integrates both static and dynamic components. Specifically, (1) the static cache preloads the entry point and its frequently accessed neighbors, while (2) the dynamic cache adaptively stores high-locality vertices encountered during the second stage of the search. Furthermore, to align with the similarity-driven search behavior of the second stage, a vector-similarity-aware disk layout strategy is proposed, which reorganizes the storage order of vertices to cluster similar vectors into the same or adjacent disk pages, thus enhancing data locality. This dual-optimization approach significantly improves cache hit rates and effectively reduces overall I/O overhead. Experimental results on multiple public datasets demonstrate that, under 90% recall, GoVector achieves an average of 46% fewer I/O operations, 1.73× higher query throughput, and 42% lower latency compared to state-of-the-art disk-based graph indexing ANNS systems. |
| Key words: high-dimensional vector approximate nearest neighbor search (ANNS) graph-based index |
|
|
|
|
