Search papers, labs, and topics across Lattice.
The paper addresses the computational bottleneck in on-disk graph-based Approximate Nearest Neighbor Search (ANNS) for high-dimensional vectors, which is often overlooked in favor of I/O optimization. AlayaLaser is introduced, featuring a novel on-disk data layout that leverages SIMD instructions to reduce computational overhead. Experimental results demonstrate that AlayaLaser outperforms existing on-disk methods and achieves comparable or superior performance to in-memory approaches.
On-disk graph indexes for billion-scale vector search are actually compute-bound, not I/O-bound, and AlayaLaser exploits this to match in-memory performance.
On-disk graph-based approximate nearest neighbor search (ANNS) is essential for large-scale, high-dimensional vector retrieval, yet its performance is widely recognized to be limited by the prohibitive I/O costs. Interestingly, we observed that the performance of on-disk graph-based index systems is compute-bound, not I/O-bound, with the rising of the vector data dimensionality (e.g., hundreds or thousands). This insight uncovers a significant optimization opportunity: existing on-disk graph-based index systems universally target I/O reduction and largely overlook computational overhead, which leaves a substantial performance improvement space. In this work, we propose AlayaLaser, an efficient on-disk graph-based index system for large-scale high-dimensional vector similarity search. In particular, we first conduct performance analysis on existing on-disk graph-based index systems via the adapted roofline model, then we devise a novel on-disk data layout in AlayaLaser to effectively alleviate the compute-bound, which is revealed by the above roofline model analysis, by exploiting SIMD instructions on modern CPUs. We next design a suite of optimization techniques (e.g., degree-based node cache, cluster-based entry point selection, and early dispatch strategy) to further improve the performance of AlayaLaser. We last conduct extensive experimental studies on a wide range of large-scale high-dimensional vector datasets to verify the superiority of AlayaLaser. Specifically, AlayaLaser not only surpasses existing on-disk graph-based index systems but also matches or even exceeds the performance of in-memory index systems.
