Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation

Shangqi Lu, Yufei Tao

Proximity graph-based methods have emerged as a leading paradigm for approximate nearest neighbor (ANN) search in the system community. This paper presents fresh insights into the…