Scalable Nearest Neighbor Search for Optimal Transport

Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya Razenshteyn, Tal Wagner
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:497-506, 2020.

Abstract

The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly popular similarity measure for rich data domains, such as images or text documents. This raises the necessity for fast nearest neighbor search algorithms according to this distance, which poses a substantial computational bottleneck on massive datasets. In this work we introduce Flowtree, a fast and accurate approximation algorithm for the Wasserstein-1 distance. We formally analyze its approximation factor and running time. We perform extensive experimental evaluation of nearest neighbor search algorithms in the W_1 distance on real-world dataset. Our results show that compared to previous state of the art, Flowtree achieves up to 7.4 times faster running time.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-backurs20a, title = {Scalable Nearest Neighbor Search for Optimal Transport}, author = {Backurs, Arturs and Dong, Yihe and Indyk, Piotr and Razenshteyn, Ilya and Wagner, Tal}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {497--506}, 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/backurs20a/backurs20a.pdf}, url = {https://proceedings.mlr.press/v119/backurs20a.html}, abstract = {The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly popular similarity measure for rich data domains, such as images or text documents. This raises the necessity for fast nearest neighbor search algorithms according to this distance, which poses a substantial computational bottleneck on massive datasets. In this work we introduce Flowtree, a fast and accurate approximation algorithm for the Wasserstein-1 distance. We formally analyze its approximation factor and running time. We perform extensive experimental evaluation of nearest neighbor search algorithms in the W_1 distance on real-world dataset. Our results show that compared to previous state of the art, Flowtree achieves up to 7.4 times faster running time.} }
Endnote
%0 Conference Paper %T Scalable Nearest Neighbor Search for Optimal Transport %A Arturs Backurs %A Yihe Dong %A Piotr Indyk %A Ilya Razenshteyn %A Tal Wagner %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-backurs20a %I PMLR %P 497--506 %U https://proceedings.mlr.press/v119/backurs20a.html %V 119 %X The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly popular similarity measure for rich data domains, such as images or text documents. This raises the necessity for fast nearest neighbor search algorithms according to this distance, which poses a substantial computational bottleneck on massive datasets. In this work we introduce Flowtree, a fast and accurate approximation algorithm for the Wasserstein-1 distance. We formally analyze its approximation factor and running time. We perform extensive experimental evaluation of nearest neighbor search algorithms in the W_1 distance on real-world dataset. Our results show that compared to previous state of the art, Flowtree achieves up to 7.4 times faster running time.
APA
Backurs, A., Dong, Y., Indyk, P., Razenshteyn, I. & Wagner, T.. (2020). Scalable Nearest Neighbor Search for Optimal Transport. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:497-506 Available from https://proceedings.mlr.press/v119/backurs20a.html.

Related Material