Scalable Nearest Neighbor Search for Optimal Transport
Arturs Backurs · Yihe Dong · Piotr Indyk · Ilya Razenshteyn · Tal Wagner
Keywords:
Large Scale Learning and Big Data
Metric Learning
Natural Language Processing / Dialogue
Optimization - Large Scale, Parallel and Distributed
2020 Poster
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.
Video
Chat is not available.
Successful Page Load