- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes DAPG, a single-layer graph index for dynamic ANN search, combining LSH-based candidate generation, node-specific percentile pruning, global degree control, and localized updates. It is evaluated on seven datasets against eleven ANN baselines.
Critical strengths
S1. Efficient ANN search under frequent updates is important, and the proposed maintenance framework is relatively simple.
S2. The experiments cover multiple datasets, static search, and dynamic workloads.
Critical weaknesses
W1. Insufficient evidence for the pruning mechanism. With fixed candidates and degree cap, Algorithms 3–4 effectively retain the closest min(r_i, T') neighbors. Table 5 shows only a 0.0004 improvement in maximum recall over Global-only at nearly identical average degrees, without uncertainty estimates for this difference.
W2. Insufficient support for dynamic maintenance. Algorithm 1 does not clearly explain incoming-edge tracking or replacement-edge generation after deletion. There is a lack of throughput comparisons at the same recall level.
Questions for authors
Q1. When does percentile pruning produce a different final graph from nearest-neighbor truncation under identical candidates and degree budgets?
Q2. How does Algorithm 1 identify incoming neighbors and restore lost connections after deletion?
Q3. How does distance-based pruning preserve navigational paths, and how much of the search improvement comes from LSH entry points rather than pruning?
Q4. Can dynamic methods be compared at the same Recall@100, including auxiliary-index, incoming-edge maintenance, and cleanup costs?
Q5. The paper proposes an adaptive degree cap (T'=\alpha\bar d_{\mathrm{local}}), but the main static experiments fix (T'=48). What is the independent benefit of the adaptive formulation?
Q6. Could the authors include comparisons with relevant dynamic ANN methods such as IP-DiskANN and SPFresh?
Q7. Why are the reported index size and build time for SIFT100M nearly identical to those for SIFT1M despite the 100-fold difference in scale? Could the authors also clarify the query parameters?
2 comments
We hope these revisions address your concerns. If they do, we would be grateful if you would consider updating your assessment. We are happy to answer any further questions.
We thank Reviewer Fqs7 for the detailed feedback and suggestions for additional
Q1.
We agree that, for a fixed candidate set and degree budget, percentile pruning is equivalent to retaining the closest min(⌈pmi⌉,T′) candidates, apart from ties. In DAPG, percentile pruning is applied to LSH-derived candidates before
SearchInBuilding. The retained candidates seed graph refinement, which may discover more candidates before global degree control is applied. Thus, local pruning can change the candidate set reaching the final pruning stage. We revised Algorithm 2 to make this order explicit.Across five paired SIFT1M builds, Full DAPG and Global-only have the same average degree (36.553) and nearly identical maximum Recall@100 (0.9800±0.0009). At Recall@100 =0.95, Full DAPG reduces latency from 0.881±0.035 ms to 0.848±0.038 ms (3.76%). We therefore narrow our claim to a modest construction-stage efficiency benefit rather than a recall improvement.
Q2.
On deletion, the implementation marks the vertex inactive, removes it from the LSH tables, collects and clears its adjacency list, removes the deleted identifier from those neighbors, and reapplies local and global degree control. Search skips inactive identifiers. The implementation does not maintain a complete reverse-adjacency index or create replacement edges during deletion. Thus, some incoming references may remain inactive and are excluded from traversal. New insertions can create new connections through the normal LSH-seeded
SearchInBuildingprocedure, but deletion alone does not restore every lost path. We revised Algorithm 1 and the discussion.Q3.
We evaluate pruning and LSH entry-point selection separately. With LSH-seeded search fixed, Full DAPG and Global-only have nearly identical maximum Recall@100 (0.9800±0.0009), while Full DAPG reduces latency at Recall@100 =0.95 from 0.881±0.035 ms to 0.848±0.038 ms (3.76%). Thus, local pruning provides a modest efficiency benefit rather than a recall gain. To study entry-point selection, we hold the pruned graph fixed and vary the traversal initialization. We therefore attribute search behavior to both construction-stage refinement and query-time entry-point selection rather than to pruning alone.
Q4.
We added a matched-recall comparison using the same MS-MARCO-1M vectors, queries, ten-round FIFO states, exact ground truth, and one measured worker thread. At Recall@100 ≈0.9594, DAPG achieves 238/71,120/2,393 search/delete/insert OPS, compared with 804/66,963/2,464 for IP-DiskANN. Wolverine++ achieves approximately 1,550/777/860 OPS at Recall@100 =0.9590. IP-DiskANN provides 3.37× higher search throughput and 1.03× higher insertion throughput, while DAPG provides 1.06× higher deletion throughput. Wolverine++ provides higher search throughput, while DAPG provides substantially higher deletion and insertion throughput.
Q5.
The adaptive formulation and fixed-cap evaluation serve different purposes. The rule T′=⌈αdˉlocal⌉ automatically calibrates the global degree budget to the candidate-neighborhood scale of a dataset, reducing the need to retune an absolute cap across datasets. In the main experiments, we fix T′=48 to control final sparsity and isolate local pruning under a common degree budget. Once T′ is fixed, the adaptive and manually selected caps produce the same global pruning operation. Thus, the intended independent benefit of the adaptive formulation is parameter transferability rather than a different graph at an identical cap.
Q6.
We added a direct matched-recall comparison with IP-DiskANN [1] using the same MS-MARCO-1M vectors, queries, ten-round FIFO workload, exact ground truth, and one measured worker thread. At Recall@100 ≈0.9594, DAPG achieves 1.06× the deletion throughput of IP-DiskANN. IP-DiskANN achieves 1.03× higher insertion throughput and 3.37× higher search throughput. We also added the experimental settings, uncertainty across FIFO states, and a DAPG degree sweep. We added SPFresh [2] to Related Work but do not report a direct throughput comparison because SPFresh targets a substantially different billion-scale, disk-resident, partition-based architecture, whereas DAPG is evaluated as an in-memory graph index. We now state this scope difference explicitly.
Q7.
The index-size and build-time results in Fig. 4(b) correspond to SIFT1M. We updated Fig. 4(b) to correctly label the dataset as SIFT1M and revised the corresponding text and caption. For the SIFT100M search experiment in Fig. 4(a), we evaluate k∈{10,20,…,100} with ef=k+150. DAPG uses L=2, K=18, T=24, T′=48, W=1.0, pC=0.95, pQ=0.9, and efC=80.
References
[1] Xu et al. “In-Place Updates of a Graph Index for Streaming Approximate Nearest Neighbor Search,” 2025.
[2] Xu et al. “SPFresh: Incremental In-Place Update for Billion-Scale Vector Search,” SOSP 2023.