Metraipolis › archive › dc_7eacfac489bc

Recast: Refinement-Centered Approximate Nearest Neighbor Search Optimized for Storage — arXiv:2611.02765

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.02765
License (as archived): CC0-1.0
Archived: 2026-11-03T11:45:31.426Z
SHA-256 of the archived text: cb7d756c0e5981ea2d647b2f31d1324a4730d7ebb255b41accc170120bd9eabd
Stable URL of this page: https://metraipolis.com/documento/dc_7eacfac489bc

How to cite

Recast: Refinement-Centered Approximate Nearest Neighbor Search Optimized for Storage — arXiv:2611.02765 — arXiv (en), https://arxiv.org/abs/2611.02765 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7eacfac489bc (Metraipolis archive dc_7eacfac489bc, sha256 cb7d756c0e5981ea2d647b2f31d1324a4730d7ebb255b41accc170120bd9eabd)

BibTeX

@misc{dc7eacfac489bc,
  title = {Recast: Refinement-Centered Approximate Nearest Neighbor Search Optimized for Storage — arXiv:2611.02765},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02765},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7eacfac489bc; sha256 cb7d756c0e5981ea2d647b2f31d1324a4730d7ebb255b41accc170120bd9eabd},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02765. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.DB, nuovi lavori del giorno).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2611.02765 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:07:07.173Z dalla pagina https://arxiv.org/list/cs.DB/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).