Scalable Nearest Neighbor Search for Optimal Transport

The hungarian method for the assignment problem

Harold W Kuhn · 1955

Earlier work this paper cites.

The quadtree and related hierarchical data structures

Hanan Samet · 1984

Earlier work this paper cites.

The metrical interpretation of superreflexivity in banach spaces

Jean Bourgain · 1986

Earlier work this paper cites.

A linear-time algorithm for minimum cost flow on undirected one-trees

Bahman Kalantari and Iraj Kalantari · 1995

Earlier work this paper cites.

Probabilistic approximation of metric spaces and its algorithmic applications

Yair Bartal · 1996

Earlier work this paper cites.

On approximating arbitrary metrices by tree metrics

Yair Bartal · 1998

Earlier work this paper cites.

Approximating a finite metric by a small number of tree metrics

Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin · 1998

Earlier work this paper cites.

The earth mover’s distance as a metric for image retrieval

Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas · 2000

Earlier work this paper cites.

Algorithmic applications of low-distortion geometric embeddings

Piotr Indyk · 2001

Earlier work this paper cites.

Similarity estimation techniques from rounding algorithms

Moses S Charikar · 2002

Earlier work this paper cites.

Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields

Jon Kleinberg and Eva Tardos · 2002

Earlier work this paper cites.

Bounded geometries, fractals, and low-distortion embeddings

Anupam Gupta, Robert Krauthgamer, and James R Lee · 2003

Earlier work this paper cites.

Fast image retrieval via embeddings

Piotr Indyk and Nitin Thaper · 2003

Earlier work this paper cites.

Video google: A text retrieval approach to object matching in videos

Josef Sivic and Andrew Zisserman · 2003

Cited alongside, same era.

Topics in optimal transportation

Cédric Villani · 2003

Cited alongside, same era.

A tight bound on approximating arbitrary metrics by tree metrics

Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar · 2004

Cited alongside, same era.

Approximation algorithms for the 0-extension problem

Gruia Calinescu, Howard Karloff, and Yuval Rabani · 2005

Cited alongside, same era.

Nonembeddability theorems via fourier analysis

Subhash Khot and Assaf Naor · 2006

Cited alongside, same era.

Ramsey partitions and proximity data structures

Manor Mendel and Assaf Naor · 2006

Cited alongside, same era.

Better embeddings for planar earth-mover distance over sparse sets

Artūrs Bačkurs and Piotr Indyk · 2014

Later among the works it cites.

Glove: Global vectors for word representation

Jeffrey Pennington, Richard Socher, and Christopher Manning · 2014

Later among the works it cites.

Snowflake universality of wasserstein spaces

Original

Alexandr Andoni, Assaf Naor, and Ofer Neiman · 2015

Later among the works it cites.

From word embeddings to document distances

Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger · 2015

Later among the works it cites.

Practical data-dependent metric compression with provable guarantees

Piotr Indyk, Ilya Razenshteyn, and Tal Wagner · 2017

Later among the works it cites.

Approximate nearest neighbor search in high dimensions