Metraipolis › archive › dc_ac4e050d1304
Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search — arXiv:2608.16488
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.16488
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T23:35:32.926Z
- SHA-256 of the archived text
3b850add4f22de9ae368e346277254be7738f14e0ce1e8c1a2538faf929e4548- Stable URL of this page
https://metraipolis.com/documento/dc_ac4e050d1304
How to cite
Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search — arXiv:2608.16488 — arXiv (en), https://arxiv.org/abs/2608.16488 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ac4e050d1304 (Metraipolis archive dc_ac4e050d1304, sha256 3b850add4f22de9ae368e346277254be7738f14e0ce1e8c1a2538faf929e4548)
BibTeX
@misc{dcac4e050d1304,
title = {Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search — arXiv:2608.16488},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.16488},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ac4e050d1304; sha256 3b850add4f22de9ae368e346277254be7738f14e0ce1e8c1a2538faf929e4548},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.16488. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Range-filtered approximate nearest neighbor search (RFANNS) is an important primitive for vector databases; it retrieves vectors that are similar to a query and satisfy a numerical range predicate, but existing RFANNS indexes expose vectors, attributes, and queries in plaintext. This assumption is unsuitable for outsourced vector databases, where sensitive data and queries must be protected from an honest-but-curious cloud server. To the best of our knowledge, this is the first study that systematically formulates and evaluates privacy-preserving RFANNS over outsourced encrypted vector databases. Our approach separates range localization from encrypted vector search: an authorized user maps the query range to a compact set of nodes in a local N-ary attribute tree, and the server searches only the corresponding proximity graph sub-indices over encrypted vectors. To reduce expensive encrypted comparisons, we use a filter-and-refine pipeline that first retrieves coarse candidates with approximate distance-comparison-preserving encryption and then reranks a small candidate set with exact distance-comparison encryption. We then analyze the computation, storage, communication, and leakage of the protocol. Experiments on four widely used vector datasets show that our method improves the QPS-Recall trade-off over representative secure adaptations of existing RFANNS approaches, scaling effectively to large datasets. Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-08-18 in cs.DB). Categorie arXiv: Databases (cs.DB) ; Information Retrieval (cs.IR). Pagina del lavoro: https://arxiv.org/abs/2608.16488 — 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-10-18T23:02:17.577Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).