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.
Introduction
Measuring similarity between complex data distributions, such as word embeddings in a document or pixel intensities in an image, requires metrics that account for underlying structure. The Optimal Transport (OT) distance, or Wasserstein-$1$ ($W_1$) distance, is ideal for this purpose but suffers from high computational costs. Exact calculations are often cubic ($O(s^3)$) in the support size $s$, and even popular approximations like the Sinkhorn algorithm are quadratic ($O(s^2)$). This complexity makes $k$-Nearest Neighbor Search ($k$-NNS) prohibitive on large datasets.
While linear-time ($O(s)$) tree-based methods like Quadtree offer a solution, their accuracy tends to degrade as the dataset size $n$ grows. We introduce Flowtree, a linear-time approximation that decouples flow discovery from cost evaluation to achieve high accuracy that is independent of dataset size.
The Flowtree Algorithm
Flowtree builds upon the framework of tree-based embeddings but introduces a critical modification. The standard approach (e.g., Quadtree) embeds the ground metric space into a randomly shifted tree of hypercubes and approximates the $W_1$ distance using the tree's internal edge weights.
Flowtree follows a three-step process:
- Embedding: The ground metric space is embedded into a randomly shifted tree.
- Flow Discovery: An optimal flow is found on the tree in linear time using a bottom-up greedy approach.
- Cost Evaluation: Instead of using tree weights, Flowtree calculates the cost of the specific flow paths found on the tree using the original ground metric distances.
This decoupling allows Flowtree to leverage the speed of tree-based optimization while maintaining the fidelity of the original metric space.
Empirical Stability and Performance
A key theoretical and empirical finding is that Flowtree’s approximation error remains stable regardless of the number of points $n$ in the dataset. In contrast, traditional Quadtree methods show fluctuating and declining accuracy as $n$ increases.
We evaluated Flowtree across several real-world datasets, including 20news, Amazon, and MNIST. In these experiments, Flowtree consistently served as a high-quality filter for $k$-NNS pipelines. It achieves accuracy levels comparable to more expensive quadratic methods like Sinkhorn while maintaining the speed of linear-time approximations.
Results and Conclusion
Flowtree demonstrates a significant improvement in end-to-end search performance. By acting as an efficient intermediate filter, it reduces the number of candidates that require expensive exact OT calculations. Our results show that Flowtree-based pipelines are $3.7$x to $7.4$x faster than previous state-of-the-art methods.
In summary, Flowtree provides a scalable, linear-time solution for Optimal Transport that does not sacrifice accuracy for speed. Its independence from dataset size makes it particularly suitable for massive, high-dimensional search tasks.
Summary updated