Graph-based Nearest Neighbor Search: From Practice to Theory

Liudmila Prokhorenkova, Aleksandr Shekhovtsov
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:7803-7813, 2020.

Abstract

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-prokhorenkova20a, title = {Graph-based Nearest Neighbor Search: From Practice to Theory}, author = {Prokhorenkova, Liudmila and Shekhovtsov, Aleksandr}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {7803--7813}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/prokhorenkova20a/prokhorenkova20a.pdf}, url = {https://proceedings.mlr.press/v119/prokhorenkova20a.html}, abstract = {Graph-based approaches are empirically shown to be very successful for the nearest neighbor search (NNS). However, there has been very little research on their theoretical guarantees. We fill this gap and rigorously analyze the performance of graph-based NNS algorithms, specifically focusing on the low-dimensional ($d \ll \log n$) regime. In addition to the basic greedy algorithm on nearest neighbor graphs, we also analyze the most successful heuristics commonly used in practice: speeding up via adding shortcut edges and improving accuracy via maintaining a dynamic list of candidates. We believe that our theoretical insights supported by experimental analysis are an important step towards understanding the limits and benefits of graph-based NNS algorithms.} }
Endnote
%0 Conference Paper %T Graph-based Nearest Neighbor Search: From Practice to Theory %A Liudmila Prokhorenkova %A Aleksandr Shekhovtsov %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-prokhorenkova20a %I PMLR %P 7803--7813 %U https://proceedings.mlr.press/v119/prokhorenkova20a.html %V 119 %X Graph-based approaches are empirically shown to be very successful for the nearest neighbor search (NNS). However, there has been very little research on their theoretical guarantees. We fill this gap and rigorously analyze the performance of graph-based NNS algorithms, specifically focusing on the low-dimensional ($d \ll \log n$) regime. In addition to the basic greedy algorithm on nearest neighbor graphs, we also analyze the most successful heuristics commonly used in practice: speeding up via adding shortcut edges and improving accuracy via maintaining a dynamic list of candidates. We believe that our theoretical insights supported by experimental analysis are an important step towards understanding the limits and benefits of graph-based NNS algorithms.
APA
Prokhorenkova, L. & Shekhovtsov, A.. (2020). Graph-based Nearest Neighbor Search: From Practice to Theory. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:7803-7813 Available from https://proceedings.mlr.press/v119/prokhorenkova20a.html.

Related Material