Pith. sign in

REVIEW 3 major objections 3 minor 53 references

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

T0 review · 3 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read MESS claims a differentially private semantic search system that keeps near-plaintext accuracy and runs 15x faster than ORAM-based Compass.

desk verdict MESS is a genuine systems contribution with a fixable but load-bearing gap: the stored-index privacy proof assumes IsoHash trained off the protected database, while the main protocol trains on it. read the letter →

arxiv 2607.28999 v2 pith:2O67MJPH submitted 2026-07-31 cs.CR

Haoyu Cui , Zengpeng Li , Tien Tuan Anh Dinh , Mei Wang This is my paper · ORCID
classification cs.CR
keywords privatesemanticsearchdifferentialprivacylocality-sensitivehashingrandomizedresponseHNSWindexaccesspatternmulti-graph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

MESS is a system for semantic search over vector embeddings when the search index lives on an untrusted cloud server. It claims that privacy of the stored data, of individual query access patterns, and of repeated-query search patterns can all be provided through differential privacy applied to binary locality-sensitive hash codes, without the heavy machinery of homomorphic encryption or oblivious RAM. To keep retrieval quality high despite the bit-flips that create privacy, the system stores each vector in multiple independently hashed and independently perturbed hierarchical navigable small-world (HNSW) graph shards and aggregates candidates across shards. The paper backs this with formal extended-differential-privacy theorems for the stored index, the access transcript, and the repeated-query transcript, and reports that search stays close to plaintext accuracy while running in 52.53 ms/query on a 100-million-vector index, up to 15.08x faster than the ORAM-based Compass baseline.

What carries the argument

The load-bearing mechanism is the LSH randomized-response (LSHRR) perturbation of shard-specific binary codes combined with a multi-graph HNSW index. Each shard applies its own pretrained IsoHash mapping, producing κ-bit codes from the original embeddings; randomized response flips each bit with probability p, giving an (ε d_H, 0)-XDP guarantee under the hash-induced Hamming pseudometric. To keep recall high, each embedding is routed to t of M shards with independent hash functions and independent perturbation coins, and the query is searched in all shards, with candidates aggregated before client-side exact reranking. The two-phase query perturbation—a permanent randomized response reused f

What would settle it

Train the shard-specific IsoHash directly on the protected database, then empirically estimate the maximum likelihood ratio of the complete server view between two neighboring embeddings that differ in a single value; if the ratio exceeds e^{η_D D_D(𝒙,𝒙′)} for any pair, the stored-data guarantee is violated. Equivalently, a cross-shard linkage procedure that correctly recovers all t shard entries of a target record would push the reconstructed XDP evidence to the complete-view threshold, showing the single-server view leaks more than the experiments indicate.

Watch

Extended reading notes

Core claim

The paper's central claim is that differential privacy, applied at the level of binary LSH codes, is enough to make a cloud-hosted nearest-neighbor index private in all three senses that matter—stored data, access pattern, and search pattern—without sacrificing search quality or online speed. MESS quantizes each embedding into a shard-specific binary code and flips bits with randomized response; a permanent randomized response memoized per query value, followed by a fresh instantaneous response per submission, hides both the query value and the fact that a query was repeated. Theorem 5.1 shows the complete stored multi-graph index is η_D-XDP with respect to the shard-aggregated Hamming pseud

Load-bearing premise

The privacy proofs assume the shard-specific IsoHash mappings are trained on data that is public, disjoint from the protected database, or excluded from the neighboring relation; if the training data overlaps or correlates with the protected embeddings, the differential-privacy bounds on the stored index and query traces no longer hold.

Editorial extensions

If this is right

  • If the theorems hold, users can outsource embedding search to an untrusted cloud with quantifiable leakage bounds instead of assuming full obliviousness.
  • DP-based approaches become a practical alternative to ORAM and homomorphic-encryption baselines for high-recall private search, changing the design space for private vector databases.
  • Because search over perturbed codes is one-round and avoids encrypted distance computation, the scheme can scale to hundred-million-vector datasets where cryptographic baselines are impractical.
  • The multi-shard redundancy gives operators a tunable privacy–accuracy–storage tradeoff through the routing multiplicity, flip probabilities, and candidate pool size.
  • The two-phase permanent plus instantaneous response offers a template for hiding query repetition without independent perturbation per submission.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the IsoHash training-data disjointness condition can be met with a public auxiliary set (for example, class prototypes not in the protected database), the same design would extend to deployment settings where the protected database itself is the only data source.
  • The paper's Poisson-binomial overtaking model suggests a principled way to auto-tune the flip probability, routing multiplicity, and candidate budget for a target recall, which the paper does not develop into a closed-form optimizer.
  • Because the guarantee is XDP with a distance pseudometric, the index could also serve as a building block for differentially private publication of embeddings in federated or streaming settings, where per-pair sensitivities are auditable.
  • The cross-shard linkage evaluation shows practical leakage well below the perfect-association bound assumed in the formal theorem; if future linkage attacks close that gap, single-server deployments would see degraded effective privacy, motivating two-server or secret-shared variants for high-assurance settings.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. MESS is a private semantic search system that combines locality-sensitive hashing, randomized response, and multiple HNSW graph shards. The client hashes and perturbs embeddings before outsourcing; the server stores encrypted payloads and HNSW indices over perturbed binary codes; queries use a two-phase permanent/instantaneous randomized-response mechanism. The paper claims formal XDP guarantees for stored-data, access-pattern, and search-pattern privacy, and evaluates accuracy and latency against plaintext HNSW, Compass, and HE-Cluster baselines on SIFT, LAION, TripClick, MS MARCO, and SIFT100M. The central issue is a mismatch between the implemented protocol, which trains IsoHash on the protected database (Fig. 2), and the formal privacy analysis, which requires the ISO-LSH mappings to be fixed and trained on public/disjoint data (Sec. 5.2.1).

Significance. If the result holds, MESS would be a notable practical contribution: it shows a DP-based design can approach plaintext ANN accuracy and achieve far lower latency than HE/ORAM-based private search on an untrusted single server. The multi-graph approach for mitigating randomized-response rank distortion is interesting, and the empirical cross-shard inference study is a useful complement to the formal analysis. The privacy bounds are derived analytically rather than fitted, and the only fitted quantities (Appendix B.1) are explicitly labeled as model fits. However, the training-data inconsistency means the main privacy theorems do not currently apply to the system as described in the main text, and the evaluation omits the achieved formal privacy parameters. With corrections, the contribution is potentially significant.

major comments (3)
  1. [§4 (Fig. 2), §5.2.1] Fig. 2 Phase 1 trains shard-specific IsoHash parameters on 'representative training data from D', but Sec. 5.2.1 requires the ISO-LSH mappings to be pretrained on data that is public, disjoint from the protected database, or excluded from the neighboring relation. If H_s is trained on D, two neighboring databases D0 and D1 differing in one substituted embedding yield different mappings H_s. Then every other record's shard codes, the HNSW graph structures, and the query-side hash mappings can differ between worlds. The proof of Theorem 5.1 conditions on a selected shard set and asserts that only the t shard-local entries of the substituted record depend on the embedding; that step is false when H_s itself is world-dependent. Theorems 5.2 and 5.3 inherit the same problem because they require fixed query mappings. Notably, the Appendix protocol (Fig. 7) already specifies a public/disjoint D
  2. [§6, Tabs. 2–3] The evaluation never reports the privacy parameters actually achieved at the tested configurations. For example, App. A.2 uses storage-side p_D=0.08, which gives eta_D=ln(0.92/0.08)=2.44, but the paper does not state eta_D, eta_R, xi_SP, or representative pair-specific XDP values for the SIFT/LAION/TripClick/MS MARCO and SIFT100M settings whose recall and latency are the headline results. The abstract claims privacy, accuracy, and efficiency simultaneously; without reporting the privacy side of the trade-off, Figs. 4–6 and Tabs. 2–3 cannot be assessed as a privacy-utility frontier. Add a table of the formal privacy parameters (or representative pair-specific values) for each evaluated configuration.
  3. [§5.2.4, Theorem 5.3] Theorem 5.3 only compares the workload W0=(q,...,q) with W1=(q,...,q,q'), i.e., a single split of one logical query into a new one. The prose in §2.3 and §5.2.4 promises protection of the general 'query-reuse relation' and states that the server 'cannot identify repeated queries'. A transcript containing several distinct query values and multiple repetitions involves multiple PRR groups and multiple reuse relations; the paper does not provide a composition argument or a bound for that general setting. Please either generalize the theorem to arbitrary workload adjacency (e.g., via composition over splits) or explicitly restrict the formal claim to the single-split adjacency.
minor comments (3)
  1. [Throughout] Typos: 'Skeched Proof' should be 'Sketch Proof' (Secs. 5.2.2–5.2.4); 'W AN' in the Fig. 4 caption and Sec. 6.2; 'iptoe' in Sec. 6.2 should be 'Tiptoe'. Also Tab. 1 has formatting glitches such as 'OursEncrypted DB'.
  2. [§6.1] The comparison would be clearer if the candidate pool sizes and p_D/p_q settings used in Fig. 4 were shown directly on the plots or in a table, rather than only in Appendix A.3. As written, the reader must cross-reference to know which privacy level each marker represents.
  3. [Appendix B.1] The fitted coefficients gamma_cov, mu_R, sigma_R, gamma_mrr are clearly labeled as empirical fits, which is good. However, the caption of Fig. 8 says 'Normal-CDF fit' without giving the fitted coefficient values; reporting them would improve reproducibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reduction: privacy theorems are direct RR/XDP compositions under fixed hash mappings; fitted accuracy curves are descriptive and not used for privacy claims.

full rationale

The central privacy theorems (5.1-5.3) are derived from bitwise randomized response applied to fixed, pretrained IsoHash mappings. Each proof is a standard composition argument: equal clean bits produce identical output distributions, differing bits contribute a likelihood ratio bounded by e^{eta} or e^{eta_R} or gamma, and HNSW traces are post-processing of the perturbed reports plus the fixed index. No theorem assumes the result it proves; the definitions of D_D, D_Q, and xi_SP are explicit metrics with parameters computed from the protocol constants and hash distances. The only fitted quantities in the paper are the normal-CDF accuracy curves in Appendix B.1 (gamma, mu_R, sigma_R), which the paper explicitly labels as nonlinear least-squares fits over measured points and says 'model the observed retrieval trends rather than exactly characterizing HNSW execution'; they are descriptive, not privacy predictions, and are not load-bearing for any privacy or efficiency claim. The one noteworthy caveat is a scope/consistency issue rather than circularity: Fig.2 Phase 1 trains IsoHash on 'representative training data from D', while Sec.5.2.1 states the proofs require mappings trained on data that are 'public, disjoint from the protected database, or excluded from the neighboring relation'. This is an assumption gap that could invalidate the formal theorem for the implemented protocol, but it does not make the derivation circular. The paper flags this assumption itself. The only self-citation ([19] in related work) is not used to support the central claim. No reduction of a central claim to a fitted value or to a self-citation chain exists.

Assumptions & free parameters 7 free parameters · 5 assumptions · 0 invented entities

The central privacy claims rest on a small number of standard DP facts plus two domain assumptions: the training data for the LSH mappings is public or disjoint, and the server has no access to client-side memoization state. The accuracy model rests on acknowledged approximations. The scheme introduces no new physical or ontological entities.

free parameters (7)
  • storage-side bit-flip probability p_D = 0.08
    Chosen by hand; controls the trade-off between the DP bound eta_D=ln((1-p_D)/p_D) and the recall loss from perturbation.
  • query-side effective bit-flip probability p_q (PRR/IRR split) = 0.00, 0.08, 0.10, 0.12 (Tab. 3 and Fig. 8)
    Chosen in experiments; determines query privacy (eta_R for access, gamma= and gamma!= for search patterns), but the main text does not report the PRR/IRR decomposition used.
  • hash length kappa per shard = 128
    Chosen; controls code dimensionality and the scale of the XDP terms, e.g., K_Q = sum kappa_s in Theorem 5.3.
  • number of shards M and routing multiplicity t = M=64, t=16
    Chosen; t/M sets replication and the completeness of the stored-index view; larger t improves accuracy but increases storage and privacy loss.
  • candidate pool size per dataset = SIFT 1400-1600, LAION 700-800, TripClick 2900-3200, MS MARCO 6000-6500; SIFT100M 4000-20000
    Chosen to balance recall against communication cost; affects end-to-end latency and communication, not the privacy proof.
  • PRR/IRR flip probabilities a, b = not reported separately
    Theorems 5.2 and 5.3 compute eta_R, gamma=, gamma!= from a, b, R; the evaluated settings only specify the combined p_q, so the privacy budget of the standard configuration cannot be reproduced from the paper.
  • accuracy model coefficients gamma_cov, mu_R, sigma_R, gamma_mrr = estimated by nonlinear least squares (values not tabulated)
    Fitted to the measured Recall/MRR curves in Appendix B.1; descriptive and not used to establish privacy claims.
assumptions (5)
  • standard math Bitwise randomized response under a fixed hash mapping satisfies XDP (from Fernandes et al. [14])
    Used as the base mechanism for Proposition 2 and Theorem 5.1; accepted from prior literature.
  • standard math DP post-processing: HNSW construction and traversal are functions of the perturbed codes plus world-independent randomness, so they incur no additional privacy cost
    Invoked in Theorems 5.1, 5.2, and 5.3; standard differential privacy composition property.
  • domain assumption The shard-specific IsoHash mappings are trained on data that is public, disjoint from the protected database, or excluded from the neighboring relation
    Stated in Sec. 5.2.1; if false, the stored-index XDP guarantee does not hold.
  • domain assumption The server is semi-honest, has no client-side state, cannot observe the PRR memoization cache, and no stable query identifier or memoization key is exposed
    Stated in Sec. 2.2 and Sec. 5.2.4; required for the access- and search-pattern theorems.
  • ad hoc to paper The correctness model's Gaussian approximation and independent-overtaking or conditional-independence assumptions hold approximately
    Used in Proposition 1 and Appendix B.1; explicitly acknowledged as approximations that model trends rather than exactly characterizing HNSW execution.

how reviews work

0 comments
Cite this review

Pith. "Pith review of MESS: Fast and Private Semantic Search on Multi-Graph HNSW." pith.science (2026). https://pith.science/paper/2O67MJPH

@misc{pith2026260728999,
  author       = {Pith},
  title        = {Pith review of: MESS: Fast and Private Semantic Search on Multi-Graph HNSW},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2O67MJPH}},
  note         = {Machine review of arXiv:2607.28999}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2607.28999 by the authors.

Figure 1
Figure 1. System architecture of MESS. removes duplicates using the identifiers, and reranks the candidates based on the decrypted embeddings. Scope. MESS supports semantic search over a database of vector embeddings, as opposed to directly over raw data (e.g., documents or images). We abstract away the data pre-processing pipeline that generates embeddings from raw data, and the post-processing pipeline for retrieving the ra… view at source ↗
Figure 1
Figure 1. System architecture of MESS [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. and ?? illustrate the multi-graph construction. For each embedding 𝑖, the client assigns it to a set of shards S𝑖 ← Route(𝑖, 𝑀, 𝑡). We instantiate Route as a data-independent pseudo￾random function that permutes [𝑀] and selects the first 𝑡 shards. For every shard 𝑗 ∈ S𝑖 , the client computes the shard-level bi￾nary embedding 𝒗𝑖,𝑗 ← ΠIsoHash.Hash(𝒙𝑖 , 𝝁𝑗 , W𝑗 , Q𝑗), then applies LSHRR to obtain e𝒗𝑖,𝑗 ← ΠLSHRR(𝒗𝑖,𝑗 ; … view at source ↗
Figures from the paper (7 more)
Figure 3
Figure 3. Figure 3: The flow of a query. for the first time, the client samples e𝒗 (PRR) 𝒒 ← ΠLSHRR(𝒗𝒒, 𝑝PRR), and writes e𝒗 (PRR) 𝒒 to the cache. If 𝒒 is in the cache, e𝒗 (PRR) 𝒒 is reused. As a result, repeated submissions do not have independent pertur￾bations of the original query bin…
Figure 4
Figure 4. Figure 4: Search quality versus latency. Hollow and filled markers indicate LAN and WAN; TripClick and MS MARCO report [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Effect of the number of selected shards 𝑡 on search quality with 𝑀 = 64 and a fixed candidate pool for each dataset. SIFT and LAION are evaluated using Recall, while TripClick and MS MARCO are evaluated using MRR. 0.00 0.08 0.10 0.12 0 1,000 2,000 3,000 4,000 Query Per…
Figure 6
Figure 6. Figure 6: SIFT100M performance under different query [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 6
Figure 6. Figure 6: SIFT100M performance under different query-side per [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: The complete protocol of MESS, including initialization, PRR/IRR query generation, server-side HNSW search, and client-side decryption and reranking. rank of the target item after storage-side and query-side perturba￾tion. Let 𝑁 (𝑑) be the number of non-target database…
Figure 8
Figure 8. Figure 8: Measured retrieval quality and fitted normal-CDF curves. Markers show measurements and lines show nonlinear least [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 35 canonical work pages

  1. [1]

    Ishtiyaque Ahmad, Laboni Sarker, Divyakant Agrawal, Amr El Abbadi, and Trinabh Gupta. 2021. Coeus: A system for oblivious document ranking and retrieval. InProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. 672–690

    work page 2021

  2. [2]

    Kinan Dak Albab, Rawane Issa, Mayank Varia, and Kalman Graffi. 2022. Batched differentially private information retrieval. In31st USENIX Security Symposium (USENIX Security 22). 3327–3344. 12

    work page 2022

  3. [3]

    Amazon Web Services. 2026. Amazon OpenSearch Service. https://aws.amazon. com/opensearch-service/serverless-vector-database/. Accessed: 2026

    work page 2026

  4. [4]

    Ghous Amjad, Seny Kamara, and Tarik Moataz. 2019. Forward and backward private searchable encryption with SGX. InProceedings of the 12th European Workshop on Systems Security. 1–6

    work page 2019

  5. [5]

    Hilal Asi, Fabian Boemer, Nicholas Genise, Muhammad Haris Mughees, Tabitha Ogilvie, Rehan Rishi, Kunal Talwar, Karl Tarbe, Akshay Wadia, Ruiyu Zhu, et al

    work page

  6. [6]

    Martin Aumüller, Anders Bourgeat, and Jana Schmurr. 2020. Differentially Private Sketches for Jaccard Similarity Estimation. InSimilarity Search and Applications - 13th International Conference, SISAP 2020. Springer, 18–32. doi:10.1007/978-3- 030-60936-8_2

    doi:10.1007/978-3- 2020

  7. [7]

    Laura Blackstone, Seny Kamara, and Tarik Moataz. 2019. Revisiting leakage abuse attacks.Cryptology ePrint Archive(2019)

    work page 2019

  8. [8]

    Guoxing Chen, Ten-Hwang Lai, Michael K Reiter, and Yinqian Zhang. 2018. Differentially private access patterns for searchable symmetric encryption. In IEEE INFOCOM 2018-IEEE conference on computer communications. IEEE, 810– 818

    work page 2018

Show all 53 references
  1. [9]

    2020.{SANNS}: Scaling up secure approximate{k-Nearest} neighbors search

    Hao Chen, Ilaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya Razenshteyn, and M Sadegh Riazi. 2020.{SANNS}: Scaling up secure approximate{k-Nearest} neighbors search. In29th USENIX Security Symposium (USENIX Security 20). 2111–2128

    2020

  2. [10]

    Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-Efficient Billion-Scale Ap- proximate Nearest Neighbor Search. InAdvances in Neural Information Processing Systems, Vol. 34. 5199–5212

    2021

  3. [11]

    Thomas Cover and Peter Hart. 1967. Nearest neighbor pattern classification. IEEE transactions on information theory13, 1 (1967), 21–27

    1967

  4. [12]

    Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Search- able symmetric encryption: improved definitions and efficient constructions. In Proceedings of the 13th ACM conference on Computer and communications security. 79–88

    2006

  5. [13]

    Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Ran- domized Aggregatable Privacy-Preserving Ordinal Response. InProceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 1054–1067. doi:10.1145/2660267.2660348

    2014

  6. [14]

    Natasha Fernandes, Yusuke Kawamoto, and Takao Murakami. 2021. Locality Sensitive Hashing with Extended Differential Privacy. InComputer Security – ESORICS 2021, Part II (Lecture Notes in Computer Science, Vol. 12973). Springer, 563–583. doi:10.1007/978-3-030-88428-4_28

    2021 doi

  7. [15]

    Fishkind, Sancar Adali, Heather G

    Donniell E. Fishkind, Sancar Adali, Heather G. Patsolic, Lingyao Meng, Digvijay Singh, Vince Lyzinski, and Carey E. Priebe. 2019. Seeded Graph Matching.Pattern Recognition87 (2019), 203–215. doi:10.1016/j.patcog.2018.09.014

    2019 doi

  8. [16]

    Google Cloud. 2026. Vector Search. https://docs.cloud.google.com/gemini- enterprise-agent-platform/build/vector-search/overview. Accessed: 2026

    2026

  9. [17]

    Alexandra Henzinger, Emma Dauterman, Henry Corrigan-Gibbs, and Nickolai Zeldovich. 2023. Private web search with tiptoe. InProceedings of the 29th symposium on operating systems principles. 396–416

    2023

  10. [18]

    Hong, Henry Corrigan-Gibbs, Sarah Meikle- john, and Vinod Vaikuntanathan

    Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meikle- john, and Vinod Vaikuntanathan. 2023. One server for the price of two: simple and fast single-server private information retrieval. InProceedings of the 32nd USENIX Conference on Security Symposium. USEN...

    2023

  11. [19]

    Guoyu Hu, Shaofeng Cai, Tien Tuan Anh Dinh, Zhongle Xie, Cong Yue, Gang Chen, and Beng Chin Ooi. 2025. HAKES: Scalable Vector Database for Embedding Search Service.Proceedings of the VLDB Endowment18, 9 (2025), 3049–3062. doi:10.14778/3746405.3746427

    2025

  12. [20]

    Zhengbai Huang, Meng Zhang, and Yi Zhang. 2019. Toward Efficient Encrypted Image Retrieval in Cloud Environment.IEEE Access7 (2019), 174541–174550. doi:10.1109/ACCESS.2019.2957497

    2019

  13. [21]

    Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. InProceedings of the thirtieth annual ACM symposium on Theory of computing. 604–613

    1998

  14. [22]

    Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bo- janowski, Armand Joulin, and Edouard Grave. 2021. Unsupervised dense in- formation retrieval with contrastive learning.arXiv preprint arXiv:2112.09118 (2021)

    2021 arXiv

  15. [23]

    Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2021. Billion-Scale Similarity Search with GPUs.IEEE Transactions on Big Data7, 3 (2021), 535–547. doi:10. 1109/TBDATA.2019.2921572

    2021

  16. [24]

    Darya Kaviani, Alp Eren Ozdarendeli, Jinhao Zhu, Yu Ding, and Raluca Ada Popa

  17. [25]

    Ehsan Kazemi, Seyed Hamed Hassani, and Matthias Grossglauser. 2015. Growing a Graph Matching from a Handful of Seeds.Proceedings of the VLDB Endowment 8, 10 (2015), 1010–1021. doi:10.14778/2794367.2794371

    2015

  18. [26]

    Weihao Kong and Wu-Jun Li. 2012. Isotropic hashing.Advances in neural information processing systems25 (2012)

    2012

  19. [27]

    Jiale Lao, Andreas Zimmerer, Olga Ovcharenko, Tianji Cong, Matthew Russo, Gerardo Vitagliano, Michael Cochez, Fatma Özcan, Gautam Gupta, Thibaud Hot- telier, H. V. Jagadish, Kris Kissel, Sebastian Schelter, Andreas Kipf, and Immanuel Trummer. 2026. SemBench: A Benchmark for Se...

    2026

  20. [28]

    Jingyu Li, Zhicong Huang, Min Zhang, Cheng Hong, Jian Liu, Tao Wei, and Wenguang Chen. 2025. Panther: Private approximate nearest neighbor search in the single server setting. InProceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security. 365–379

    2025

  21. [29]

    Hang Liu, Anna Scaglione, and Hoi-To Wai. 2024. Blind Graph Matching Using Graph Signals.IEEE Transactions on Signal Processing72 (2024), 1766–1781. doi:10.1109/TSP.2024.3382840

    2024

  22. [30]

    Yingfan Liu, Yandi Zhang, Jiadong Xie, Hui Li, Jeffrey Xu Yu, and Jiangtao Cui. 2025. Privacy-Preserving Approximate Nearest Neighbor Search on High- Dimensional Data. InProceedings of the IEEE 41st International Conference on Data Engineering (ICDE 2025). 3017–3029. doi:10.11...

    2025

  23. [31]

    Yingfan Liu, Yandi Zhang, Jiadong Xie, Hui Li, Jeffrey Xu Yu, and Jiangtao Cui. 2025. Privacy-preserving approximate nearest neighbor search on high- dimensional data. In2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE, 3017–3029

    2025

  24. [32]

    David G Lowe. 2004. Distinctive image features from scale-invariant keypoints. International journal of computer vision60, 2 (2004), 91–110

    2004

  25. [33]

    Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.IEEE transactions on pattern analysis and machine intelligence42, 4 (2018), 824–836

    2018

  26. [34]

    Arvind Narayanan and Vitaly Shmatikov. 2009. De-anonymizing Social Networks. In2009 30th IEEE Symposium on Security and Privacy. IEEE, 173–187. doi:10.1109/ SP.2009.22

    2009

  27. [35]

    Simon Oya and Florian Kerschbaum. 2021. Hiding the access pattern is not enough: Exploiting search pattern leakage in searchable encryption. In30th USENIX security symposium (USENIX Security 21). 127–142

    2021

  28. [36]

    Sadegh Riazi, Beidi Chen, Anshumali Shrivastava, Dan Wallach, and Fari- naz Koushanfar

    M. Sadegh Riazi, Beidi Chen, Anshumali Shrivastava, Dan Wallach, and Fari- naz Koushanfar. 2019. Sub-Linear Privacy-Preserving Near-Neighbor Search. Cryptology ePrint Archive, Paper 2019/1222. https://eprint.iacr.org/2019/1222

    2019

  29. [37]

    Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001. Item-based collaborative filtering recommendation algorithms. InProceedings of the 10th international conference on World Wide Web. 285–295

    2001

  30. [38]

    Sacha Servan-Schreiber, Simon Langowski, and Srinivas Devadas. 2022. Private approximate nearest neighbor search with sublinear communication. In2022 IEEE Symposium on Security and Privacy (SP). IEEE, 911–929

    2022

  31. [39]

    Zhiwei Shang, Simon Oya, Andreas Peter, and Florian Kerschbaum. 2021. Obfus- cated Access and Search Patterns in Searchable Encryption. InProceedings of the 28th Annual Network and Distributed System Security Symposium (NDSS 2021)

    2021

  32. [40]

    Sivic and Zisserman. 2003. Video Google: A text retrieval approach to object matching in videos. InProceedings ninth IEEE international conference on computer vision. IEEE, 1470–1477

    2003

  33. [41]

    Paul Swoboda, Dagmar Kainmüller, Ashkan Mokarian, Christian Theobalt, and Florian Bernard. 2019. A Convex Relaxation for Multi-Graph Matching. InPro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 11156–11165. doi:10.1109/CVPR.2019.01141

    2019

  34. [42]

    Warren S Torgerson. 1952. Multidimensional scaling: I. Theory and method. Psychometrika17, 4 (1952), 401–419

    1952

  35. [43]

    Sajani Vithana, Martina Cardone, and Flavio P Calmon. 2024. Private approximate nearest neighbor search for vector database querying. In2024 IEEE International Symposium on Information Theory (ISIT). IEEE, 3666–3671

    2024

  36. [44]

    Viet Vo, Shangqi Lai, Xingliang Yuan, Surya Nepal, and Joseph K Liu. 2021. Towards efficient and strong backward private searchable encryption with se- cure enclaves. InInternational Conference on Applied Cryptography and Network Security. Springer, 50–75

    2021

  37. [45]

    Yichuan Wang, Zhifei Li, Shu Liu, Yongji Wu, Ziming Mao, Yilong Zhao, Xiao Yan, Zhiying Xu, Yang Zhou, Ion Stoica, et al . 2025. LEANN: A Low-Storage Vector Index.arXiv preprint arXiv:2506.08276(2025)

    2025

  38. [46]

    Weaviate. 2026. AI Database that developers love. https://weaviate.io/. Accessed: 2026

    2026

  39. [47]

    Kilian Q Weinberger and Lawrence K Saul. 2009. Distance metric learning for large margin nearest neighbor classification.Journal of machine learning research 10, 2 (2009)

    2009

  40. [48]

    Wai Kit Wong, David Wai-lok Cheung, Ben Kao, and Nikos Mamoulis. 2009. Secure kNN computation on encrypted databases. InProceedings of the 2009 ACM SIGMOD International Conference on Management of data. 139–152

    2009

  41. [49]

    Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. 2023. VBASE: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In17th USENIX Symposium on ...

    2023

  42. [50]

    Mingxun Zhou, Elaine Shi, and Giulia Fanti. 2024. Pacmann: Efficient private approximate nearest neighbor search. InThe Thirteenth International Conference on Learning Representations. 13

    2024

  43. [51]

    Jinhao Zhu, Liana Patel, Matei Zaharia, and Raluca Ada Popa. 2025. Compass: Encrypted semantic search with high accuracy. In19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25). 915–938. A Detailed Accounting and Empirical Leakage Evaluation This appe...

    2025

  44. [2024]

    Scalable private search with wally.arXiv preprint arXiv:2406.06761(2024)

    2024 arXiv

  45. [2026]

    Opal: Private Memory for Personal AI.arXiv preprint arXiv:2604.02522 (2026)

    2026 arXiv

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.