We consider the point-to-point (approximate) shortest-path query problem, which is the
following generalization of the classical single-source (SSSP) and all-pairs shortest-path …

(MATH) A locality sensitive hashing scheme is a distribution on a family \F of hash functions
operating on a collection of objects, such that for two objects x, y, Pr h εF h (x)= h (y)= sim (x …

In this paper, we show that any n point metric space can be embedded into a distribution
over dominating tree metrics such that the expected stretch of any edge is O (log n). This …

The doubling constant of a metric space (X, d) is the smallest value/spl lambda/such that
every ball in X can be covered by/spl lambda/balls of half the radius. The doubling …

The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be
covered using 2k balls of radius r. This concept for abstract metrics has been proposed as a …

We prove that every n-point metric space of negative type (in particular, every n-point subset
of L1) embeds into a Euclidean space with distortion O (√ log n log log n), a result which is …

Metric Embedding plays an important role in a vast range of application areas such as
computer vision, computational biology, machine learning, networking, statistics, and …

Abstract The Optimal Transport (aka Wasserstein) distance is an increasingly popular
similarity measure for rich data domains, such as images or text documents. This raises the …

We devise a new embedding technique, which we call measured descent, based on
decomposing a metric space locally, at varying speeds, according to the density of some …

Many classical problems in geometry and analysis involve the gluing together of local
information to produce a coherent global picture. Inevitably, the difficulty of such a procedure …