Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search

• URL: http://arxiv.org/abs/2608.16488v1
• Date: Mon, 17 Aug 2026 12:28:25 GMT
• Title: Efficient Privacy-Preserving Range Filtered Approximate Nearest Neighbor Search
• Abstract summary: Range-filtered approximate nearest neighbor search (RFANNS) is an important primitive for vector databases.<n>We formulate and evaluate privacy-preserving RFANNS over outsourced encrypted vector databases.<n>Our method improves the QPS-Recall trade-off over representative secure adaptations of existing RFANNS approaches.
• Score: 22.644268689842377
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• Learning Filter-Aware Distance Metrics for Nearest Neighbor Search with Multiple Filters [7.493563348124023]
  Filtered Approximate Nearest Neighbor (ANN) search retrieves the closest vectors for a query vector from a dataset.<n>Existing graph-based methods typically incorporate filter awareness by assigning fixed penalties.<n>We propose a principled alternative that learns the optimal trade-off between vector distance and filter match directly from the data.
  arXiv  Detail & Related papers  (2025-11-06T05:24:41Z)
• Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors [18.796661826646616]
  Filtered Approximate Nearest Neighbor Search is a problem known as Filtered Approximate Nearest Neighbor Search (FANNS)<n>We present a comprehensive survey and taxonomy of FANNS methods and analyze how they are benchmarked in the literature.<n>We introduce a novel dataset consisting of embedding vectors for the abstracts of over 2.7 million research articles from the arXiv repository, accompanied by 11 real-world attributes such as authors and categories.
  arXiv  Detail & Related papers  (2025-07-29T16:39:54Z)
• Beyond Nearest Neighbors: Semantic Compression and Graph-Augmented Retrieval for Enhanced Vector Search [2.377892000761193]
  We introduce a new retrieval paradigm: semantic compression, which aims to select a compact, representative set of vectors that captures the broader semantic structure around a query.<n>To operationalize this idea, we propose graph-augmented vector retrieval, which overlays semantic graphs (e.g., kNN or knowledge-based links) atop vector spaces.<n>Our work outlines a foundation for meaning-centric vector search systems, emphasizing hybrid indexing, diversity-aware querying, and structured semantic retrieval.
  arXiv  Detail & Related papers  (2025-07-25T23:35:11Z)
• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  We show that in $q$-metric spaces, metric trees can leverage a stronger version of the triangle inequality to reduce comparisons for exact search.<n>We propose a novel projection method that embeds datasets with arbitrary dissimilarity measures into $q$-metric spaces.
  arXiv  Detail & Related papers  (2025-06-06T22:09:44Z)
• Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
  We provide experimental results on the BEIR dataset using the open-source Lucene search library. Our results provide guidance for today's search practitioner in understanding the design space of dense and sparse retrievers.
  arXiv  Detail & Related papers  (2024-09-10T12:46:23Z)
• Efficient Data Access Paths for Mixed Vector-Relational Search [8.80592433569832]
  Machine learning and the adoption of data processing methods using vector embeddings sparked a great interest in creating systems for vector data management. While the predominant approach of vector data management is to use specialized index structures for fast search over the entirety of the vector embeddings, once combined with other (meta)data, the search queries can also become selective on relational attributes. As using vector indexes differs from traditional relational data access, we revisit and analyze alternative access paths for efficient mixed vector-relational search.
  arXiv  Detail & Related papers  (2024-03-23T11:34:17Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  This work presents an adaptive group testing framework for the range-based high dimensional near neighbor search problem. Our method efficiently marks each item in a database as neighbor or non-neighbor of a query point, based on a cosine distance threshold without exhaustive search. We show that, using softmax-based features, our method achieves a more than ten-fold speed-up over exhaustive search with no loss of accuracy.
  arXiv  Detail & Related papers  (2023-11-05T06:12:03Z)
• Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR Decomposition [77.4863142882136]
  Cross-encoder models are prohibitively expensive for direct k-nearest neighbor (k-NN) search. We propose ADACUR, a method that adaptively, iteratively, and efficiently minimizes the approximation error for the practically important top-k neighbors.
  arXiv  Detail & Related papers  (2023-05-04T17:01:17Z)
• Collaborative Training between Region Proposal Localization and Classification for Domain Adaptive Object Detection [121.28769542994664]
  Domain adaptation for object detection tries to adapt the detector from labeled datasets to unlabeled ones for better performance. In this paper, we are the first to reveal that the region proposal network (RPN) and region proposal classifier(RPC) demonstrate significantly different transferability when facing large domain gap.
  arXiv  Detail & Related papers  (2020-09-17T07:39:52Z)
• Progressively Pretrained Dense Corpus Index for Open-Domain Question Answering [87.32442219333046]
  We propose a simple and resource-efficient method to pretrain the paragraph encoder. Our method outperforms an existing dense retrieval method that uses 7 times more computational resources for pretraining.
  arXiv  Detail & Related papers  (2020-04-30T18:09:50Z)
• PyODDS: An End-to-end Outlier Detection System with Automated Machine Learning [55.32009000204512]
  We present PyODDS, an automated end-to-end Python system for Outlier Detection with Database Support. Specifically, we define the search space in the outlier detection pipeline, and produce a search strategy within the given search space. It also provides unified interfaces and visualizations for users with or without data science or machine learning background.
  arXiv  Detail & Related papers  (2020-03-12T03:30:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.