MESS: Fast and Private Semantic Search on Multi-Graph HNSW
MESS combines binary hashing, multi-graph HNSW, and differential privacy to enable fast, private semantic search with low latency.
Key Findings
Methodology
MESS employs a pipeline where high-dimensional vectors are mapped to binary codes via IsoHash, then perturbed using LSH randomized response to ensure privacy. Multiple independent HNSW graphs are constructed over these perturbed codes, each with different parameters. During search, the query vector undergoes the same hashing and perturbation, and a Hamming-distance-based search is performed across all shards. The results are aggregated and decrypted by the client. The system balances privacy, accuracy, and efficiency by leveraging multi-graph fusion and two-phase query perturbation, avoiding cryptographic overheads like homomorphic encryption or ORAM.
Key Results
- On SIFT100M, MESS achieves an average query latency of 52.53 ms, outperforming state-of-the-art methods by up to 15.08×, with communication overhead reduced by 35.28×. The recall rate remains above 90%, demonstrating high accuracy under privacy constraints.
- Extensive experiments show that the multi-graph design effectively mitigates the impact of perturbation, maintaining near-plaintext retrieval quality. The system scales well with large datasets, confirming its practicality for real-world cloud applications.
- Compared to baseline privacy solutions, MESS provides a superior trade-off between privacy, speed, and accuracy, making it suitable for privacy-sensitive large-scale vector search scenarios.
Significance
This work advances private semantic search by integrating differential privacy with efficient multi-graph indexing, addressing the longstanding challenge of balancing privacy and performance. It opens new avenues for deploying privacy-preserving vector databases in cloud environments, enabling secure, scalable, and high-quality retrieval for sensitive data such as personal images, documents, and medical records. The approach significantly reduces latency and communication costs, making private search feasible at industry scale, and lays the groundwork for future research on dynamic, multi-user privacy-preserving vector search systems.
Technical Contribution
The core innovation lies in combining LSH-based randomized response with multiple independent HNSW graphs, each with distinct parameters, to counteract the effects of perturbation on recall. The two-phase query perturbation mechanism further protects against pattern leakage. Theoretical privacy bounds are derived, and the multi-graph fusion approach is shown to improve robustness against adversarial attacks. The system demonstrates that privacy-preserving ANN search can be both practical and accurate without relying on heavy cryptography, thus bridging the gap between security and efficiency.
Novelty
This is the first work to integrate differential privacy with multi-graph HNSW indexing specifically for semantic search. Unlike prior solutions relying solely on encryption or single-layer perturbation, MESS employs a multi-graph structure with independent perturbations and a two-stage query randomization, significantly enhancing privacy without sacrificing accuracy. Its innovative combination of hashing, perturbation, and multi-graph fusion sets a new standard in private vector search.
Limitations
- The system's performance depends heavily on the choice of perturbation parameters; overly aggressive perturbation reduces recall, while mild perturbation risks privacy leakage. Parameter tuning remains complex.
- Maintaining multiple independent graphs increases storage and update complexity, especially for dynamic datasets.
- In scenarios with extremely high privacy demands, the recall may degrade, necessitating further optimization of multi-graph fusion strategies.
Future Work
Future research will explore adaptive perturbation schemes based on data sensitivity, dynamic index updating for real-time applications, and integration with federated learning to support multi-party privacy-preserving search. Additionally, efforts will focus on reducing storage overhead and improving robustness against sophisticated inference attacks, aiming for broader deployment in industry environments.
AI Executive Summary
As the volume of high-dimensional data surges, semantic search systems have become vital for information retrieval and AI applications. Traditional solutions like FAISS, HNSW, and Annoy deliver high efficiency but lack privacy guarantees, especially in cloud deployments where sensitive data is involved. Existing cryptographic approaches such as homomorphic encryption and ORAM provide strong privacy but suffer from prohibitive computational and communication costs, limiting scalability.
This paper introduces MESS, a novel system that combines differential privacy, binary hashing, and multi-graph HNSW indexing to enable fast, private semantic search. By mapping vectors into binary codes using IsoHash and perturbing them with LSH randomized response, MESS ensures data, query, and access pattern privacy. The multi-graph structure, built over independently perturbed codes, mitigates the accuracy loss caused by noise, maintaining high recall rates. During search, the system performs Hamming-distance-based retrieval across multiple shards, then aggregates and decrypts results on the client side.
Experimental results on large-scale datasets like SIFT100M demonstrate that MESS achieves an average query latency of just over 50 milliseconds, outperforming existing privacy-preserving methods by up to 15 times while significantly reducing communication overhead. The system maintains over 90% recall, validating its effectiveness in balancing privacy and accuracy. Its efficiency and scalability make it suitable for real-world cloud applications, addressing critical privacy concerns in sensitive data retrieval.
Overall, MESS represents a significant step forward in private vector search technology. It offers a practical, high-performance solution that can be integrated into industry-grade AI and data management systems. Future work will focus on adaptive privacy parameters, dynamic index updates, and multi-party privacy scenarios, further broadening its applicability and robustness in diverse environments.
Deep Dive
Plain Language Accessible to non-experts
想象你在一个大型图书馆里，里面藏着成千上万的书。你想找到和某本书内容相似的其他书，但又不想让别人知道你在找哪本。于是，你用一种特殊的秘密编码，把每本书的内容变成一串0和1的数字。这个编码会稍微改变一些数字，让别人无法知道你真正感兴趣的书。图书馆有很多不同的书架，每个书架都存放着不同的编码版本。每次你想找书时，你也用相同的方法编码你的查询，然后在每个书架上找最接近的编码。最后，把所有找到的编码合起来，你就能找到最相似的书。这种方法既保护了你的隐私，又能快速找到你想要的内容，就像用不同的密码和多个书架合作，既安全又高效。
ELI14 Explained like you're 14
想象你在学校里，有很多书，每本书都有一个特别的编号。你想找和某本书内容差不多的其他书，但又不想让别人知道你在找哪本。于是，你用一种神奇的变换，把每个编号变成一串0和1的数字，这个变换会稍微改变一些数字，让别人猜不到你真正的目标。你还把这些编号放到几个不同的书架上，每个书架用不同的方法存放。每次你要找书时，也用相同的变换，然后在每个书架上找最接近的编号。最后，把所有找到的编号合起来，你就能找到最相似的书。这种方法既能保护你的隐私，又能让你快速找到想要的书，就像用不同的密码和多个书架合作，既安全又快！
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.