Giant: An I/O-Optimized Graph-Based Index for High-dimensional Vector Search via Page Group Expansion
摘要
Modern vector search systems increasingly depend on high-capacity and cost-efficient NVMe SSDs for storage, as data dimensionality and scale continue to grow. Graph-based indices are widely adopted for their superior search accuracy; however, the graph traversal triggers intensive random I/O on SSDs, significantly degrading search performance. Existing graph-based retrieval methods attempt to reduce I/O overhead through page expansion. However, these approaches introduce two key limitations: 1) Insufficient page expansion. As vector dimensions grow, fewer nodes fit within a single SSD page, reducing the number of accessible nodes for expansion and thus limiting traversal efficiency. 2) Inefficient utilization of I/O time. Existing candidate pool expansion strategy exhibits diminishing returns in reducing I/O overhead, while its computation increases linearly, resulting in inefficient utilization of I/O time. To address these issues, we propose Giant, an I/O-optimized graph index for high-dimensional vector search based on a novel page group expansion mechanism. This mechanism is supported by two core techniques: a memory-resident group index enabling deeper node expansion, and a page expansion list offering diverse supplementary candidates. Experiments demonstrate that Giant reduces average search latency by 12%–43% and achieves 1.10 \(\times -\) 1.41 \(\times \) higher throughput compared with state-of-the-art methods.