Source-linked AI summary
How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?
Tomohiro Yamashita, Daichi Amagata, Yusuke Matsui
TL;DR
No comprehensive methodology evaluates ANNS data deletion under practical use cases, although deletion time and post-deletion search performance matter when selecting algorithms. The paper formalizes logical deletion, physical deletion, and rebuilding, evaluates them on HNSW under practical workloads, and proposes Deletion Control to select a method based on required accuracy. On SIFT1B [12] with b = 105 and α = 0.84, the proposed method almost satisfies required search accuracy and has the smallest total deletion time among strategies that meet it.
Problem
No comprehensive methodology evaluates ANNS data deletion under practical use cases, although deletion time and post-deletion search performance matter when selecting algorithms.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
Deletion Control selects a deletion strategy based on required search accuracy, with the SIFT1B experiment showing it can nearly meet that requirement at the lowest total deletion time among qualifying strategies.
Source: §5 · p. 4, §6 · p. 4Deletion Control’s parameters θ and π cannot be measured without actual query data.
Source: §5 · p. 4
Abstract
from arXiv · showhide
Approximate Nearest Neighbor Search (ANNS) has recently gained significant attention due to its many applications, such as Retrieval-Augmented Generation. Such applications require ANNS algorithms that support dynamic data, so the ANNS problem on dynamic data has attracted considerable interest. However, a comprehensive evaluation methodology for data deletion in ANNS has yet to be established. This study proposes an experimental framework and comprehensive evaluation metrics to assess the efficiency of data deletion for ANNS indexes under practical use cases. Specifically, we categorize data deletion methods in graph-based ANNS into three approaches and formalize them mathematically. The performance is assessed in terms of accuracy, query speed, and other relevant metrics. Finally, we apply the proposed evaluation framework to Hierarchical Navigable Small World, one of the state-of-the-art ANNS methods, to analyze the effects of data deletion, and propose Deletion Control, a method which dynamically selects the appropriate deletion method under a required search accuracy.
1 Introduction
ANNS supports applications including RAG and recommendation systems, where frequent additions and removals make data deletion relevant. The paper addresses the lack of comprehensive, practical evaluation by formalizing graph-based deletion methods, evaluating them, and proposing dynamic method selection.
1 Introduction
- ANNS supports RAG [1] and recommendation systems, where frequent additions and removals of items occur.Research on deletion includes IVF-based [3], product quantization-based [4], and graph-based methods [5] [6] [7].Source: §1 · p. 1
- No comprehensive methodology evaluates deletion under practical use cases, although deletion time and post-deletion search performance matter for selecting ANNS algorithms.Prior evaluations use unrealistic settings and criteria that are not sufficiently comprehensive.Source: §1 · p. 1
- The paper proposes a deployment-oriented evaluation methodology for graph-based ANNS deletion, formalizes three methods, measures practical performance metrics, and dynamically selects among methods.The framework is implemented for HNSW.Source: §1 · p. 1
2 Related Work
Prior work handles deletion in graph-based ANNS through edge reconnection or backup graph strategies, but practical experimental setups remain lacking.
2 Related Work
- FreshDiskANN reconnects neighboring nodes’ edges after deletion, MN-RU maintains a backup graph to preserve accuracy, and IPGM recalculates one-hop neighbors and reconnects edges [5, 6, 7].The passage identifies a lack of practical experimental setup in existing studies.Source: §2 · p. 2
3 Formal Definition of Deletion
The paper formalizes graph-based deletion using shared definitions for the graph and its operations, then distinguishes logical deletion, physical deletion, and rebuilding. These approaches differ in how they handle deleted nodes and graph structure.
3 Formal Definition of Deletion
- The paper formalizes three baseline graph-based deletion methods: logical deletion, physical deletion, and rebuilding.The methods are defined using pseudocode.Source: §3 · p. 2
- A graph is represented by node vectors P and neighborhood sets N, with each node’s neighbors recorded by index.Each node p_i is a d-dimensional vector, and N_i is its set of neighboring-node indices.Source: §3 · p. 2
- SEARCH maps a query and graph to approximate neighbors, CONSTRUCT maps nodes to neighborhoods, and DELETE maps deletion indices and graph data to updated nodes and neighborhoods.DELETE outputs subsets P′ and N′ of the original node and neighborhood sets.Source: §3 · p. 2
- Logical deletion flags removed nodes for exclusion from search; physical deletion removes their edges and memory contents, while rebuilding reconstructs the graph from remaining data.Figure 1 summarizes the three deletion approaches.Source: §3 · p. 2, Figure 1 · p. 3
4 Experiments
The experiments assess deletion approaches across datasets using accuracy, throughput, and repeated update workloads. Results show distinct trade-offs in search performance, deletion speed, and accuracy over repeated updates.
4 Experiments
- Experiments use SIFT1M, GIST1M, SIFT1B, DEEP1M, and Glove100Angular, with repeated equal-batch insertions and deletions; the SIFT1B subset contains 2 × 10^6 points.Search accuracy is measured by 1-Recall@10; speed uses QPS-search, QPS-add, and QPS-delete, including a QPS-Recall curve.Source: §4 · p. 3
- Rebuilding has the highest post-update search performance, followed by physical and logical deletion; logical deletion is fastest, while rebuilding is relatively slower than physical deletion for frequent small batches.With repeated updates, logical deletion’s search accuracy deteriorates, while physical deletion’s accuracy stabilizes at a constant value.Source: §4 · p. 3
5 Deletion Control
Deletion Control chooses between physical deletion and logical deletion followed by rebuilding to keep search accuracy above a target. On SIFT1B, it almost met the target and had the lowest total deletion time among strategies that did.
5 Deletion Control
- The setting assumes repeated updates with the same batch size and uses a small query training set with known ground truth.The paper states that θ and π cannot be measured without actual query data.Source: §5 · pp. 3–4
- The policy estimates θ as the lowest measured physical-deletion 1-Recall@10 and estimates π from the average per-step decline under logical deletion.It approximates logical-deletion accuracy as linear in update step, using training-set experiments.Source: §5 · p. 4
- When α < θ, the policy repeatedly uses physical deletion; when α ≥ θ, it performs π logical-deletion steps followed by rebuilding.The latter schedule is intended to keep 1-Recall@10 at or above α, with rebuilding restoring it to R0.Source: §5 · p. 4
- On SIFT1B [12] with b = 105 and α = 0.84, the proposed method almost satisfied the required search accuracy and had the smallest total deletion time among strategies meeting that requirement.The estimates were θ = 0.816 and π = 1, so the selected strategy alternated between logical deletion and rebuilding.Source: §5 · p. 4
6 Conclusion
The study formalizes three baseline deletion approaches, establishes practical evaluation settings and metrics, evaluates the approaches on HNSW, and proposes accuracy-guided deletion control.
6 Conclusion
- The study formally defines logical deletion, physical deletion, and rebuilding for ANNS, with mathematical formulations.Source: §6 · p. 4
- It establishes an experimental setup and evaluation metrics aligned with practical use cases.Source: §6 · p. 4
- It implements and empirically evaluates the baseline deletion approaches on HNSW.Source: §6 · p. 4
- It proposes an algorithm that selects a deletion method based on required accuracy.Source: §6 · p. 4
A Algorithm of three deletion methods
The appendix specifies logical deletion, physical deletion, and rebuilding as distinct graph-based deletion approaches. They differ in whether data remains in the graph, is removed directly, or the index is reconstructed.
A.1 Logical deletion
- Logical deletion updates flags and filters deleted vectors from search results, while leaving deleted nodes in the graph.This is efficient to perform, but retained nodes accumulate memory and repeated updates can leave too few non-deleted vectors for filtering.Source: §A.1 · p. 6
A.2 Physical deletion
- Physical deletion removes data without rebuilding, but deleting edges changes graph structure and may affect search performance.When implemented properly, it need not retain vector data for distance calculations and can be the most memory-efficient method.Source: §A.2 · p. 6
A.3 Rebuilding
- Rebuilding reconstructs the index from the graph nodes, preserving an optimal structure to avoid search-performance degradation and maintain appropriate memory use.The node set P is required for construction and distance computations when an update batch arrives.Source: §A.3 · p. 6
B Experimental Settings
The experimental setup repeatedly deletes and inserts equal-sized batches while keeping the index size fixed, recomputing ground truth for each update step.
B Experimental Settings
- The setup performs s update iterations and maintains n indexed vectors, with n ≤ no, regardless of s.The original base-vector set is Po, and queries come from Q.Source: B Experimental Settings · pp. 6–7
- Ground truth is recomputed for each update step using a full search over the query set Q.The ground-truth set has the same size as Q.Source: B Experimental Settings · p. 6
- Each update step deletes a batch of b consecutive indexed vectors, then inserts b new vectors.The deletion indices are consecutive, and inserted vectors are always new.Source: B Experimental Settings · p. 7
- Small b represents frequent small updates, while large b represents larger updates in fewer iterations.Source: B Experimental Settings · p. 7
- Experiments ran single-threaded on an Intel Core i7-13700H processor with 32GB RAM and Ubuntu 22.04.5.Source: B Experimental Settings · p. 7
C Mathematical Representation of Evaluation Metrics
The section defines search accuracy through 1-Recall@10 and query processing speed through QPS-based measures, including a QPS-Recall curve.
C Mathematical Representation of Evaluation Metrics
- The study uses 1-Recall@10 as its search-accuracy measure, with k set to 10; higher recall indicates better search accuracy.Source: C Mathematical Representation of… · p. 7
- QPS measures query processing speed; the study evaluates search, insertion, and deletion rates as QPS-search, QPS-add, and QPS-delete.Source: C Mathematical Representation of… · p. 7
- The QPS-Recall curve plots QPS-search against 1-Recall@10 while varying HNSW search parameters; upper-right placement indicates higher search performance.Source: C Mathematical Representation of… · p. 7
D All Experimental Results
Across the reported datasets, rebuilding best preserves search performance and memory usage, while logical deletion degrades search and increases memory use. Insertion-speed findings vary with deletion method and batch size.
D All Experimental Results
- The experiments cover SIFT1M, GIST1M, DEEP1M, Glove100Angular, and SIFT1B, with SIFT1B reported at batch sizes b = 105 and b = 103.Source: D All Experimental Results · p. 7
D.1 QPS-Recall
- Across datasets, rebuilding maintains search performance through repeated updates, while logical deletion degrades both accuracy and speed; physical deletion is slightly below rebuilding.Source: §D.1 · p. 8
D.2 1-Recall@10
- Logical-deletion accuracy falls with repeated updates; rebuilding is highest, physical deletion is lower, and physical deletion stabilizes after enough operations.Larger batch sizes result in higher converged accuracy.Source: §D.2 · p. 8
D.3 Memory Usage
- Logical-deletion memory consumption grows linearly with each step, while memory usage remains unchanged for rebuilding and physical deletion.The authors say the latter methods effectively reclaim memory when data is deleted.Source: §D.3 · p. 8
D.4 QPS-add
- At b = 105, insertion speed remains unchanged across repeated updates and is highest for physical deletion; logical-deletion speed varies at b = 103.Source: §D.4 · p. 8
D.5 QPS-delete
Deletion speed and search speed favor different methods: logical deletion is fastest to delete, while physical deletion gives the highest search speed. Rebuilding slows with higher vector dimensionality and smaller deletion batches, and Algorithm 4 presents Deletion Control.
D.5 QPS-delete
- Approximately 10^9[1/s] for logical deletion versus at most 10^3[1/s] for rebuilding and physical deletion; at b = 10^5, deletion takes approximately 10^-4[s] versus up to 10^2[s] for physical deletion.The reported deletion-speed comparison holds across datasets.Source: §D.5 · p. 8, Figure 5 · p. 10, Figure 6 · p. 10
- Only rebuilding’s deletion speed is affected by vector dimensionality, because rebuilding requires distance calculations and higher-dimensional vectors increase their time.The comparison uses SIFT1M at 128 dimensions and GIST1M at 960 dimensions.Source: §D.5 · p. 8
- When SIFT1B’s batch size falls from b = 10^5 to b = 10^3, physical-deletion speed remains nearly constant while rebuilding slows by approximately a factor of 100.Physical deletion primarily performs memory operations for the specified deletion queries; rebuilding time stays almost constant for relatively small datasets regardless of deleted-point count.Source: §D.5 · pp. 8–9
D.6 QPS-search
- Across datasets, physical deletion gives the highest search speed, while logical deletion gives the lowest, likely because it filters retrieved results using a flag array.Physical deletion’s sparser graph is cited as a likely reason for its faster search.Source: §D.6 · p. 9
E Deletion Control
- Algorithm 4 presents the Deletion Control strategy, with required search accuracy and estimated θ and π as inputs.The algorithm listing identifies these inputs.Source: E Deletion Control · p. 9, §D.5 · p. 9