Pith.

Databases · arXiv:2611.16516 v1 · submitted 12 Nov 2026 · 57 references

Authenticated Approximate Nearest Neighbor Search in Outsourced Vector Databases

Yuanhang Zhou, Xinyi Zhang, Cheng Xu, Jianliang Xu

The paper says

“Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds.”

more of the abstract

However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. Existing authenticated ANN approaches face substantial scalability challenges. They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a 6.6 × speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

Holds up, with conditions. Well-engineered system with impressive latency results, but the security proof for the aggregated IPA protocol has a gap that should be addressed before acceptance. This line is wrong

2 major objections · 5 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 57 references say.

The paper says, at Appendix B, Theorem 7.1

The review did not quote this passage.

Pith says: Objection 1 of 2 · major

The knowledge-soundness proof of the IPA aggregation protocol relies on rewinding the adversary to obtain n transcripts and then solving a Vandermonde system. The authors state that 'while extending to n branches introduces a polynomial reduction loss, the success probability remains non-negligible for polynomial n,' but they do not provide a concrete bound or analysis.

more of objection 1

For the Forking Lemma, the extractor's success probability is typically ε' ≥ ε^n / poly(λ). In practical deployments, n (the number of visited nodes) can be thousands (e.g., high-recall scenarios on OpenAI3072). Even if ε is non-negligible (e.g., 1/λ), ε' becomes negligible for n ≥ 2. Thus the claimed knowledge soundness does not hold for the parameter regime targeted by VIDA. This is a load-bearing issue: the security of the entire scheme depends on the aggregation protocol being secure. The authors must either provide a proof with tighter bound (e.g., constant-size aggregation by reducing n, or using a different technique like batch proofs with logarithmic dependence) or explicitly analyze how the extractor's success probability depends on n and justify that it remains non-negligible for the maximum n encountered in their experiments.

The paper says, at Appendix B, Theorem 7.1

The review did not quote this passage.

Pith says: Objection 2 of 2 · major

The proof sketch assumes the extractor can obtain n valid transcripts with distinct challenges from an adversary that succeeds with non-negligible probability. However, the General Forking Lemma typically requires that the adversary's success probability is at least (some polynomial factor) to obtain two transcripts; extending to n transcripts would require either a more complex lemma or a different approach.

more of objection 2

The paper does not cite or include a version of the Forking Lemma that provides n forks with only polynomial loss. The extractor construction therefore lacks a rigorous foundation.

5 minor objections

The paper says, at Section II, Definition 2.1

Pith says: minor objection 1 of 5

The security definition references an ideal result from a 'deterministic ANN algorithm,' but ANN algorithms are inherently approximate. The definition should clarify that the ideal result is the output of a designated deterministic algorithm (e.g., HNSW with fixed parameters) rather than the exact nearest neighbors. The text implicitly assumes this, but making it explicit would avoid confusion.

The paper says, at Section IV-C, Equation (1)

Pith says: minor objection 2 of 5

The Fiat-Shamir challenge in Equation (1) is computed as r = H(C_q | C_1 | IP_1 | ... | C_n | IP_n). For security, the adversary's view should include all commitments and inner products. However, the inner products IP_i are claimed values that the prover computes; if they are included before verification, the adversary could choose them adaptively. The proof should address that the challenge is bound to these values via the hash.

show 3 more

The paper says, at Section VIII-A

Pith says: minor objection 3 of 5

The experimental section states that the source code is available, but it is not checked whether the implementation includes all cryptographic primitives (e.g., Bulletproofs with Ristretto255). This is a minor reproducibility concern.

The paper says, at Table I

Pith says: minor objection 4 of 5

The notation table lists symbols but does not include definitions for some used in Section VI (e.g., η_j, H_exaj, H_quaj). Adding these would improve readability.

The paper says, at Appendix D

Pith says: minor objection 5 of 5

Figure 13 and 14 are duplicates of earlier figures; it would be clearer to present only unique additional results rather than repeating the same panels.

What would settle it

Derive the extractor's success probability for the aggregated IPA protocol from Appendix B, using the standard General Forking Lemma (Pointcheval‑Stern) and the concrete parameters from the experiments: n ≈ 1000, security parameter λ = 128. Compute the maximum adversary advantage ε for which the extractor still succeeds with non‑negligible probability. If ε must be ≥ 0.99 for n=1000, then the proof is insufficient; if ε can be plausibly small (e.g., 2^{-80}), the proof collapses.

from the skeptic's reading

How the review went

4 readings by deepseek-v4-flash · 13 Nov 2026

  1. Reader holds up, with conditions confidence moderate
  2. Skeptic partly agrees 37 s · 35,640 tokens read, 2,583 written
  3. Editor wrote the verdict above 37 s · 36,509 tokens read, 1,397 written
  4. Referee major revision: 2 major objections, 5 minor 34 s · 35,995 tokens read, 1,790 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

This paper tackles a real and timely problem—authenticating approximate nearest neighbor search in outsourced vector databases. The authors propose VIDA, which combines vector commitments, an aggregated inner-product argument (IPA), and a topology-aware Merkle spanning tree (MeST). The engineering is solid and the experimental evaluation is the strongest part: VIDA achieves up to 6.6× end-to-end speedup and reduces data transfer by 99.2% over baselines on high-dimensional datasets. The ablation study shows that both aggregation and MeST contribute meaningfully. The paper is clearly written and the problem is well-motivated.

However, the security proof for the core aggregation primitive has a gap that warrants careful consideration. The stress-test note is on point: the knowledge-soundness proof in Appendix B rewinds the adversary n times to obtain n transcripts, then solves a Vandermonde system. The authors claim that extending to n branches introduces a polynomial reduction loss and that success probability remains non-negligible for polynomial n. But the standard Forking Lemma gives a bound of roughly εn / poly(λ). For realistic workloads where n is in the thousands (the number of visited nodes in high-recall search), this becomes negligible even if ε is non-negligible. The paper does not provide a concrete bound or justify why n is small enough. This is not a minor oversight; it affects the entire security claim of the scheme. A plausible fix would be to use a different aggregation technique that avoids exponential dependence, or to restrict the aggregation to smaller batches with a formal argument.

Other concerns are minor. The paper does not discuss timing side channels from proof generation, and the offline construction overhead is non-trivial (5× build time over baselines), but these are acceptable trade-offs. The quantization-aware variant shows limited gains under low recall or low-dimensional settings, which the authors honestly acknowledge in Appendix E.

Overall, this is a serious piece of work that deserves a proper peer review. The experimental results are compelling, but the security proof needs to be tightened before it can be trusted. I would bring this to a reading group with the caveat that the proof is under scrutiny, and I would cite it only after the security analysis is resolved.

The strongest objection

The security of VIDA's core aggregation primitive depends on the claim that the aggregation protocol satisfies computational knowledge soundness (Theorem 7.1). The proof in Appendix B uses the General Forking Lemma to rewind the adversary n times, obtaining n valid transcripts with distinct Fiat‑Shamir challenges. The extractor then solves a Vandermonde system to recover the individual witnesses. The authors state that ‘while extending to n branches introduces a polynomial reduction loss, the success probability remains non‑negligible for polynomial n.’ This statement is not justified with a concrete bound. The Forking Lemma typically gives a reduction of the form ε' ≥ ε^n / poly(λ), where ε is the original adversary advantage and ε' is the extractor's advantage. For realistic workloads, n (the number of visited nodes) can be in the thousands (e.g., high‑recall search on OpenAI3072). If ε is, say, 1/λ (non‑negligible), then ε' ≈ (1/λ)^n, which is negligible for n ≥ 2. Thus the extractor's success probability may be negligible, and the knowledge soundness argument fails for the parameter regime in which the scheme is deployed. The paper does not address this issue or provide an alternative proof technique that avoids exponential dependence on n.

The reader identified the lack of concrete security bounds and reliance on rewinding as the weakest assumption. My concern sharpens this: the proof's exponential dependence on n creates a concrete gap for the parameter sizes used in the experiments. However, the overall scheme is still likely sound because other knowledge‑sound arguments for batch proofs (e.g., Bulletproofs aggregation) use more robust techniques (e.g., splitting lemmas with polynomial loss). The paper could address this by either adopting a different aggregation scheme with a tighter reduction or by explicitly bounding n to a small constant and arguing that visited sets remain small. The empirical results are strong, and the problem is well‑motivated. Therefore, I do not change the verdict; the paper remains conditionally acceptable subject to a tightened security analysis or an explicit discussion of the reduction loss for practical n.

The referee's report

If the security proofs hold, VIDA represents a significant advance in verifiable outsourced ANN search, addressing the bandwidth bottleneck that has limited prior approaches. The combination of vector commitments, aggregated IPA, topology-aware ADS, and quantization-aware pruning is novel and practically motivated. The experimental evaluation is thorough and demonstrates clear improvements over baselines on diverse datasets and network conditions.

Pith's reading of the paper (a machine's summary, not the authors')

The paper aims to solve the problem of verifying the integrity of approximate nearest neighbor search when the vector database is outsourced to an untrusted cloud. Existing solutions require transmitting entire high-dimensional vectors to the client for distance recomputation, causing severe bandwidth bottlenecks. VIDA replaces raw vectors with compact Pedersen commitments and uses an aggregated inner product argument to verify distances without revealing the vectors. Additionally, a topology-aware Merkle spanning tree (MeST) aligns the authentication structure with the graph traversal pattern, reducing structural proof size. The paper demonstrates up to a 6.6× end-to-end latency improvement and 99.2% reduction in data transfer time over prior methods.

What carries the argument. The key machinery is threefold: (1) vector commitments (Pedersen commitments) that bind to a vector without revealing it, (2) an aggregated inner product argument (AggIPA) that batch-verifies multiple inner products between the query vector and visited data vectors using a single proof, and (3) the MeST index, a Merkle tree built as a distance-aware minimum spanning tree of the proximity graph, which places co-visited nodes close together in the tree to minimize proof size.

Core claim. The central discovery is that by combining vector commitments with an aggregated inner product argument, the client can authenticate distance computations for all visited graph nodes from a single compact proof, eliminating the transmission of high-dimensional vectors. Moreover, constructing the Merkle authentication tree as a distance-aware spanning tree of the proximity graph significantly compresses the structural authentication paths for frequently co-visited nodes. Together these techniques make verifiable ANN search practical for large-scale high-dimensional datasets.

The premise it rests on. The security of the aggregated IPA protocol relies on the random oracle model and the discrete logarithm assumption; if either is broken, the verification can be forged. Additionally, the proof for aggregation requires rewinding the adversary a polynomial number of times, which assumes the adversary's success probability remains non-negligible after rewinding.

If the paper is right (Pith's inferences, not the authors')

Outsourced vector databases can now offer verifiable ANN search with latency comparable to unauthenticated search, enabling trust in cloud-based retrieval-augmented generation and recommendation systems.

The aggregation technique reduces client-side verification cost from linear in the number of visited nodes to nearly constant, making high-recall searches feasible even on bandwidth-constrained networks.

MeST's topology-aware construction generalizes to other graph-based query verification problems beyond ANN, such as shortest-path or subgraph queries.

The quantization-aware extension further reduces the number of exact-distance authentications, extending the approach to scenarios with extremely limited bandwidth or device memory.

The IPA aggregation proof could likely be further compressed using recursive SNARKs, potentially reducing proof size below the current constant-size implementation and lowering verification time further.

MeST's distance-aware spanning tree could be adapted for verifiable graph navigation in other contexts, such as authenticated shortest-path queries on road networks or provenance tracking in graph databases.

The security model assumes an honest data owner and client; a malicious client colluding with the cloud could break verification in weaker trust models, so practical deployments may need additional safeguards against client-side attacks.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds. However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. Existing authenticated ANN approaches face substantial scalability challenges. They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a 6.6 × speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-13

The authors' main claim, as the classifier picked it out 1.00

“Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a $6.6\times$ speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.07 · human participants 0.02 · controlled comparison 0.65 · randomized assignment 0.01 · states quantitative result 0.99 · compares with prior results 0.97 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. background 1.00 0.05 0.01 asserted 1.00
To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds. background 1.00 0.04 0.01 asserted 0.97
However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. background 0.91 0.05 0.02 hedged possibility 0.93
Existing authenticated ANN approaches face substantial scalability challenges. gap 0.75 0.05 0.02 asserted 1.00
They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. gap 0.75 0.04 0.02 asserted 1.00
In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. contribution 1.00 0.89 0.14 asserted 1.00
VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. method 0.85 0.93 0.08 asserted 1.00
Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. contribution 0.80 0.94 0.05 asserted 1.00
Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. contribution 0.62 0.94 0.03 asserted 1.00
Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a $6.6\times$ speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods. result 1.00 0.97 0.86 asserted 1.00

What kind of paper the classifier reports this is: method or tool 1.00 · evidence from observation or experiment 0.99

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 7,488 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

Figures (15)
Figure 1 of the paper
Figure 1. System Overview string, graph, or time series). The distance between any two objects is evaluated by a metric function δ(·, ·). Formally, a k-Nearest Neighbor (kNN) query Q = (k, xq) requests the k nearest neighbors of the query vector xq. The exact query result set, denoted as Rexact ⊆ D, satisfies |Rexact| = k and δ(xq, xi) ≤ δ(xq, xi ′ ) for any oi ∈ Rexact and any oi ′ ∈ D \ Rexact. In practice, exact kNN search is compu￾tationally prohibitive in high dimensions due to the curse of dimensionality [9]. This paper therefore focuses on Approxi￾mate Nearest Neighbor (ANN) search. By…
Figure 3 of the paper
Figure 3. Strawman Index MHT nodes. It then authenticates the reconstructed hash against the one signed by the DO. This validates the integrity of all returned vi ∈ Vgraph. Next, the client assembles these authenticated nodes to build a local subgraph I ′ . Finally, the client replays the search over I ′ to obtain a local result R′ . The verification succeeds iff R′ = R and the local traversal does not try to access any unverified node outside Vgraph. Example. In Figure 2b, for a 1-NN query Q, the traversal starts from entry point v1 and visits the node set Vgraph = {v1, v3, v5, v6, v9, v11,…
Figure 4 of the paper
Figure 4. Preliminary Evaluation on OpenAI3072 severe burden on network bandwidth. To enable local search replay, the protocol must transmit the complete raw high￾dimensional vector xi for every visited node vi ∈ Vgraph. This bottleneck is especially severe in modern AI applications that use high-dimensional embeddings. To quantify the overhead, we conducted a preliminary evaluation on the OpenAI3072 dataset [21] (d = 3072). As illustrated in
Figure 5 of the paper
Figure 5. MeST Index global objective while employing a local greedy strategy to prioritize the closest neighbors as a tie-breaker when multiple choices exist (Line 9). By prioritizing local distance within a hop-constrained structure, the resulting ADS ensures that frequently co-visited nodes share common ancestor paths in the MHT, thereby maximizing proof compression in the VO. Having defined the spanning tree structure, we now address the second challenge: determining the optimal data to store in each Merkle tree node to support verifiable search while revealing minimal information.…
Figure 6 of the paper
Figure 6. Quantization-aware MeST Index Verifiable Search. During query processing, the SP ex￾ecutes the quantization-aware graph search in Algorithm 3. The search follows the same priority-queue-guided traversal as the original graph search. When a node vi is dequeued and expanded, the SP adds it to Vmerkle and scans each neighbor vj ∈ Adji . It first obtains the current search threshold δth and computes the lower bound LBj from ηj and xq (Line 8). If LBj > δth, then vj is pruned without exact distance compu￾tation and recorded in the quantization-pruned node set Vqua (Line 10). Otherwise,…
Figure 7 of the paper
Figure 7. Latency on Different Recalls 0 1,600 3,200 4,800 6,400 25 50 100 200 400 (a) OpenAI3072 Latency (ms) k (Recall=0.99) Algorithm: ANNProof VIDA* ANNProof-Q VIDA*-Q Fill: Server Transfer Client 0 2,000 4,000 6,000 25 50 100 200 400 (b) WIT k (Recall=0.98) Algorithm: ANNProof VIDA* ANNProof-Q VIDA*-Q Fill: Server Transfer Client 0 400 800 1,200 1,600 2,000 25 50 100 200 400 (c) LAION k (Recall=0.97) Algorithm: ANNProof VIDA* ANNProof-Q VIDA*-Q Fill: Server Transfer Client 0 1,400 2,800 4,200 5,600 25 50 100 200 400 (d) Wikipedia k (Recall=0.98) Algorithm: ANNProof VIDA* ANNProof-Q…
Figure 8 of the paper
Figure 8. Latency of Varying k 0 3,000 6,000 9,000 12,000 15,000 18,000 40 200 300 1,000 (a) OpenAI3072 Latency (ms) Bandwidth (Mbps) 0 4,000 8,000 12,000 16,000 20,000 40 200 300 1,000 (b) WIT Bandwidth (Mbps) 0 800 1,600 2,400 3,200 4,000 4,800 40 200 300 1,000 (c) LAION Bandwidth (Mbps) 0 2,500 5,000 7,500 10,000 12,500 40 200 300 1,000 (d) Wikipedia Bandwidth (Mbps) 0 1,500 3,000 4,500 6,000 7,500 40 200 300 1,000 (e) Msmarco Bandwidth (Mbps) 0 2,000 4,000 6,000 8,000 10,000 40 200 300 1,000 (f) Cluster Bandwidth (Mbps) 0 1,600 3,200 4,800 6,400 25 50 100 200 400 (a) OpenAI3072 Latency…
Figure 10 of the paper
Figure 10. Scalability Test duces communication overhead, even against the quantization￾aware baseline. Latency generally increases with k as more nodes are visited and larger VOs are generated, but the growth is nonlinear. At a fixed recall, small-k queries may still require large search parameters, so node visits do not decrease proportionally with k. This effect makes the raw-vector-based baselines costly even at small k, whereas our schemes grow more slowly. On OpenAI3072, when k increases from 25 to 400, the latency of VIDA*-Q increases by only 2.0×, compared with 2.5× for VIDA*, 3.7×…
Figure 11 of the paper
Figure 11. Ablation Study only 3.9× and 3.9×, respectively. This result suggests that our IPA-based distance authentication significantly reduces the dependence of verification cost on vector dimensionality, making our schemes particularly well suited for modern high￾dimensional embedding workloads. We also evaluate query latency at lower dimensions (see Section E-B). 2) Offline Construction: We evaluate offline index initial￾ization in terms of construction time and ADS size. Relative to their corresponding baselines, VIDA* and VIDA*-Q require 5.5× and 5.4× the construction time on average,…
Figure 12 of the paper
Figure 12. An Example on a Multi-layered Graph is the hash for the neighbors at the l-th layer, defined as H (l) i = H(g (l) i ) = H({IDj | Cj | ∥xj∥}∀vj∈Adj(l) i ). The remainder of the ADS structure and its construction algorithm are identical to those described in Section V-A. Example. Consider the two-layered proximity graph in
Figure 13 of the paper
Figure 13. Latency of Varying k: Additional Datasets Impact of k. We vary k from 25 to 400 while maintaining target recalls for each dataset. As shown in
Figure 14 of the paper
Figure 14. Latency on Different Network Settings: Additional Datasets
Figure 15 of the paper
Figure 15. ADS Build Time 0 1x105 2x105 3x105 4x105 5x105 OpenAI3072 WIT LAIONWikipediaMSMARCO Cluster Index Size (MB)

Showing 13 of the paper's 15 figures. Figures are the authors', reproduced from the paper.

References (57)
  1. [1] “Milvus,” https://milvus.io, [Accessed: 2026-6-1] on Pith
  2. [2] “Qdrant,” https://qdrant.tech, [Accessed: 2026-6-1] on Pith
  3. [3] “Weaviate,” https://weaviate.io, [Accessed: 2026-6-1] on Pith
  4. [4] P. Lewis, E. Perez, A. Piktus, F. Petroni, V . Karpukhin, N. Goyal, H. K ¨uttler, M. Lewis, W.-t. Yih, T. Rockt ¨aschelet al., “Retrieval- augmented generation for knowledge-intensive NLP tasks,”Proc. Adv. Neural Inf. Process. Syst., vol. 33, pp. 9459–9474, 2020 on Pith
  5. [5] S. Zhang, L. Yao, A. Sun, and Y . Tay, “Deep learning based recom- mender system: A survey and new perspectives,”ACM Comput. Surv., vol. 52, no. 1, pp. 1–38, 2019 on Pith
  6. [6] V . Karpukhin, B. Oguz, S. Min, P. S. Lewis, L. Wu, S. Edunov, D. Chen, and W.-t. Yih, “Dense passage retrieval for open-domain question answering,” inProc. Conf. Empir. Methods Nat. Lang. Process. (EMNLP), 2020, pp. 6769–6781 on Pith
  7. [7] Y . Liu, J. Cui, Z. Huang, H. Li, and H. T. Shen, “SK-LSH: An efficient index structure for approximate nearest neighbor search,”Proc. VLDB Endow., vol. 7, no. 9, pp. 745–756, 2014 on Pith
  8. [8] H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 1, pp. 117–128, 2010 on Pith
  9. [9] Y . A. Malkov and D. A. Yashunin, “Efficient and robust approxi- mate nearest neighbor search using hierarchical navigable small world graphs,”IEEE Trans. Pattern Anal. Mach. Intell., vol. 42, no. 4, pp. 824–836, 2018 on Pith
  10. [10] C. Fu, C. Xiang, C. Wang, and D. Cai, “Fast approximate nearest neighbor search with the navigating spreading-out graph,”Proc. VLDB Endow., vol. 12, no. 5, pp. 461–474, 2019 on Pith
  11. [11] J. J. Pan, J. Wang, and G. Li, “Survey of vector database management systems,”VLDB J., vol. 33, no. 5, pp. 1591–1615, 2024 on Pith
  12. [12] Y . Song, X. Zhou, C. S. Jensen, and J. Xu, “Vector search for the future: From memory-resident, static heterogeneous storage, to cloud- native architectures,” inProc. ACM Manage. Data, 2026 on Pith
  13. [13] Z. Niu, X. Tian, X. Peng, and X. Chen, “BlendHouse: A cloud-native vector database system in ByteHouse,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2025, pp. 4332–4345 on Pith
  14. [14] N. Upreti, H. V . Simhadri, H. S. Sundar, K. Sundaram, S. Boshra, B. Perumalswamy, S. Atri, M. Chisholm, R. R. Singh, G. Yanget al., “Cost-effective, low latency vector search with azure cosmos db,”Proc. VLDB Endow., vol. 18, no. 12, pp. 5166–5183, 2025 on Pith
  15. [15] Y . Zhang, J. Katz, and C. Papamanthou, “IntegriDB: Verifiable SQL for outsourced databases,” inProc. ACM SIGSAC Conf. Comput. Commun. Secur. (CCS), 2015, pp. 1480–1491 on Pith
  16. [16] Y . Zhang, D. Genkin, J. Katz, D. Papadopoulos, and C. Papamanthou, “vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases,” inProc. IEEE Symp. Secur. Privacy (SP). IEEE, 2017, pp. 863–880 on Pith
  17. [17] X. Li, C. Weng, Y . Xu, X. Wang, and J. Rogers, “ZKSQL: Verifiable and efficient query evaluation with zero-knowledge proofs,”Proc. VLDB Endow., vol. 16, no. 8, 2023 on Pith
  18. [18] L. Lu, Z. Wen, Y . Yuan, Q. He, J. Chen, and Z. Liu, “ANNProof: Build- ing a verifiable and efficient outsourced approximate nearest neighbor search system on blockchain,”Future Gener. Comput. Syst., vol. 156, pp. 206–220, 2024 on Pith
  19. [19] C. Wang, J. Zhang, X. Liu, K. Wei, and B. Feng, “Verifiable graph- based approximate nearest neighbor search,” inProc. Int. Conf. Adv. Data Min. Appl.Springer, 2024, pp. 3–17 on Pith
  20. [20] R. C. Merkle, “A certified digital signature,” inProc. CRYPTO. Springer, 1989, pp. 218–238 on Pith
show 37 more
  1. [21] “OpenAI3072,” https://huggingface.co/datasets/Qdrant/ dbpedia-entities-openai3-text-embedding-3-large-3072-1M, [Accessed: 2026-6-1] on Pith
  2. [22] C. Gentry, S. Halevi, and V . Lyubashevsky, “Practical non-interactive publicly verifiable secret sharing with thousands of parties,” inProc. EUROCRYPT. Springer, 2022, pp. 458–487 on Pith
  3. [23] J. Zhang, M. Su, X. Liu, and G. Wang, “Springproofs: Efficient inner product arguments for vectors of arbitrary length,” inProc. IEEE Symp. Secur. Privacy (SP). IEEE, 2024, pp. 3147–3164 on Pith
  4. [24] T. P. Pedersen, “Non-interactive and information-theoretic secure verifi- able secret sharing,” inProc. CRYPTO. Springer, 1991, pp. 129–140 on Pith
  5. [25] R. Henry and I. Goldberg, “Batch proofs of partial knowledge,” inProc. Appl. Cryptogr. Netw. Secur.Springer, 2013, pp. 502–517 on Pith
  6. [26] M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols,” inProc. ACM SIGSAC Conf. Comput. Commun. Secur. (CCS), 1993, pp. 62–73 on Pith
  7. [27] W. Zhou, Y . Lu, H. Li, and Q. Tian, “Scalar quantization for large scale image search,” inProc. ACM Int. Conf. Multimedia (MM). ACM, 2012, pp. 169–178 on Pith
  8. [28] J. Gao and C. Long, “RaBitQ: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search,”Proc. ACM Manage. Data, vol. 2, no. 3, pp. 1–27, 2024 on Pith
  9. [29] B. B ¨unz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell, “Bulletproofs: Short proofs for confidential transactions and more,” in Proc. IEEE Symp. Secur. Privacy (SP). IEEE, 2018, pp. 315–334 on Pith
  10. [30] J. Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit, “Efficient zero- knowledge arguments for arithmetic circuits in the discrete log setting,” inProc. Annu. Int. Conf. Theory Appl. Cryptogr. Tech.Springer, 2016, pp. 327–357 on Pith
  11. [31] M. Wang, X. Xu, Q. Yue, and Y . Wang, “A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search,”Proc. VLDB Endow., vol. 14, no. 11, pp. 1964–1978, 2021 on Pith
  12. [32] K. Srinivasan, K. Raman, J. Chen, M. Bendersky, and M. Najork, “WIT: Wikipedia-based image text dataset for multimodal multilingual machine learning,” inProc. ACM SIGIR Int. Conf. Res. Dev. Inf. Retr., 2021, pp. 2443–2449 on Pith
  13. [33] C. Schuhmann, R. Vencu, R. Beaumont, R. Kaczmarczyk, C. Mullis, A. Katta, T. Coombes, J. Jitsev, and A. Komatsuzaki, “LAION-400M: Open dataset of clip-filtered 400 million image-text pairs,”arXiv preprint arXiv:2111.02114, 2021 on PithPith's reviewarXiv
  14. [34] “Wikipedia,” https://huggingface.co/datasets/Cohere/ wikipedia-2023-11-embed-multilingual-v3, [Accessed: 2026-6-1] on Pith
  15. [35] “Msmarco,” https://huggingface.co/datasets/Cohere/msmarco-v2. 1-embed-english-v3, [Accessed: 2026-6-1] on Pith
  16. [36] “Bulletproofs,” https://github.com/zkcrypto/bulletproofs, [Accessed: 2026-6-1] on Pith
  17. [37] “Toxiproxy,” https://github.com/Shopify/toxiproxy, [Accessed: 2026-6- 1] on Pith
  18. [38] X. Yang, H. Lin, Z. Li, F. Qian, X. Li, Z. He, X. Wu, X. Wang, Y . Liu, Z. Liao, D. Hu, and T. Xu, “Mobile access bandwidth in practice: Measurement, analysis, and implications,” inProc. ACM SIGCOMM Conf., 2022, pp. 114–128 on Pith
  19. [39] I. Azizi, K. Echihabi, and T. Palpanas, “Graph-based vector search: An experimental evaluation of the state-of-the-art,”Proc. ACM Manage. Data, vol. 3, no. 1, pp. 1–31, 2025 on Pith
  20. [40] K. Lu, M. Kudo, C. Xiao, and Y . Ishikawa, “HVS: Hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search,”Proc. VLDB Endow., vol. 15, no. 2, pp. 246–258, 2021 on Pith
  21. [41] W. Li, Y . Zhang, Y . Sun, W. Wang, M. Li, W. Zhang, and X. Lin, “Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement,”IEEE Trans. Knowl. Data Eng., vol. 32, no. 8, pp. 1475–1488, 2019 on Pith
  22. [42] S. Jayaram Subramanya, F. Devvrit, H. V . Simhadri, R. Krishnawamy, and R. Kadekodi, “Diskann: Fast accurate billion-point nearest neighbor search on a single node,”Proc. Adv. Neural Inf. Process. Syst., vol. 32, 2019 on Pith
  23. [43] H. Ootomo, A. Naruse, C. Nolet, R. Wang, T. Feher, and Y . Wang, “Cagra: Highly parallel graph construction and approximate nearest neighbor search for GPUs,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2024, pp. 4236–4247 on Pith
  24. [44] Y . Lin, K. Zhang, Z. He, Y . Jing, and X. S. Wang, “Survey of filtered approximate nearest neighbor search over the vector-scalar hybrid data,” arXiv preprint arXiv:2505.06501, 2025 on PithPith's reviewarXiv
  25. [45] C. Zhang, C. Xu, H. Wang, J. Xu, and B. Choi, “Authenticated keyword search in scalable hybrid-storage blockchains,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2021, pp. 996–1007 on Pith
  26. [46] H. Wang, C. Xu, C. Zhang, J. Xu, Z. Peng, and J. Pei, “vChain+: Optimizing verifiable blockchain boolean range queries,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2022, pp. 1927–1940 on Pith
  27. [47] P. Sun, L. Zhang, J. Liu, C. Tang, and J. Wang, “E 3FS: Efficient, secure, and verifiable fuzzy search with data updates in hybrid-storage blockchains,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2025, pp. 3890–3903 on Pith
  28. [48] Z. Yao, T. Li, J. Xin, Y . Li, C. Wang, Z. Wang, D. Srivastava, and C. S. Jensen, “VGQ: Enabling verifiable graph queries on blockchain systems,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2025, pp. 3602–3614 on Pith
  29. [49] C. Zhang, C. Xu, J. Xu, and B. Choi, “Distributed kNN query authenti- cation,” inProc. IEEE Int. Conf. Mobile Data Manage. (MDM). IEEE, 2018, pp. 167–176 on Pith
  30. [50] N. Cui, K. Qian, T. Cai, J. Li, X. Yang, J. Cui, and H. Zhong, “Towards multi-user, secure, and verifiable kNN query in cloud database,”IEEE Trans. Knowl. Data Eng., vol. 35, no. 9, pp. 9333–9349, 2023 on Pith
  31. [51] Z. Qiu, W. Qu, J. Zhang, and B. Yuan, “V3DB: Audit-on-demand zero-knowledge proofs for verifiable vector search over committed snapshots,”Proc. VLDB Endow., vol. 19, no. 10, pp. 2604–2616, 2026 on Pith
  32. [52] Y . Jiang, X. Yang, X. Liu, Y . Guo, and J. Zhang, “zkRAG: Efficiently proving RAG retrieval in zero knowledge,”Cryptology ePrint Archive, no. 2026/709, 2026. [Online]. Available: https://eprint.iacr.org/2026/709 on Pith
  33. [53] J. Zhu, L. Patel, M. Zaharia, and R. A. Popa, “Compass: Encrypted semantic search with high accuracy,” inProc. USENIX Symp. Oper. Syst. Des. Implement. (OSDI), 2025, pp. 915–938 on Pith
  34. [54] H. Chen, I. Chillotti, Y . Dong, O. Poburinnaya, I. Razenshteyn, and M. S. Riazi, “SANNS: Scaling up secure approximate k-nearest neighbors search,” inProc. USENIX Secur. Symp., 2020, pp. 2111–2128 on Pith
  35. [55] J. Li, Z. Huang, M. Zhang, C. Hong, J. Liu, T. Wei, and W. Chen, “Panther: Private approximate nearest neighbor search in the single server setting,” inProc. ACM SIGSAC Conf. Comput. Commun. Secur. (CCS), 2025, pp. 365–379 on Pith
  36. [56] M. Zhou, E. Shi, and G. Fanti, “Pacmann: Efficient private approximate nearest neighbor search,”Cryptology ePrint Archive, 2024 on Pith
  37. [57] Y . Liu, Y . Zhang, J. Xie, H. Li, J. X. Yu, and J. Cui, “Privacy-preserving approximate nearest neighbor search on high-dimensional data,” inProc. IEEE Int. Conf. Data Eng. (ICDE). IEEE, 2025, pp. 3017–3029. APPENDIXA MESTFORMULTI-LAYEREDGRAPHS In graph-based ANN search, a pr... on Pith

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment