← 研踪 PaperTrailarXiv:2605.11523 · v2
NAVIS: Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search
首次提交 2026-05-12 12:47
版本更新 2026-11-08 04:20
雷达观测 2026-11-10 11:14
摘要
On-disk graph-based vector search (GVS) has become the dominant approach for serving large-scale vector databases at high recall. Yet prior systems struggle to sustain concurrent search and update throughput on high-dimensional workloads. We identify the main bottleneck as position seeking, the graph traversal that finds neighbors during each update. Unlike search, which returns only the top-K closest vectors, it explores a much larger set to build an R-neighbor list of close neighbors and long-range shortcuts. These neighbors have different distance-accuracy requirements, yet search-oriented packed layouts fetch full vectors with every edge-list access, consuming cache capacity regardless of their role. We present NAVIS, an on-SSD GVS system that redesigns position seeking around this mismatch. At its core, locality-driven decoupling separates vectors from edgelists and packs graph-local edgelists together. This decoupling enables convergence-aware speculative reranking to selectively load full vectors until a sufficient set of close neighbors is resolved, while selecting the remaining shortcuts using approximate distances. It also allows NAVIS to devote cache capacity entirely to edgelists. To make this cache effective, NAVIS keeps the entrance graph fresh via lightweight updates that reuse traversal information already produced during position seeking, thereby maintaining a stable hot set of edgelists near its entry points. Across multiple large-scale benchmarks, NAVIS improves insertion throughput by up to 3.97x and concurrent search throughput by up to 4.00x while reducing search latency by up to 75.69%.
作者备注：15 pages, accepted to VLDB 2027, Code: https://github.com/AIS-SNU/NAVIS
期刊信息：PVLDB, 20(3): 481-495, 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-08 04:20 · 最新观测版本
NAVIS: Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search
On-disk graph-based vector search (GVS) has become the dominant approach for serving large-scale vector databases at high recall. Yet prior systems struggle to sustain concurrent search and update throughput on high-dimensional workloads. We identify the main bottleneck as position seeking, the graph traversal that finds neighbors during each update. Unlike search, which returns only the top-K closest vectors, it explores a much larger set to build an R-neighbor list of close neighbors and long-range shortcuts. These neighbors have different distance-accuracy requirements, yet search-oriented packed layouts fetch full vectors with every edge-list access, consuming cache capacity regardless of their role. We present NAVIS, an on-SSD GVS system that redesigns position seeking around this mismatch. At its core, locality-driven decoupling separates vectors from edgelists and packs graph-local edgelists together. This decoupling enables convergence-aware speculative reranking to selectively load full vectors until a sufficient set of close neighbors is resolved, while selecting the remaining shortcuts using approximate distances. It also allows NAVIS to devote cache capacity entirely to edgelists. To make this cache effective, NAVIS keeps the entrance graph fresh via lightweight updates that reuse traversal information already produced during position seeking, thereby maintaining a stable hot set of edgelists near its entry points. Across multiple large-scale benchmarks, NAVIS improves insertion throughput by up to 3.97x and concurrent search throughput by up to 4.00x while reducing search latency by up to 75.69%.
查看此版本解读 →查看此版本原文 ↗