# Proximity Graph Maintenance for Fast Online Nearest Neighbor Search

arXiv: https://arxiv.org/abs/2206.10839 · HTML: https://mlsanity.com/paper/2206.10839/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2022.

## Built on by (most cited first, 5 of 5)

- [A Comprehensive Survey on Trustworthy Recommender Systems](https://mlsanity.com/paper/2209.10117/) (2022)
- [Practice with Graph-based ANN Algorithms on Sparse Data: Chi-square Two-tower model, HNSW, Sign Cauchy Projections](https://mlsanity.com/paper/2306.07607/) (2023)
- [CoopHash: Cooperative Learning of Multipurpose Descriptor and Contrastive Pair Generator via Variational MCMC Teaching for Supervised Image Hashing](https://mlsanity.com/paper/2210.04288/) (2022)
- [How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?](https://mlsanity.com/paper/2512.06200/) (2025)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)

## Abstract (arXiv)

Approximate Nearest Neighbor (ANN) search is a fundamental technique for (e.g.,) the deployment of recommender systems. Recent studies bring proximity graph-based methods into practitioners' attention -- proximity graph-based methods outperform other solutions such as quantization, hashing, and tree-based ANN algorithm families. In current recommendation systems, data point insertions, deletions, and queries are streamed into the system in an online fashion as users and items change dynamically. As proximity graphs are constructed incrementally by inserting data points as new vertices into the graph, online insertions and queries are well-supported in proximity graph. However, a data point deletion incurs removing a vertex from the proximity graph index, while no proper graph index updating mechanisms are discussed in previous studies. To tackle the challenge, we propose an incremental proximity graph maintenance (IPGM) algorithm for online ANN. IPGM supports both vertex deletion and insertion on proximity graphs. Given a vertex deletion request, we thoroughly investigate solutions to update the connections of the vertex. The proposed updating scheme eliminates the performance drop in online ANN methods on proximity graphs, making the algorithm suitable for practical systems.