litlas
Log inCreate account

Scalable Nearest Neighbor Search for Optimal Transport

Authors: Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya P. Razenshteyn, Tal Wagner - International Conference on Machine Learning, ICML 2020 cited by 61

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.

The Hungarian Method forthe Assignment ProblemThe Hungarian Method for the Assignment ProblemSimilarity estimationtechniques from roundin…Similarity estimation techniques from rounding algorithmsA tight bound onapproximating arbitrary…A tight bound on approximating arbitrary metrics by tree metricsPlanar Earthmover is notin L_1Planar Earthmover is not in L_1Hamming Embedding andWeak Geometric…Hamming Embedding and Weak Geometric Consistency for Large Scale Image SearchProduct Quantization forNearest Neighbor SearchProduct Quantization for Nearest Neighbor SearchDistributedRepresentations of Word…Distributed Representations of Words and Phrases and their CompositionalityGlove: Global Vectorsfor Word RepresentationGlove: Global Vectors for Word RepresentationFrom Word Embeddings ToDocument DistancesFrom Word Embeddings To Document DistancesWord Mover's Embedding:From Word2Vec to…Word Mover's Embedding: From Word2Vec to Document EmbeddingTree-SlicedApproximation of…Tree-Sliced Approximation of Wasserstein DistancesHierarchical OptimalTransport for Document…Hierarchical Optimal Transport for Document RepresentationTree-SlicedApproximation of…Tree-Sliced Approximation of Wasserstein DistancesSANNS: Scaling Up SecureApproximate k-Nearest…SANNS: Scaling Up Secure Approximate k-Nearest Neighbors SearchUniversal consistency ofWasserstein k-NN…Universal consistency of Wasserstein k-NN classifierMulticlassClassification via…Multiclass Classification via Class-Weighted Nearest NeighborsDual Regularized OptimalTransportDual Regularized Optimal TransportApproximation Algorithmsfor 1-Wasserstein…Approximation Algorithms for 1-Wasserstein Distance Between Persistence DiagramsFast Dataset Search withEarth Mover's DistanceFast Dataset Search with Earth Mover's DistanceLAMBO: LandmarksAugmentation With…LAMBO: Landmarks Augmentation With Manifold-Barycentric OversamplingLearning UltrametricTrees for Optimal…Learning Ultrametric Trees for Optimal Transport RegressionA Class of TopologicalPseudodistances for Fas…A Class of Topological Pseudodistances for Fast Comparison of Persistence DiagramsAn Empirical Study ofSimplicial…An Empirical Study of Simplicial Representation Learning with Wasserstein DistanceScalable NearestNeighbor Search for…Scalable Nearest Neighbor Search for Optimal TransportEarlier referencesFocus paperCiting papersOlderNewer

Click a node to pin it, click the empty canvas to go back to this paper, or hover to preview. Open a node’s page from its title.