Scalable Nearest Neighbor Search For Optimal Transport

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keybackurs2019scalable

Related papers

• Tensor-train Point Cloud Compression And Efficient Approximate Nearest-neighbor Search (2024)0.00
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44
• Efficient Autotuning Of Hyperparameters In Approximate Nearest Neighbor Search (2018)6.77
• Random Binary Trees For Approximate Nearest Neighbour Search In Binary Space (2017)2.26
• Lightweight-yet-efficient: Revitalizing Ball-tree For Point-to-hyperplane Nearest Neighbor Search (2023)10.01
• Efficient Approximate Nearest Neighbor Search For Multiple Weighted \(l_{p\leq2}\) Distance Functions (2020)0.00
• Adaptive Estimation For Approximate K-nearest-neighbor Computations (2019)0.00
• Efficient And Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016)22.99