Timezone: »

 
Poster
Scalable Nearest Neighbor Search for Optimal Transport
Arturs Backurs · Yihe Dong · Piotr Indyk · Ilya Razenshteyn · Tal Wagner

Tue Jul 14 07:00 AM -- 07:45 AM & Tue Jul 14 06:00 PM -- 06:45 PM (PDT) @
in Poster Session 1 »

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.

Keywords: Large Scale Learning and Big Data · Metric Learning · Natural Language Processing / Dialogue · Optimization - Large Scale, Parallel and Distributed

Author Information

Arturs Backurs (TTIC)
Yihe Dong (Microsoft)

I am a researcher and engineer passionate about machine learning and its applications. My interests lie primarily in geometric deep learning, robust ML, and natural language processing.

Piotr Indyk (MIT)
Ilya Razenshteyn (Microsoft Research Redmond)
Tal Wagner (MIT)

More from the Same Authors