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

arXiv:2607.28999 · cs.CR · Submitted 2026-07-31 · Read on arXiv

Haoyu Cui, Zengpeng Li, Tien Tuan Anh Dinh, Mei Wang

cs.CR

Submitted: 2026-07-31

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Embeddings — 41× in this paper · explained in 2 episodes
• Accuracy — 21× in this paper · explained in 1 episode
• Differential Privacy — 12× in this paper · explained in 4 episodes
• Trace — 11× in this paper · explained in 2 episodes
• Aggregation — 7× in this paper · explained in 1 episode
• Communication Overhead — 6× in this paper · explained in 2 episodes
• Graph Construction — 6× in this paper · explained in 3 episodes
• Hamming Distance — 6× in this paper · explained in 2 episodes
• Hierarchical Navigable Small World — 5× in this paper
• Private Information Retrieval — 5× in this paper
• Calibration — 4× in this paper · explained in 7 episodes
• Clustering — 3× in this paper · explained in 2 episodes
• Differential Privacy (DP) — 3× in this paper · explained in 7 episodes
• Differentially Private — 3× in this paper · explained in 3 episodes
• Ablation — 2× in this paper · explained in 1 episode
• Adjacency Matrix — 2× in this paper · explained in 1 episode
• Computational overhead — 2× in this paper · explained in 2 episodes
• Core — 2× in this paper · explained in 2 episodes
• IEEE Symposium on Security and Privacy — 2× in this paper
• RAG — 2× in this paper · explained in 3 episodes
• AUC — 1× in this paper · explained in 2 episodes
• Adaptive Graph — 1× in this paper · explained in 1 episode
• Algorithmic Primitives — 1× in this paper · explained in 1 episode
• Benchmark — 1× in this paper · explained in 2 episodes
• Consistency — 1× in this paper · explained in 3 episodes
• Contrastive Learning — 1× in this paper · explained in 5 episodes
• Cosine Similarity — 1× in this paper · explained in 3 episodes
• Curse of Dimensionality — 1× in this paper · explained in 6 episodes
• EMMA — 1× in this paper · explained in 2 episodes
• Gradient Flow — 1× in this paper · explained in 2 episodes
• International Conference on Data Engineering — 1× in this paper
• Large Language Models (LLMs) — 1× in this paper · explained in 6 episodes
• Quantization — 1× in this paper · explained in 12 episodes
• Retrieval-Augmented Generation (RAG) — 1× in this paper · explained in 16 episodes

Sources

• LEANN: A Low-Storage Vector Index
• Wally: Batched Private Nearest Neighbor Search at Scale
• Unsupervised Dense Information Retrieval with Contrastive Learning
• Opal: Private Memory for Personal AI

Related papers

• SoK: AI-Augmented Binary Reversing
• Relaxed Sender Anonymity for CBDC Interbank Settlement: A Zero-Knowledge Approach on Permissioned EVM
• Calibration-Family Overfit: Why Trusted Sabotage Monitors Don't Transfer Across Lineages
• Efficient Fuzzy PSI under One-Sided Assumptions
• Sealing the Audit-Runtime Gap for LLM Skills
• Token Composition: A Graph Based on EVM Logs