Recast improves vector search speed and storage efficiency
Recast: Refinement-Centered Approximate Nearest Neighbor Search Optimized for Storage
Databases
Summary
Finding similar items in huge collections often needs a mix of fast memory and slower storage. The authors designed Recast, which keeps a small summary of all items in memory and stores the full details on disk. To answer questions quickly, Recast first scans summaries in memory to guess good matches, then checks only those few matches on disk more carefully. This approach speeds up updates and searches while using less space. The authors showed Recast works better than other methods on real data.
What this means in practice
- •For search engine developers: Build large-scale similarity search systems that handle fast insertions, deletions, and queries efficiently using less disk space and memory.
- •For database engineers: Improve management of large vector databases by optimizing balance between memory-resident indexes and disk-resident vector storage for better update and query performance.
Authors
Zehai Yang, Fengyi Tao, Wenzhuo Dong, Shimin Chen
Abstract
Large-scale ANNS systems often exploit storage in addition to DRAM for supporting vector search. The central question is how to divide the work between memory and storage for achieving both high query throughput-recall and good index maintenance performance. Existing storage-optimized ANNS paradigms fall short of providing a complete answer: disk-resident graph indexes have difficulty in supporting efficient vector deletions, while posting-list systems often incur more disk I/Os for queries. In this paper, we introduce a refinement-centered paradigm for storage-optimized ANNS systems. We propose Recast as a concrete design of this paradigm. Recast stores raw vectors on disk and keeps an IVF index with our RecastQ quantization encoding in memory. For an ANNS query, Recast selects nprobe inverted lists and performs SIMD-based FastScan on their RecastQ codes to identify refinement candidates in memory. It then retrieves candidate vectors from disk, computes exact distances, and refines the top-K result. To reduce disk I/Os, RecastQ computes uncertainty intervals containing true distances with high probability. Our QUIC policy selects a minimal refinement set based on these intervals, minimizing candidate-retrieval I/Os. Both the on-disk raw vectors and the in-memory IVF structure support insertions and deletions. Experiments on real-world data sets show that Recast processes batched insertions and deletions 3.10-37.27x faster than SPFresh and OdinANN, while its QPS at 0.99 recall changes by at most 6.9% after updating 50% of the corpus. For static queries at 0.99 recall, Recast achieves 1.56-2.01x the QPS of the strongest baseline with the matched memory budget on each data set, while requiring 1.22-6.75x less external storage than the evaluated systems. At matched in-memory space, RecastQ also provides a better Recall-refinement frontier than RaBitQ.