pipette
ENEnglish

CAROUSEL: GPU-Accelerated Private Vector Search via Homomorphic Sketching

Sohaib, Divyakant Agrawal, Amr El Abbadi, Soamar Homsi

PreprintUso en el mundo real

En palabras de los autores

Vector search on untrusted infrastructure exposes the query embedding, a faithful summary of the user's intent. Fully homomorphic encryption can hide the query, but existing approaches still require a full scan followed by ranking of encrypted scores. Scalable private systems avoid encrypted ranking by either sending scores from a single cluster to the client or moving the search to the client, which must first stream the entire vector index for preprocessing. We present \textsc{Carousel}, which instead scores the full corpus under encryption and compresses the results for client-side ranking. The server scores every vector under encryption, raises the scores to a power that preserves their order by magnitude while suppressing all but a handful, and compresses the resulting sparse vector into a logarithmic number of ciphertexts using homomorphic additions alone. Because every vector is scored, \textsc{Carousel} incurs no recall loss from discarding candidates. Since clients hold no database-dependent state, insertions and deletions take effect immediately at the cost of a single vector write. \textsc{Carousel} searches billion vectors of BIGANN SIFT1B across multiple GPUs and achieves recall@100 of . At million SIFT vectors, it achieves recall@100 of with a query latency of seconds on a single GPU.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.