MESS: Fast and Private Semantic Search on Multi-Graph HNSW

• URL: http://arxiv.org/abs/2607.28999v2
• Date: Tue, 04 Aug 2026 05:14:18 GMT
• Title: MESS: Fast and Private Semantic Search on Multi-Graph HNSW
• Abstract summary: We present MESS, a search system with three properties: privacy, accuracy, and efficiency.<n>It maps the original vectors into binary codes, applies locality-sensitive hashing (LSH) and randomized response, and constructs a multi-graph Hierarchical Navigable Small World (HNSW) index over the perturbed codes.<n> MESS achieves up to 15.08times lower latency than state-of-the-art baselines.
• Score: 11.990611521434944
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semantic search systems map data to a high-dimensional vector space and support retrieval of similar data via approximate nearest neighbor search. When the system is hosted by an untrusted cloud provider, there is no privacy for the data or the query. Our goal is to design a system with three properties: privacy, accuracy, and efficiency. Existing works adopt either homomorphic encryption (HE), oblivious RAM (ORAM), or a differential privacy (DP) approach. They fall short of achieving all three properties. In this paper, we present MESS, a system that realizes our goal. It maps the original vectors into binary codes, applies locality-sensitive hashing (LSH) and randomized response, and constructs a multi-graph Hierarchical Navigable Small World (HNSW) index over the perturbed codes. MESS ensures data, query, and access pattern privacy. It also ensures search pattern privacy via a two-phase query perturbation mechanism. The multi-graph index mitigates the impact of perturbation on result quality, thereby achieving accuracy. MESS is efficient because search is performed directly over perturbed codes, without the overhead of homomorphic encryption or ORAM. We give formal analysis of the system's privacy and extensive evaluation of its performance. The results show that MESS achieves up to 15.08\times lower latency than state-of-the-art baselines.

Related papers

• Atlas: Efficient Verifiable Semantic Search [42.56979915155187]
  We present Atlas, a system that lets a provider prove a query was answered correctly against its committed index without revealing the index.<n>At its core is a new zero-knowledge proof for HNSW search, built on three techniques.<n> Atlas is the first to demonstrate verifiable graph-based search at scale.
  arXiv  Detail & Related papers  (2026-09-10T17:30:39Z)
• Achieving Text-based Person Retrieval with Any Granularity [80.69427598925718]
  This paper introduces a new paradigm, Text-based Person Retrieval with Any Granularity.<n>We formalize a five-level granularity spectrum and construct UFine6926-MG, a high-quality multi-grained annotated dataset.<n>We then propose the Cross-modal Multi-grained Aligning and Matching framework.
  arXiv  Detail & Related papers  (2026-07-23T08:42:25Z)
• GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
  GONDOR is a memory-efficient extension of Greedy Best-First Search (GBFS)<n>GONDOR periodically compresses the search tree while retaining a sparse set of anchor states, then upon reaching the goal reconstructs the path by re-searching between the sparse states.<n> Experiments show that GONDOR consistently improves coverage under low memory budgets compared to standard GBFS.
  arXiv  Detail & Related papers  (2026-05-27T13:20:58Z)
• Differentially Private Motif-Preserving Multi-modal Hashing [9.39195684989942]
  Cross-modal hashing enables efficient retrieval by encoding images and text into compact binary codes.<n>Existing privacy-preserving approaches fail on graph-structured data.<n>DMP-MH is a Sanitize-then-Distill framework that decouples privacy from representation learning.
  arXiv  Detail & Related papers  (2026-05-14T22:43:30Z)
• Benchmarking Fraud Detectors on Private Graph Data [70.4654745317714]
  Currently, many types of fraud are managed in part by automated detection algorithms that operate over graphs.<n>We consider the scenario where a data holder wishes to outsource development of fraud detectors to third parties.<n>Third parties submit their fraud detectors to the data holder, who evaluates these algorithms on a private dataset and then publicly communicates the results.<n>We propose a realistic privacy attack on this system that allows an adversary to de-anonymize individuals' data based only on the evaluation results.
  arXiv  Detail & Related papers  (2025-07-30T03:20:15Z)
• Threshold-Protected Searchable Sharing: Privacy Preserving Aggregated-ANN Search for Collaborative RAG [0.0]
  Two key bottlenecks are private data repositories' locality constraints and the need to maintain compatibility with mainstream search techniques.<n>We develop a secure and privacy-preserving aggregated approximate nearest neighbor search (SP-A$2$NN) with HNSW compatibility.<n>We also explore a novel security analytical framework that incorporates privacy analysis via reductions.
  arXiv  Detail & Related papers  (2025-07-23T04:45:01Z)
• VeriFuzzy: A Dynamic Verifiable Fuzzy Search Service for Encrypted Cloud Data [13.863905835870836]
  Service that supports dynamic, verifiable fuzzy search (DVFS) over encrypted cloud data remains a fundamental challenge.<n>This paper presents textbfVeriFuzzy, a novel DVFS service framework that cohesively integrates three innovations.<n>Our code and dataset are now open source, hoping to inspire future DVFS research.
  arXiv  Detail & Related papers  (2025-07-15T02:36:30Z)
• Investigating the Scalability of Approximate Sparse Retrieval Algorithms to Massive Datasets [8.1990111961557]
  We investigate the behavior of state-of-the-art retrieval algorithms on massive datasets.<n>We compare and contrast the recently-proposed Seismic and graph-based solutions adapted from dense retrieval.<n>We extensively evaluate Splade embeddings of 138M passages from MsMarco-v2 and report indexing time and other efficiency and effectiveness metrics.
  arXiv  Detail & Related papers  (2025-01-20T17:59:21Z)
• OPANAS: One-Shot Path Aggregation Network Architecture Search for Object Detection [82.04372532783931]
  Recently, neural architecture search (NAS) has been exploited to design feature pyramid networks (FPNs) We propose a novel One-Shot Path Aggregation Network Architecture Search (OPANAS) algorithm, which significantly improves both searching efficiency and detection accuracy.
  arXiv  Detail & Related papers  (2021-03-08T01:48:53Z)
• Comprehensive Graph-conditional Similarity Preserving Network for Unsupervised Cross-modal Hashing [97.44152794234405]
  Unsupervised cross-modal hashing (UCMH) has become a hot topic recently. In this paper, we devise a deep graph-neighbor coherence preserving network (DGCPN) DGCPN regulates comprehensive similarity preserving losses by exploiting three types of data similarities.
  arXiv  Detail & Related papers  (2020-12-25T07:40:59Z)
• Ultra-Fast, Low-Storage, Highly Effective Coarse-grained Selection in Retrieval-based Chatbot by Using Deep Semantic Hashing [25.803411212281443]
  There are two approaches for coarse-grained selection module: sparse representation and dense representation. Extensive experiment results demonstrate that dense representation method significantly outperforms the sparse representation. We propose an ultra-fast, low-storage, and highly effective Deep Semantic Hashing Coarse-grained selection method, called DSHC model. Our proposed DSHC model can achieve much faster speed and lower storage than sparse representation, with limited performance loss compared with dense representation.
  arXiv  Detail & Related papers  (2020-12-17T14:54:59Z)
• A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
  Differential privacy (DP) is a compelling privacy definition that explains the privacy-utility tradeoff via formal, provable guarantees. We propose a private sketch that supports a multitude of machine learning tasks including regression, classification, density estimation, and more. Our sketch consists of randomized contingency tables that are indexed with locality-sensitive hashing and constructed with an efficient one-pass algorithm.
  arXiv  Detail & Related papers  (2020-06-16T17:47:48Z)

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.