Enhancing HNSW Index for Real-Time Updates: Addressing Unreachable Points and Performance Degradation

I. INTRODUCTION

• Graph-based methods demonstrate superior empirical search performance compared with other index types.The introduction describes ANNS as relevant to data mining, information retrieval, and recommendation systems.Source: §I · p. 1
• Static graph indices cannot accommodate the real-time insertions and removals needed when application data changes.The introduction uses changing documents in RAG as an example of this need.Source: §I · pp. 1–2
• HNSW can make points inaccessible after deletions and insertions, while mixed updates are less efficient than queries and can delay them.The introduction notes that inaccessible relevant points can compromise retrieval accuracy in recommendation and RAG systems.Source: §I · p. 2
• MN-RU improves deletion and insertion speed while alleviating unreachable points, and its redesigned strategies reduce their number and growth rate.The paper also proposes practical solutions for mitigating the phenomenon and improving mixed-operation efficiency.Source: §I · p. 2
• The evaluation reports that the proposed approach outperforms the native HNSW strategy.The authors implemented a comparative evaluation platform to assess the methods.Source: §I · p. 2

A. Approximate Nearest Neighbor Search Algorithms

• Tree-based partitioning works effectively on low-dimensional data, but beyond 10 dimensions it can become slower than brute-force linear scans.Pyramid technique and iDistance are cited as strategies addressing the curse of dimensionality.Source: A. Approximate Nearest Neighbor Search… · p. 2
• Hash-based methods project high-dimensional points into lower-dimensional spaces, but often require many hash tables for satisfactory search outcomes.The passage names VHP, LCCS-LSH, PMLSH, and R2SLH as variants.Source: A. Approximate Nearest Neighbor Search… · p. 2
• Product quantization compresses vectors into compact codes to reduce memory use and supports distance estimation between raw vectors and compressed codes.Related approaches, aim to mitigate quantization errors and improve query precision.Source: A. Approximate Nearest Neighbor Search… · p. 2
• Graph-based methods support high-dimensional ANNS, but exact KNN graph construction grows exponentially with node count and construction can face memory constraints.Approximate graphs and cluster algorithms are discussed as alternatives for graph construction and query processing.Source: A. Approximate Nearest Neighbor Search… · p. 3
• FreshDiskANN [27], SPANN, and SPFresh are presented as recent approaches addressing dynamic-index freshness and search or update performance.The passage attributes StreamingMerge deletions and subsequent insertions to FreshDiskANN, balanced clustering to SPANN, and throughput and latency improvements to SPFresh.Source: A. Approximate Nearest Neighbor Search… · p. 3

B. HNSW

• For replaced updates, HNSW checks for deleted points, gathers one- and two-hop neighbors, prunes candidate neighbors, updates connections, and inserts the new point.The procedure is implemented through addPoint, updatePoint, and repairConnectionsForUpdate.Source: B. HNSW · p. 3
• Replaced updates reuse deleted-point storage for new insertions, preventing index growth and maintaining space utilization.The passage contrasts this with leaving deleted entries in the index after inserting new points.Source: B. HNSW · p. 3
• The proposed approach extends HNSW by optimizing deletions and insertions to improve dynamic-update efficiency and mitigate unreachable points.The stated aims include reducing latency and promoting graph connectivity.Source: B. HNSW · p. 3

III. ISSUES IN UPDATE EFFICIENCY AND UNREACHABLE POINTS

• At roughly 90% recall, replaced-update insertion is 5 to 10 times slower than query operations on GIST and ImageNet.The passage reports that replaced-update efficiency lags query efficiency across three public datasets.Source: §III · p. 3, Figure 1 · p. 3

A. Causes of Unreachable Points

• An unreachable point has outgoing edges but no incoming edges in any graph layer.In the example, deleting node d removes node v’s only incoming edge, leaving it unvisited unless it is the entry point.Source: A. Causes of Unreachable Points · pp. 3–4, Figure 2 · p. 4
• Replacing a deleted point can create zero-in-degree points because the repair strategy may remove edges from affected points to their original neighbors.Those original neighbors may then go unvisited in later searches unless they are entry points.Source: A. Causes of Unreachable Points · p. 4
• The Sift experiment deletes 5% of points per iteration, excluding previously unreachable points, and reinserts them to demonstrate unreachable-point growth.The supplied caption specifies the repeated deletion and reinsertion procedure; it does not provide a numerical outcome.Source: Figure 3 · p. 4

B. Demonstration on Specific Datasets

• After about 3,000 iterations, unreachable points reach 3%–4% of the original dataset, while recall declines by about 3% with the same configuration.The reported recall decline becomes more severe with further iterations and cannot be mitigated by increasing ef.Source: B. Demonstration on Specific Datasets · p. 4

IV. METHODOLOGY

• MN-RU improves update efficiency and reduces unreachable points, while a backup index and dual search address their effect on queries.The architecture integrates the HNSW index in the upper-level application and MN-RU within the index.Source: §IV · p. 4

A. Dual Indexes Design

• The backup index is built from points not found by an HNSW search configured to retrieve all points, avoiding recurrent full reconstruction.The procedure extracts the unfound set and constructs a separate HNSW index for it.Source: A. Dual Indexes Design · p. 5
• A threshold triggers backup-index reconstruction after a specified number of replaced updates; its value is empirically set to 40,000.The application layer can adjust the threshold according to its needs.Source: A. Dual Indexes Design · p. 5

• dualSearch searches the primary and backup indexes, merges their results, sorts by distance to the query, and returns the top k points.The backup index is dedicated to managing unreachable points, so the combined query covers points absent from the primary index after replaced updates.Source: B. Dual Index Search · p. 5
• Each index search returns k nearest neighbors using the query point and dynamic candidate-list size ef before the two result sets are combined.Source: B. Dual Index Search · p. 5
• The paper reports that this approach improves search accuracy and maintains robust query performance even when unreachable points are present.Source: B. Dual Index Search · p. 5

C. Index Maintenance

• The candidate set is narrowed because absent edges to two-hop neighbors were previously judged suboptimal by HNSW and are likely to remain so after an update.Source: C. Index Maintenance · p. 6
• The repair algorithm updates one-hop neighbors that included the deleted point, selecting candidates from each neighbor’s original neighbors and the deleted point’s neighbors.It excludes two-hop neighbors from the candidate set and has time complexity O(M^2) per layer, compared with the original approach’s O(M^3) per layer.Source: C. Index Maintenance · p. 6
• For deletion, the method appends the deleted point to deletedList; for replacement, MN-RU repairs connectivity before inserting the new point.The new point inherits the deleted point’s layer level and is then inserted using the standard HNSW process.Source: C. Index Maintenance · p. 6

V. EXPERIMENTS

• Experiments ran in C++ on an Intel Xeon E5-2678 v3 at 2.50 GHz with 110 GB memory, using 40 threads for insertion, deletion, and retrieval.Source: §V · p. 6

A. Datasets

• The evaluation used four datasets with different sizes and dimensions.The supplied data-statistics passage identifies the table but provides no values.Source: A. Datasets · p. 7, Table 1 · p. 7
• Sift2M is the first two million vectors from Sift1B, which contains one billion 128-dimensional SIFT descriptors.Source: A. Datasets · p. 7

B. Baselines

• MN-RU methods reselect neighbors for points mutually connected to deleted points; MN-THN-RU also reselects for qualifying two-hop neighbors.The α and β variants use α-RNG pruning with α = 1; γ uses α = 1.1 and directly implements Algorithm 2.Source: B. Baselines · p. 7
• The primary baseline is HNSW-RU, which replaces deleted nodes in the index to maintain graph structure and efficacy.The experiments construct HNSW using dataset-specific parameters; the remaining methods use consistent settings.Source: B. Baselines · p. 7

C. Experimental Scenarios And Metrics

• Full coverage uses 100 iterations, dividing Gist, Sift, and ImageNet into 100 parts and deleting and reinserting a portion per iteration.Source: C. Experimental Scenarios And Metrics · p. 7
• Random updates run for 200 iterations on Gist, Sift, and ImageNet, with 10,000 randomly generated labels deleted and reinserted per iteration.Source: C. Experimental Scenarios And Metrics · p. 7
• The new-data scenario starts with the first million Sift2M points, then replaces 100,000 points per iteration for 10 iterations, ending with the second million.Source: C. Experimental Scenarios And Metrics · p. 7

D. Update Time Efficiency

• 2–4 times faster in all scenarios, MN-RU variants achieve lower update times than HNSW-RU.The comparison covers full-coverage, random, and new-data scenarios.Source: D. Update Time Efficiency · p. 8

E. Unreachable Points Growth

• Approximately 3% to 4% of Gist points and 2% to 3% of ImageNet points are unreachable for HNSW-RU after 200 iterations; MN-RU γ and MN-THN-RU maintain fewer.Unreachable-point counts increase for every method over prolonged update operations.Source: E. Unreachable Points Growth · p. 8, Figure 8 · p. 9, Figure 9 · p. 9
• The original query sets—1,000 Gist queries and 200 ImageNet queries—make it difficult to observe unreachable-point effects on accuracy, especially for K ≤100.Source: E. Unreachable Points Growth · p. 8
• With τ = 40,000, rebuilding the backup index every four iterations significantly reduces unreachable points versus HNSW-RU on GIST under full coverage.Source: E. Unreachable Points Growth · p. 9

VI. CONCLUSION

• MN-THN-RU and MN-RU γ with the backup index mitigate HNSW replaced-update limitations by improving mixed-operation efficiency and maintaining better graph connectivity.Source: §VI · p. 9