Skip to yearly menu bar Skip to main content


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 ]


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.

Chat is not available.