Reproduce “CleANN: Efficient Full Dynamism in Graph-based Approximate Nearest Neighbor Search” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ziyu Zhang, Yuanhao Wei, Joshua Engels, Julian Shun
CleanANN presents a fully dynamic graph-based approximate nearest-neighbor index that handles insertions, deletions, and searches concurrently without relying on periodic global rebuilding. By combining search-guided bridge edges, local repair of tombstoned neighborhoods, and semi-lazy slot reuse, it maintains high recall while delivering 1.14–1.26× the mixed-workload throughput of IP-DiskANN and 12–18× that of Wolverine++ in reported experiments.
Key insights
- Deletion maintenance can be made workload-driven: repairing paths that searches actually use is sufficient to preserve navigability without reconnecting every incoming edge of each deleted node.
- Semi-lazy memory reclamation trades complete immediate cleanup for prompt slot reuse, while residual stale edges are later filtered or pruned through normal graph operations.
- Guided bridge construction provides a modest but consistent recall benefit, showing that ordinary insertions and searches can also serve as opportunities for online graph improvement.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.