Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search
2026-08-17 • Databases
DatabasesInformation Retrieval
AI summaryⓘ
The authors study how to search for similar items in a database while only looking at data within a specific range, without revealing sensitive information to the cloud server storing the data. They propose a method that splits the search into two parts: first finding the relevant range using a local tree structure, then searching encrypted data on the server. Their technique uses a two-step process to quickly find approximate matches and then refine them exactly, reducing costly operations on encrypted data. Experiments show their approach works well and keeps data private while handling large datasets.
Approximate Nearest Neighbor SearchRange FilteringEncrypted Vector DatabasesPrivacy-Preserving SearchProximity GraphDistance-Comparison EncryptionFilter-and-Refine PipelineOutsourced DatabasesData LeakageQPS-Recall Trade-off
Authors
Haoyu Wang, Yandi Zhang, Jiadong Xie, Yingfan Liu, Hui Li, Jeffrey Xu Yu, Jiangtao Cui
Abstract
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.