Graph-based Nearest Neighbor Search: From Practice to Theory

• DOI: 10.48550/arxiv.1907.00845
• Publication Date: 2019-01-01
• Authors: Liudmila Prokhore...; Aleksandr Shekhov...
• Keywords: Heuristics; Best bin first; Nearest neighbor graph

Graph-based approaches are empirically shown to be very successful for the nearest neighbor search (NNS). However, there has been little research on their theoretical guarantees. We fill this gap and rigorously analyze performance of graph-based NNS algorithms, specifically focusing low-dimensional (d << \log n) regime. In addition basic greedy algorithm graphs, we also most heuristics commonly used in practice: speeding up via adding shortcut edges improving accuracy maintaining a dynamic list candidates. believe that our insights supported by experimental analysis an important step towards understanding limits benefits algorithms.