On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search

Majid Daliri, Mohammadreza Daneshvaramoli, Purna Dutta +4

Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in compari…