Ramsey partitions and proximity data structures

Manor Mendel^{∗} The Open University of Israel

Assaf Naor^{†} Microsoft Research

Abstract

This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in [8]). We then proceed to construct optimal Ramsey partitions, and use them to show that for every ε ∈ (0, 1), any n-point metric space has a subset of size n^{1−ε} which embeds into Hilbert space with distortion O(1/ε). This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor [5], in addition to considerably simplifying its proof. We use our new Ramsey partitions to design the best known approximate distance oracles when the distortion is large, closing a gap left open by Thorup and Zwick in [31]. Namely, we show that for any n point metric space X, and k ≥ 1, there exists an O(k)-approximate distance oracle whose storage requirement is O (n^{1+1/k}), and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking.

∗Email: mendelma@gmail.com. Part of this work was carried out while M. Mendel was visiting Microsoft Research.

†Email: anaor@microsoft.com.

1 Introduction

Motivated by the search for a non-linear version of Dvoretzky’s theorem, Bourgain, Figiel and Milman [8] posed the following problem, which is known today as the metric Ramsey problem: Given a target distortion α > 1 and an integer n, what is the largest k such that any n-point metric space has a subset of size k which embeds into Hilbert space with distortion α? (Recall that a metric space (X, d_{X}) is said to embed into Hilbert space with distortion α if there exists a mapping f : X → L_{2} such that for every x, y ∈ X, we have d_{X}(x, y) ≤ ∥f (x) − f (y)∥_{2} ≤ αd_{X}(x, y)). This problem has since been investigated by several authors, motivated in part by the discovery of its applications to online algorithms — we refer to [5] for a discussion of the history and applications of the metric Ramsey problem.

The most recent work on the metric Ramsey problem is due to Bartal, Linial, Mendel and Naor [5], who obtained various nearly optimal upper and lower bounds in several contexts. Among the results in [5] is the following theorem which deals with the case of large distortion: For every ε ∈ (0, 1), any n-point metric space has a subset of size n^{1−ε} which embeds into an ultrametric with distortion O (\frac{log(2/ε)}{ε}) (recall that an ultrametric (X, d_{X}) is a metric space satisfying for every x, y, z ∈ X, d_{X}(x, y) ≤ max{d_{X}(x, z), d_{X}(y, z)} ). Since ultrametrics embed isometrically into Hilbert space, this is indeed a metric Ramsey theorem. Moreover, it was shown in [5] that this result is optimal up to the log(2/ε) factor, i.e. there exists arbitrarily large n-point metric spaces any subset of which of size n^{1−ε} incurs distortion Ω(1/ε) in any embedding into Hilbert space. The main result of this paper closes this gap:

Theorem 1.1. Let (X, d_{X}) be an n-point metric space and ε ∈ (0, 1). Then there exists a subset Y ⊆ X with |Y| ≥ n^{1−ε} such that (Y, d_{X}) is equivalent to an ultrametric with distortion at most \frac{128}{ε}.

In the four years that elapsed since our work on [5] there has been remarkable development in the structure theory of finite metric spaces. In particular, the theory of random partitions of metric spaces has been considerably refined, and was shown to have numerous applications in mathematics and computer science (see for example [17, 25, 24, 1] and the references therein). The starting point of the present paper was our attempt to revisit the metric Ramsey problem using random partitions. It turns out that this approach can indeed be used to resolve the metric Ramsey problem for large distortion, though it requires the introduction of a new kind of random partition, an improved “padding inequality” for known partitions, and a novel application of the random partition method in the setting of Ramsey problems. In Section 2 we introduce the notion of Ramsey partitions, and show how they can be used to address the metric Ramsey problem. We then proceed in Section 3 to construct optimal Ramsey partitions, yielding Theorem 1.1. Our construction is inspired in part by Bartal’s probabilistic embedding into trees [4], and is based on a random partition due to Calinescu, Karloff and Rabani [9], with an improved analysis which strengthens the work of Fakcharoenphol, Rao and Talwar [17]. In particular, our proof of Theorem 1.1 is self contained, and considerably simpler than the proof of the result from [5] quoted above. Nevertheless, the construction of [5] is deterministic, while our proof of Theorem 1.1 is probabilistic. Moreover, we do not see a simple way to use our new approach to simplify the proof of another main result of [5], namely the phase transition at distortion α = 2 (we refer to [5] for details, as this result will not be used here). The results of [5] which were used crucially in our work [27] on the metric version of Milman’s Quotient of Subspace theorem are also not covered by the present paper.

Algorithmic applications to the construction of proximity data structures. The main algorithmic application of the metric Ramsey theorem in [5] is to obtain the best known lower bounds on the competitive ratio of the randomized k-server problem. We refer to [5] and the references therein for more information on this topic, as Theorem 1.1 does not yield improved k-server lower bounds. However, Ramsey partitions are useful to obtain positive results, and not only algorithmic lower bounds, which we now describe.

A finite metric space can be thought of as given by its n × n distance matrix. However, in many algorithmic contexts it is worthwhile to preprocess this data so that we store significantly less than n^{2} numbers, and still be able to quickly find out approximately the distance between two query points. In other words, quoting Thorup and Zwick [31], “In most applications we are not really interested in all distances, we just want the ability to retrieve them quickly, if needed”. The need for such “compact” representation of metrics also occurs naturally in mathematics; for example the methods developed in theroetical computer science (specifically [11, 20]) are a key tool in the recent work of Fefferman and Klartag [18] on the extension of C^{m} functions defined on n points in ^{d} to all of ^{d}.

An influential compact representation of metrics used in theoretical computer science is the approximate distance oracle [3, 14, 31, 20]. Stated formally, a (P, S, Q, D)-approximate distance oracle on a finite metric space (X, d_{X}) is a data structure that takes expected time P to preprocess from the given distance matrix, takes space S to store, and given two query points x, y ∈ X, computes in time Q a number E(x, y) satisfying d_{X}(x, y) ≤ E(x, y) ≤ D·d_{X}(x, y). Thus the distance matrix itself is a (P = O(1), S = O(n^{2}), Q = O(1), D = 1)- approximate distance oracle, but clearly the interest is in compact data structures in the sense that S = o(n^{2}). In what follows we will depart from the above somewhat cumbersome terminology, and simply discuss D-approximate distance oracles (emphasizing the distortion D), and state in words the values of the other relevant parameters (namely the preprocessing time, storage space and query time).

An important paper of Thorup and Zwick [31] constructs the best known approximate distance oracles. Namely, they show that for every integer k, every n-point metric space has a (2k − 1)-approximate distance oracle which can be preprocessed on time O (n^{2+1/k}), requires storage O (k · n^{1+1/k}), and has query time O(k). Moreover, it is shown in [31] that this distortion/storage tradeoff is almost tight: A widely believed combinatorial conjecture of Erdős [16] is shown in [31] (see also [26]) to imply that any data structure supporting approximate distance queries with distortion at most 2k − 1 must be of size at least Ω (n^{1+1/k}) bits. Since for large values of k the query time of the Thorup-Zwick oracle is large, the problem remained whether there exist good approximate distance oracles whose query time is a constant independent of the distortion (i.e., in a sense, true “oracles”). Here we use Ramsey partitions to answer this question positively: For any distortion, every metric space admits an approximate distance oracle with preprocessing time and space almost as good as the Thorup-Zwick oracle (in fact, for distortions larger than Ω(logn/ loglogn) our storage space is slightly better), but whose query time is a universal constant. Stated formally, we prove the following theorem:

Theorem 1.2. For any k > 1, every n-point metric space (X, d_{X}) admits a O(k)-approximate distance oracle whose preprocessing time is O (n^{2+1/k} logn), requiring storage space O (n^{1+1/k}), and whose query time is a universal constant.

Another application of Ramsey partitions is to the construction of data structures for approximate ranking. This problem is motivated in part by web search and the analysis of social networks, in addition to being a natural extension of the ubiquitous approximate nearest neighbor search problem (see [2, 23, 13] and the references therein). In the approximate nearest neighbor search problem we are given c > 1, a metric space (X, d_{X}), and a subset Y ⊆ X. The goal is to preprocess the data points Y so that given a query point x ∈ X \ Y we quickly return a point y ∈ Y which is a c-approximate nearest neighbor of x, i.e. d_{X}(x, y) ≤ cd_{X}(x, Y). More generally, one might want to find the second closest point to x in Y, and so forth (this problem has been studied extensively in computational geometry, see for example [2]). In other words, by ordering the points in X in increasing distance from x ∈ X we induce a proximity ranking of the points of X. Each point of X induces a different ranking of this type, and computing it efficiently is a natural generalization of the nearest neighbor problem. Using our new Ramsey partitions we design the following data structure for solving this problem approximately:

Theorem 1.3. Fix k > 1, and an n-point metric space (X, d_{X}). Then there exist a data structure which can be preprocessed in time O (kn^{2+1/k} logn), uses only O (kn^{1+1/k})storage space, and supports the following type of queries: Given x ∈ X, have “fast access” to a permutation of π^{(x)} of X satisfying for every 1 ≤ i < j ≤ n, d_{X}(x, π^{(x)}(i)) ≤ O(k) · d_{X}(x, π^{(x)}(j)).

By “fast access” to π^{(x)} we mean that we can do the following:

1. Given a point x ∈ X, and i ∈ {1, …, n}, find π^{(x)}(i) in constant time.

2. For any x, u ∈ X, compute j ∈ {1, …, n} such that π^{(x)}(j) = u in constant time.

As is clear from the above discussion, the present paper is a combination of results in pure mathematics, as well as the theory of data structures. This exemplifies the close interplay between geometry and computer science, which has become a major driving force in modern research in these areas. Thus, this paper “caters” to two different communities, and we put effort into making it accessible to both.

2 Ramsey partitions and their equivalence to the metric Ramsey problem

Let (X, d_{X}) be a metric space. In what follows for x ∈ X and r ≥ 0 we let B_{X}(x, r) = {y ∈ X : d_{X}(x, y) ≤ r} be the closed ball of radius r centered at x. Given a partition 𝒫 of X and x ∈ X we denote by 𝒫(x) the unique element of 𝒫 containing x. For Δ > 0 we say that 𝒫 is Δ-bounded if for every C ∈ 𝒫, diam(C) ≤ Δ. A partition tree of X is a sequence of partitions {𝒫_{k}}_{k=0}^{∞} of X such that 𝒫_{0} = {X}, for all k ≥ 0 the partition 𝒫_{k} is 8^{−k} diam(X)-bounded, and 𝒫_{k+1} is a refinement of 𝒫_{k} (the choice of 8 as the base of the exponent in this definition is convenient, but does not play a crucial role here). For β, γ > 0 we shall say that a distribution Pr over partition trees {𝒫_{k}}_{k=0}^{∞} of X is completely β-padded with exponent γ if for every x ∈ X,

Pr[∀ k ∈ , B_{X}(x, β · 8^{−k} diam(X))⊆ 𝒫_{k}(x)] ≥ |X|^{−γ}.

We shall call such distributions over partition trees Ramsey partitions.

The following lemma shows that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem. In fact, it is possible to prove the converse direction, i.e. that the metric Ramsey theorem implies the existence of good Ramsey partitions (with appropriate dependence on the various parameters). We defer the proof of this implication to Appendix B as it will not be used in this paper due to the fact that in Section 3 we will construct directly optimal Ramsey partitions.

Lemma 2.1. Let (X, d_{X}) be an n-point metric space which admits a distribution over partition trees which is completely β-padded with exponent γ. Then there exists a subset Y ⊆ X with |Y| ≥ n^{1−γ} which is 8/β equivalent to an ultrametric.

Proof. We may assume without loss of generality that diam(X) = 1. Let {𝒫_{k}}_{k=0}^{∞} be a distribution over partition trees of X which is completely β-padded with exponent γ. We define an ultrametric ρ on X as follows. For x, y ∈ X let k be the largest integer for which 𝒫_{k}(x) = 𝒫_{k}(y), and set ρ(x, y) = 8^{−k}. It is straightforward to check that ρ is indeed an ultrametric. Consider the random subset Y ⊆ X given by

Y = {x ∈ X : ∀ k ∈ , B_{X}(x, β · 8^{−k})⊆ 𝒫_{k}(x)} .

Then

|Y| = ∑_{x∈X}Pr[∀ k ∈ , B_{X}(x, β · 8^{−k} diam(X))⊆ 𝒫_{k}(x)] ≥ n^{1−γ}.

We can therefore choose Y ⊆ X with |Y| ≥ n^{1−γ} such that for all x ∈ Y and all k ≥ 0 we have B_{X}(x, β · 8^{−k})⊆ 𝒫_{k}(x). Fix x, y ∈ X, and let k be the largest integer for which 𝒫_{k}(x) = 𝒫_{k}(y). Then d_{X}(x, y) ≤ diam(𝒫_{k}(x)) ≤ 8^{−k} = ρ(x, y). On the other hand, if x ∈ X and y ∈ Y then, since 𝒫_{k+1}(x) 𝒫_{k+1}(y), the choice of Y implies that x B_{X}(y, β · 8^{−k−1}). Thus d_{X}(x, y) > β · 8^{−k−1} = \frac{β}{8}ρ(x, y). It follows that the metrics d_{X} and ρ are equivalent on Y with distortion 8/β.

3 Constructing optimal Ramsey partitions

The following lemma gives improved bounds on the “padding probability” of a distribution over partitions which was discovered by Calinescu, Karloff and Rabani in [9].

Lemma 3.1. Let (X, d_{X}) be a finite metric space. Then for every Δ > 0 there exits a distribution Pr over Δ-bounded partitions of X such that for every 0 < t ≤ Δ/8 and every x ∈ X,

Pr[B_{X}(x, t)⊆ 𝒫(x)] ≥ (\frac{|B_{X}(x, Δ/8)|}{|B_{X}(x, Δ)|})^{\frac{16t}{Δ}} .  (1)

Remark 3.1. The distribution over partitions used in the proof of Lemma 3.1 is precisely the distribution introduced by Calinescu, Karloff and Rabani in [9]. In [17] Fakcharoenphol, Rao and Talwar proved the following estimate for the same distribution

Pr[B_{X}(x, t)⊆ 𝒫(x)] ≥ 1 − O (\frac{t}{Δ} log \frac{|B_{X}(x, Δ)|}{|B_{X}(x, Δ/8)|}).  (2)

Clearly the bound (1) is stronger than the bound (2), and this improvement is crucial for our proof of Theorem 1.1. The use of the “local ratio of balls” (or “local growth”) in the estimate (2) of Fakcharoenphol, Rao and Talwar was a fundamental breakthrough, which, apart from their striking application in [17], has since found several applications in mathematics and computer science (see [25, 24, 1]).

Proof of Lemma 3.1. Write X = {x_{1}, …, x_{n}}. Let R be chosen uniformly at random from the interval [Δ/4, Δ/2], and let π be a permutation of {1, …, n} chosen uniformly at random from all such permutations (here, and in what follows, R and π are independent). Define C_{1} B_{X}(x_{π(1)}, R)and inductively for 2 ≤ j ≤ n,

C_{j} B_{X}(x_{π(j)}, R)\ ⋃_{i=1}^{j−1} C_{i}.

Finally we let 𝒫 {C_{1}, …, C_{n}} \ {∅}. Clearly 𝒫 is a (random) Δ-bounded partition on X.

For every r ∈ [Δ/4, Δ/2],

Pr[B_{X}(x, t)⊆ 𝒫(x)|R = r] ≥ \frac{|B_{X}(x, r − t)|}{|B_{X}(x, r + t)|}.  (3)

Indeed, if R = r, then the triangle inequality implies that if in the random order induced by the partition π on the points of the ball B_{X}(x, r + t) the minimal element is from the ball B_{X}(x, r − t), then B_{X}(x, t)⊆ 𝒫(x) (draw a picture). This event happens with probability \frac{|B_{X}(x,r−t)|}{|B_{X}(x,r+t)|}, implying (3).

Write \frac{Δ}{8t} = k + β, where β ∈ [0, 1) and k is a positive integer. Then

Pr[B_{X}(x, t)⊆ 𝒫(x)] ≥ \frac{4}{Δ} ∫ _{Δ/4}^{Δ/2} \frac{|B_{X}(x, r − t)|}{|B_{X}(x, r + t)|}dr  (4)

= \frac{4}{Δ} ∑_{j=0}^{k−1} ∫ _{\frac{Δ}{4} +2jt}^{\frac{Δ}{4} +2(j+1)t} \frac{|B_{X}(x, r − t)|}{|B_{X}(x, r + t)|}dr + \frac{4}{Δ} ∫ \frac{Δ}{4} +2kt^{\frac{Δ}{2}} \frac{|B_{X}(x, r − t)|}{|B_{X}(x, r + t)|}dr

≥ \frac{4}{Δ} ∫ _{0}^{2t} ∑_{j=0}^{k−1} \frac{|B_{X}(x, \frac{Δ}{4} + 2jt + s − t) |}{|B_{X}(x, \frac{Δ}{4} + 2jt + s + t) |}ds + \frac{4}{Δ} (\frac{Δ}{4} − 2kt) \frac{|B_{X}(x, \frac{Δ}{4} + 2kt − t)|}{|B_{X}(x, \frac{Δ}{2} + t)|}

≥ \frac{4k}{Δ} ∫ _{0}^{2t} [∏_{j=0}^{k−1} \frac{|B_{X}(x, \frac{Δ}{4} + 2jt + s − t) |}{|B_{X}(x, \frac{Δ}{4} + 2jt + s + t) |}]^{\frac{1}{k}} ds + (1 − \frac{8kt}{Δ}) \frac{|B_{X}(x, \frac{Δ}{4} + 2kt − t)|}{|B_{X}(x, \frac{Δ}{2} + t)|} (5)

= \frac{4k}{Δ} · ∫ _{0}^{2t} [\frac{|B_{X}(x, \frac{Δ}{4} + s − t)|}{|B_{X}(x, \frac{Δ}{4} + 2t (k − 1) + s + t) |}]^{\frac{1}{k}} ds + (1 − \frac{8kt}{Δ}) \frac{|B_{X}(x, \frac{Δ}{4} + 2kt − t)|}{|B_{X}(x, \frac{Δ}{2} + t)|}

≥ \frac{8kt}{Δ}[\frac{|B_{X}(x, \frac{Δ}{4} − t)|}{|B_{X}(x, \frac{Δ}{4} + 2kt + t)|}]^{\frac{1}{k}} + (1 − \frac{8kt}{Δ}) \frac{|B_{X}(x, \frac{Δ}{4} + 2kt − t)|}{|B_{X}(x, \frac{Δ}{2} + t)|}

≥ [\frac{|B_{X}(x, \frac{Δ}{4} − t)|}{|B_{X}(x, \frac{Δ}{4} + 2kt + t)|}]^{\frac{8t}{Δ}} · [\frac{|B_{X}(x, \frac{Δ}{4} + 2kt − t)|}{|B_{X}(x, \frac{Δ}{2} + t)|}]^{1− \frac{8kt}{Δ}}  (6)

= [\frac{|B_{X}(x, \frac{Δ}{4} − t)|}{|B_{X}(x, \frac{Δ}{4} + 2kt + t)|} · \frac{|B_{X}(x, \frac{Δ}{4} + 2kt − t)|}{|B_{X}(x, \frac{Δ}{2} + t)|}]^{\frac{8t}{Δ}} · [\frac{|B_{X}(x, \frac{Δ}{4} + 2kt − t)|}{|B_{X}(x, \frac{Δ}{2} + t)|}]^{^{\frac{8t}{Δ}}(\frac{Δ}{8t}−k−1)}

≥ [\frac{|B_{X}(x, \frac{Δ}{4} − t)|}{|B_{X}(x, \frac{Δ}{2} + t)|}]^{\frac{16t}{Δ}} ,  (7)

where in (4) we used (3), in (5) we used the arithmetic mean/geometric mean inequality, in (6) we used the elementary inequality θa + (1 − θ)b ≥ a^{θ}b^{1−θ}, which holds for all θ ∈ [0, 1] and a, b ≥ 0, and in (7) we used the fact that \frac{Δ}{8t} − k − 1 is negative.

The following theorem, in conjunction with Lemma 2.1, implies Theorem 1.1.

Theorem 3.2. For every α > 1, every finite metric space (X, d_{X}) admits a completely 1/α padded random partition tree with exponent 16/α.

Proof. Fix α > 1. Without loss of generality we may assume that diam(X) = 1. We construct a partition tree {ℰ_{k}}_{k=0}^{∞} of X as follows. Set ℰ_{0} = {X}. Having defined ℰ_{k} we let 𝒫_{k+1} be a partition as in Lemma 3.1 with Δ = 8^{−k} and t = Δ/α (the random partition 𝒫_{k+1} is chosen independently of the random partitions 𝒫_{1}, …, 𝒫_{k}). Define ℰ_{k+1} to be the common refinement of ℰ_{k} and 𝒫_{k+1}, i.e.

ℰ_{k+1} {C ∩ C′: C ∈ ℰ_{k}, C′ ∈ 𝒫_{k+1}}.

The construction implies that for every x ∈ X and every k ≥ 0 we have ℰ_{k+1}(x) = ℰ_{k}(x) ∩ 𝒫_{k+1}(x). Thus one proves inductively that

∀ k ∈ , B_{X}(x, \frac{8^{−k}}{α} ) ⊆ 𝒫_{k}(x) ⟹ ∀ k ∈ , B_{X}(x, \frac{8^{−k}}{α} ) ⊆ ℰ_{k}(x).

From Lemma 3.1 and the independence of {𝒫_{k}}_{k=1}^{∞} it follows that

Pr[∀ k ∈ , B_{X}(x, \frac{8^{−k}}{α} ) ⊆ ℰ_{k}(x)] ≥ Pr[∀ k ∈ , B_{X}(x, \frac{8^{−k}}{α} ) ⊆ 𝒫_{k}(x)]
= ∏_{k=1}^{∞} Pr[B_{X}(x, \frac{8^{−k}}{α} ) ⊆ 𝒫_{k}(x)]

≥ ∏_{k=1}^{∞} [\frac{|B_{X}(x, 8^{−k−1})|}{|B_{X}(x, 8^{−k})}]^{\frac{16}{α}}
= |B_{X}(x, 1/8)|^{− \frac{16}{α}} ≥ |X|^{− \frac{16}{α}} .

4 Applications to proximity data structures

In this section we show how Theorem 3.2 can be applied to the design of various proximity data structures, which are listed below. Before doing so we shall recall some standard facts about tree representations of ultrametrics, all of which can be found in the discussion in [5]. Any finite ultrametric (X, ρ) can be represented by a tree T = (V, E) with labels Δ : V → (0, ∞), whose leaves are X, and such that if u, v ∈ V and v is a child of u then Δ(v) ≤ Δ(u). Given x, y ∈ X we then have ρ(x, y) = Δ (lca(x, y)), where lca(x, y) is the least common ancestor of x and y in T. For k ≥ 1 the labelled tree described above is called a k-HST (hierarchically well separated tree) if its labels satisfy the stronger decay condition Δ(v) ≤ \frac{Δ(u)}{k} whenever v is a child of u. The tree T is called an exact k-HST if we actually have an equality Δ(v) = \frac{Δ(u)}{k} whenever v is a child of u. Lemma 3.5 in [5] implies any 1-HST with n-leaves is k-equivalent to a k-HST which can be computed in time O(n).

We start by proving several structural lemmas which will play a crucial role in the design of our new data structures.

Lemma 4.1 (Extending ultrametrics). Let (X, d_{X}) be a finite metric space, and α ≥ 1. Fix ∅ Y ⊆ X, and assume that there exits an ultrametric ρ on Y such that for every x, y ∈ Y, d_{X}(x, y) ≤ ρ(x, y) ≤ αd_{X}(x, y). Then there exists an ultrametric ρ̃ defined on all of X such that for every x, y ∈ X we have d_{X}(x, y) ≤ ρ̃(x, y), and if x ∈ X and y ∈ Y then ρ̃(x, y) ≤ 6αd_{X}(x, y).

Proof. Let T = (V, E) be the 1-HST representation of ρ, with labels Δ : V → (0, ∞). In other words, the leaves of T are Y, and for every x, y ∈ Y we have Δ(lca(x, y)) = ρ(x, y). It will be convenient to augment T by adding an incoming edge to the root with Δ(parent(root)) = ∞. This clearly does not change the induced metric on Y. For every x ∈ X \ Y let y ∈ Y be its closest point in Y, i.e. d_{X}(x, y) = d_{X}(x, Y). Let u be the least ancestor of y for which Δ(u) ≥ d_{X}(x, y) (such a u must exist because we added the incoming edge to the root). Let v be the child of u along the path connecting u and y. We add a vertex w on the edge {u, v} whose label is d_{X}(x, y), and connect x to T as a child of w. The resulting tree is clearly still a 1-HST. Repeating this procedure for every x ∈ X \ Y we obtain a 1-HST T̃ whose leaves are X. Denote the labels on T̃ by Δ̃.

Fix x, y ∈ X, and let x′, y′ ∈ Y the nearest neighbors of x, y (respectively) used in the above construction. Then

Δ̃ (lcaT̃(x, y)) = max{Δ̃ (lcaT̃(x, x′)), Δ̃ (lcaT̃(y, y′)), Δ̃ (lcaT̃(x′, y′))}
≥ max{d_{X}(x, x′), d_{X}(y, y′), d_{X}(x′, y′)}
≥ \frac{d_{X}(x, x′) + d_{X}(y, y′) + d_{X}(x′, y′)}{3}
≥ \frac{1}{3}d_{X}(x, y).  (8)

In the reverse direction, if x ∈ X and y ∈ Y let x′ ∈ Y be the closest point in Y to x used in the construction of T̃. Then d_{X}(x′, y) ≤ d_{X}(x′, x) + d_{X}(x, y) ≤ 2d_{X}(x, y). If lcaT̃(y, x′) is an ancestor of lcaT̃(x, x′) then

Δ̃ (lcaT̃(x, y))= Δ̃ (lcaT̃(x′, y))= ρ(x′, y) ≤ α · d_{X}(x′, y) ≤ 2α · d_{X}(x, y).  (9)

If, on the other hand, lcaT̃(y, x′) is a descendant of lcaT̃(x, x′) then

Δ̃ (lcaT̃(x, y))= Δ̃ (lcaT̃(x, x′))= d_{X}(x, x′) ≤ d_{X}(x, y).  (10)

Scaling the labels of T̃ by a factor of 3, the required result is a combination of (8), (9) and (10).

The following lemma is a structural result on the existence of a certain distribution over decreasing chains of subsets of a finite metric space. In what follows we shall call such a distribution a stochastic Ramsey chain.

Lemma 4.2 (Stochastic Ramsey chains). Let (X, d_{X}) be an n-point metric space and k ≥ 1. Then there exists a distribution over decreasing sequences of subsets X = X_{0} X_{1} X_{2} ⋯ X_{s} = ∅ (s itself is a random variable), such that for all p > −1/k,

[∑_{j=0}^{s−1} |X_{j}|^{p}]≤ (max\{ \frac{k}{1 + pk}, 1\}) · n^{p+1/k},  (11)

and such that for each j ∈ {1, …, s} there exists an ultrametric ρ_{j} on X satisfying for every x, y ∈ X, ρ_{j}(x, y) ≥ d_{X}(x, y), and if x ∈ X and y ∈ X_{j−1} \ X_{j} then ρ_{j}(x, y) ≤ O(k) · d_{X}(x, y).

Remark 4.1. In what follows we will only use the cases p ∈ {0, 1, 2} in Lemma 4.2. Observe that for p = 0,

(11) is simply the estimate s ≤ kn^{1/k}.

Proof of Lemma 4.2. By the Theorem 3.2 and the proof of Lemma 2.1 there is a distribution over subsets Y_{1} ⊆ X_{0} such that |Y_{1}| ≥ n^{1−1/k} and there exists an ultrametric ρ_{1} on Y_{1} such that every x, y ∈ Y_{1} satisfy d_{X}(x, y) ≤ ρ_{1}(x, y) ≤ O(k) · d_{X}(x, y). By Lemma 4.1 we may assume that ρ_{1} is defined on all of X, for every x, y ∈ X we have ρ_{1}(x, y) ≥ d_{X}(x, y), and if x ∈ X and y ∈ Y_{1} then ρ_{1}(x, y) ≤ O(k)·d_{X}(x, y). Define X_{1} = X_{0}\Y_{1} and apply the same reasoning to X_{1}, obtaining a random subset Y_{2} ⊆ X_{0}\Y_{1} and an ultrametric ρ_{2}. Continuing in this manner until we arrive at the empty set, we see that there are disjoint subsets, Y_{1}, …, Y_{s} ⊆ X, and for each j an ultrametric ρ_{j} on X, such that for x, y ∈ X we have ρ_{j}(x, y) ≥ d_{X}(x, y), and for x ∈ X, y ∈ Y_{j} we have ρ_{j}(x, y) ≤ O(k) · d_{X}(x, y). Additionally, writing X_{j} X \ ⋃ _{i=1}^{j} Y_{i}, we have the estimate

[|Y_{j}||Y_{1}, …, Y_{j−1} ] ≥ |X_{j−1} |^{1−1/k}.

The proof of (11) is by induction on n. For n = 1 the claim is obvious, and if n > 1 then by the inductive hypothesis

[∑_{j=0}^{s−1} |X_{j}|^{p}|Y_{1}] ≤ n^{p} + (max\{ \frac{k}{1 + pk}, 1\}) · |X_{1}|^{p+1/k}

= n^{p} + (max\{ \frac{k}{1 + pk}, 1\}) · n^{p+1/k} (1 − \frac{|Y_{1}|}{n})^{p+1/k}
≤ n^{p} + (max\{ \frac{k}{1 + pk}, 1\}) · n^{p+1/k} (1 − (min\{p + \frac{1}{k}, 1\}) · \frac{|Y_{1}|}{n})
= (max\{ \frac{k}{1 + pk}, 1\}) · n^{p+1/k} + n^{p} − n^{p−1+1/k}|Y_{1}|.

Taking expectation with respect to Y_{1} gives the required result.

Remark 4.2. If one does not mind losing a factor of O(logn) in the construction time and storage of the Ramsey chain, then an alternative to Lemma 4.2 is to randomly and independently sample O (n^{1/k}logn) ultrametrics from the Ramsey partitions.

Before passing to the description of our new data structures, we need to say a few words about the algorithmic implementation of Lemma 4.2 (this will be the central preprocessing step in our constructions). We should point out here that the computational model in which we will be working is the RAM model, which is standard in the context of our type of data-structure problems (see for example [31]). In fact, we can settle for weaker computational models such as the “Unit cost floating-point word RAM model” — a detailed discussion of these issues can be found in Section 2.2. of [20].

The natural implementation of the Calinescu-Karloff-Rabani (CKR) random partition used in the proof of Lemma 3.1 takes O (n^{2})time. Denote by Φ = Φ(X) the aspect ratio of X, i.e. the diameter of X divided by the minimal positive distance in X. The construction of the distribution over partition trees in the proof of Theorem 3.2 requires performing O(logΦ) such decompositions. This results in O (n^{2} logΦ) preprocessing time to sample one partition tree from the distribution. Using a standard technique (described for example in [20, Sections 3.2-3.3]), we dispense with the dependence on the aspect ratio and obtain that the expected preprocessing time of one partition tree is O (n^{2} logn). Since the argument in [20] is presented in a slightly different context, we shall briefly sketch it here.

We start by constructing an ultrametric ρ on X, represented by an HST H, such that for every x, y ∈ X, d_{X}(x, y) ≤ ρ(x, y) ≤ nd_{X}(x, y). The fact that such a tree exists is contained in [5, Lemma 3.6], and it can be constructed in time O (n^{2})using the Minimum Spanning Tree algorithm. This implementation is done in [20, Section 3.2]. We then apply the CKR random partition with diameter Δ as follows: Instead of applying it to the points in X, we apply it to the vertices u of H for which

Δ(u) ≤ \frac{Δ}{n^{2}} < Δ (parent(u)).  (12)

Each such vertex u represents all the subtree rooted at u (in particular, we can choose arbitrary leaf descendants to calculate distances — these distances are calculated using the metric d_{X}), and they are all assigned to the same cluster as u in the resulting partition. This is essentially an application of the algorithm to an appropriate quotient of X (see the discussion in [27]). We actually apply a weighted version of the CKR decomposition in the spirit of [25], in which, in the choice of random permutation, each vertex u as above is chosen with probability proportional to the number of leaves which are descendants of u (note that this change alters the guarantee of the partition only slightly: We will obtain clusters bounded by (1 + 1/n^{2})Δ, and in the estimate on the padding probability the radii of the balls is changed by only a factor of (1 ± 1/n)). We also do not process each scale, but rather work in “event driven mode”: Vertices of H are put in a non decreasing order according to their labels in a queue. Each time we pop a new vertex u, and partition the spaces at all the scales in the range [Δ(u), n^{2}Δ(u)], for which we have not done so already. In doing so we effectively skip “irrelevant” scales. To estimate the running time of this procedure note that the CKR decomposition at scale 8^{j} takes time O (m_{i}^{2}), where m_{i} is the number of vertices u of H satisfying (12) with Δ = 8^{i}. Note also that each vertex of H participates in at most O(logn) such CKR decompositions, so ∑ _{i} m_{i} = O(n logn). Hence the running time of the sampling procedure in Lemma 4.2 is up to a constant factor ∑ _{i} m_{i}^{2} = O (n^{2} logn).

The Ramsey chain in Lemma 4.2 will be used in two different ways in the ensuing constructions. For our approximate distance oracle data structure we will just need that the ultrametric ρ_{j} is defined on X_{j−1} (and not all of X). Thus, by the above argument, and Lemma 4.2, the expected preprocessing time in this case is O ( ∑ _{j=1}^{s−1} |X_{j}|^{2} logΦ(X_{j})) = O (n^{2+1/k} logn) and the expected storage space is O ( ∑ _{j=1}^{s−1} |X_{j}|)= O (n^{1+1/k}). For the purpose of our approximate ranking data structure we will really need the metrics ρ_{j} to be defined on all of X. Thus in this case the expected preprocessing time will be O (n^{2} logn · s)= O (kn^{2+1/k} logn), and the expected storage space is O (n · s)= O (kn^{1+1/k}).

1) Approximate distance oracles. Our improved approximate distance oracle is contained in Theorem 1.2, which we now prove.

Proof of Theorem 1.2. We shall use the notation in the statement of Lemma 4.2. Let T_{j} = (V_{j}, E_{j}) and Δ_{j} : V_{j} → (0, ∞) be the HST representation of the ultrametric ρ_{j} (which was actually constructed explicitly in the proofs of Lemma 2.1 and Lemma 4.2). The usefulness of the tree representation stems from the fact that it very easy to handle algorithmically. In particular there exists a simple scheme that takes a tree and preprocesses it in linear time so that it is possible to compute the least common ancestor of two given nodes in constant time (see [21, 6]). Hence, we can preprocess any 1-HST so that the distance between any two points can be computed in O(1) time.

For every point x ∈ X let i_{x} be the largest index for which x ∈ X_{i_{x}−1}. Thus, in particular, x ∈ Y_{i_{x}}. We further maintain for every x ∈ X a vector (in the sense of data-structures) vec_{x} of length i_{x} (with O(1) time direct access), such that for i ∈ {0, …, i_{x}− 1}, vec_{x}[i] is a pointer to the leaf representing x in T_{i}. Now, given a query x, y ∈ X assume without loss of generality that i_{x} ≤ i_{y}. It follows that x, y ∈ X_{i_{x}−1}. We locate the leaves x̂ = vec_{x}[i_{x}], and ŷ = vec_{y}[i_{x}] in T_{i_{x}}, and then compute lca (x̂, ŷ) to obtain an O(k) approximation to d_{X}(x, y). Observe that the above data structure only requires ρ_{j} to be defined on X_{j−1} (and satisfying the conclusion of Lemma 4.2 for x, y ∈ X_{j−1} ). The expected preprocessing time is O (n^{2+1/k} logn). The size of the above data structure is O (∑ _{j=0}^{s} |X_{j}|), which is in expectation O (n^{1+1/k}).

Remark 4.3. Using the distributed labeling for the least common ancestor operation on trees of Peleg [29], the procedure described in the proof of Theorem 1.2 can be easily converted to a distance labeling data structure (we refer to [31, Section 3.5] for a description of this problem). We shall not pursue this direction here, since while the resulting data structure is non-trivial, it does not seem to improve over the known distance labeling schema [31].

2) Approximate ranking. Before passing to our α-approximate ranking data structure (Theorem 1.3) we recall the setting of the problem. Thinking of X as a metric on {1, …, n}, and fixing α > 1, the goal here is to associate with every x ∈ X a permutation π^{(x)} of {1, …, n} such that d_{X}(x, π^{(x)}(i)) ≤ α · d_{X}(x, π^{(x)}(j)) for every 1 ≤ i ≤ j ≤ n. This relaxation of the exact proximity ranking induced by the metric d_{X} allows us to gain storage efficiency, while enabling fast access to this data. By fast access we mean that we can preform the following tasks:

1. Given an element x ∈ X, and i ∈ {1, …, n}, find π^{(x)}(i) in O(1) time.

2. Given an element x ∈ X and y ∈ X, find number i ∈ {1, …, n}, such that π^{(x)}(i) = y, in O(1) time.

Before passing to the proof of Theorem 1.3 we require the following lemma.

Lemma 4.3. Let T = (V, E) be a rooted tree with n leaves. For v ∈ V, let ℒ_{T}(v) be the set of leaves in the subtree rooted at v, and denote ℓ_{T}(v) = |ℒ_{T}(v)|. Then there exists a data structure, that we call Size-Ancestor, which can be preprocessed in time O(n), and answers in time O(1) the following query: Given ℓ ∈ and a leaf x ∈ V, find an ancestor u of x such that ℓ_{T}(u) < ℓ ≤ ℓ(parent(u)). Here we use the convention ℓ(parent(root)) = ∞.

To the best of our knowledge, the data structure described in Lemma 4.3 has not been previously studied. We therefore include a proof of Lemma 4.3 in Appendix A, and proceed at this point to conclude the proof of Theorem 1.3.

Proof of Theorem 1.3. We shall use the notation in the statement of Lemma 4.2. Let T_{j} = (V_{j}, E_{j}) and Δ_{j} : V → (0, ∞) be the HST representation of the ultrametric ρ_{j}. We may assume without loss of generality that each of these trees is binary and does not contain a vertex which has only one child. Before presenting the actual implementation of the data structure, let us explicitly describe the permutation π^{(x)} that the data structure will use. For every internal vertex v ∈ V_{j} assign arbitrarily the value 0 to one of its children, and the value 1 to the other. This induces a unique (lexicographical) order on the leaves of T_{j}. Next, fix x ∈ X and i_{x} such that x ∈ Y_{i_{x}}. The permutation π^{(x)} is defined as follows. Starting from the leaf x in T_{i_{x}}, we scan the path from x to the root of T_{i_{x}}. On the way, when we reach a vertex u from its child v, let w denote the sibling of v, i.e. the other child of u. We next output all the leafs which are descendants of w according to the total order described above. Continuing in this manner until we reach the root of T_{i_{x}} we obtain a permutation π^{(x)} of X.

We claim that the permutation π^{(x)} constructed above is an O(k)-approximation to the proximity ranking induced by x. Indeed, fix y, z ∈ X such that Ck · d_{X}(x, y) < d_{X}(x, z), where C is a large enough absolute constant. We claim that z will appear after y in the order induced by π^{(x)}. This is true since the distances from x are preserved up to a factor of O(k) in the ultrametric T_{i_{x}}. Thus for large enough C we are guaranteed that d_{T_{ix}}(x, y) < d_{T_{ix}}(x, z), and therefore lca_{T_{ix}}(x, z) is a proper ancestor of lca_{T_{ix}}(x, y). Hence in the order just describe above, y will be scanned before z.

We now turn to the description of the actual data structure, which is an enhancement of the data structure constructed in the proof of Theorem 1.2. As in the proof of Theorem 1.2 our data structure will consist of a “vector of the trees T_{j}”, where we maintain for each x ∈ X a pointer to the leaf representing x in each T_{j}. The remaining description of our data structure will deal with each tree T_{j} separately. First of all, with each vertex v ∈ T_{j} we also store the number of leaves which are the descendants of v, i.e. |ℒ_{T_{j}}(v)| (note that all these numbers can be computed in time O(n) time using, say, depth-first search). With each leaf of T_{j} we also store its index in the order described above, and there is a reverse indexing by a vector that allows, given an index, to find the corresponding vertex in O(1) time. Each internal vertex contains a pointer to its leftmost (smallest) and rightmost (largest) descendant leaves. This data structure can be clearly constructed in O(n) time using, e.g., depth-first transversal of the tree. We now give details on how to answer the required queries using the “ammunition” we have listed above.

1. Using Lemma 4.3, find an ancestor v of x such that ℓ_{T_{j}}(v) < i ≤ ℓ_{T_{j}}(parent(v)) in O(1) time. Let u = parent(v) (note that v can not be the root). Let w be the sibling of v (i.e. the other child of u). Next we pick the leaf numbered (i − ℓ_{T_{j}}(v))+ left(w) − 1, where left(w) is the index to the leftmost descendant of w.

2. Find u = lca(x, y) (in O(1) time, using [21, 6]). Let v and w be the children of u, which are ancestors of x and y, respectively. Return ℓ_{T_{j}}(v) + ind(y) − left(w), where ind(y) is the index of y in the total order of the leaves of the tree.

This concludes the construction of our approximate ranking data structure. Because we need to have the ultrametric ρ_{j} defined on all of X, the preprocessing time is O (kn^{2+1/k} logn)and the storage size is O (kn^{1+1/k}), as required.

Remark 4.4. Our approximate ranking data structure can also be used in a nearest neighbor heuristic called “Orchard Algorithm” [28] (see also [13, Sec. 3.2]). In this algorithm the vanilla heuristic can be used to obtain the exact proximity ranking, and requires storage Ω (n^{2}). Using approximate ranking the storage requirement can be significantly improved, though the query performance is somewhat weaker due to the inaccuracy of the ranking lists.

3) Computing the Lipschitz constant. Here we describe a data structure for computing the Lipschitz constant of a function f : X → Y, where (Y, d_{Y}) is an arbitrary metric space. When (X, d_{X}) is a doubling metric space (see [22]), this problem was studied in [20]. In what follows we shall always assume that f is given in oracle form, i.e. it is encoded in such a way that we can compute its value on a given point in constant time.

Lemma 4.4. There is an algorithm that, given an n-point ultrametric (U, d_{U}) defined by the HST T = (V, E) (in particular U is the set of leaves of T), an arbitrary metric space (Y, d_{Y}), and a mapping f : U → Y, returns in time O(n) a number A ≥ 0 satisfying ∥f ∥_{Lip} ≥ A ≥ \frac{1}{16} · ∥f ∥_{Lip}.

Proof. We assume that T is 4-HST. As remarked in the beginning of Section 4, this can be achieved by distorting the distances in U by a factor of at most 4, in O(n) time. We also assume that the tree T stores for every vertex v ∈ V an arbitrary leaf x_{v} ∈ U which is a descendant of v (this can be easily computed in O(n) time). For a vertex u ∈ V we denote by Δ(u) its label (i.e. ∀ x, y ∈ U, d_{U}(x, y) = Δ(lca(x, y))).

The algorithm is as follows:

\underline{Lip-UM(T, f)}

A ← 0

For every vertex u ∈ T do Let v_{1}, …v_{r} be the children of u.

A ← max\{A, max_{2≤i≤r} ^{\frac{d_{Y}(f (x_{v_{1}}),f (x_{v_{i}}))}{Δ(u)}}\}

Output A

Clearly the algorithm runs in linear time (the total number of vertices in the tree is O(n) and each vertex is visited at most twice). Furthermore, by construction the algorithm outputs A ≤ ∥f ∥_{Lip}. It remains prove a lower bound on A. Let x_{1}, x_{2} ∈ U be such that ∥f ∥_{Lip} = \frac{d_{Y}(f (x_{1}),f (x_{2}))}{d_{U}(x_{1},x_{2})}, and denote u = lca(x, y). Let w_{1}, w_{2} be the children of u such that x_{1} ∈ ℒ_{T}(w_{1}), and x_{2} ∈ ℒ_{T}(w_{2}). Let v_{1} be the “first child” of u as ordered by the algorithm Lip-UM (notice that this vertex has special role). Then

A ≥ max\{ \frac{d_{Y}(f (x_{w_{1}}), f (x_{v_{1}}))}{Δ(u)} , \frac{d_{Y}(f (x_{w_{2}}), f (x_{v_{1}}))}{Δ(u)} \}
≥ \frac{1}{2} · \frac{d_{Y}(f (x_{w_{1}}), f (x_{w_{2}}))}{Δ(u)}
≥ \frac{1}{2} · \frac{d_{Y}(f (x_{1}), f (x_{2})) − diam(f (ℒ_{T}(w_{1}))) − diam(f (ℒ_{T}(w_{2})))}{Δ(u)} .

If max\{diam(f (ℒ_{T}(w_{1}))), diam(f (ℒ_{T}(w_{1})))\} ≤ \frac{1}{4}d_{Y}(f (x_{1}), f (x_{2})), then we conclude that

A ≥ \frac{1}{4} · \frac{d_{Y}(f (x_{1}), f (x_{2}))}{Δ(u)} ,

as needed. Otherwise, assuming that diam(f (ℒ_{T}(w_{1}))) > \frac{1}{4} · d_{Y}(f (x_{1}), f (x_{2})), there exist z, z′ ∈ ℒ_{T}(w_{1}) such that

\frac{d_{Y}(f (z), f (z′))}{d_{U}(z, z′)} > \frac{\frac{1}{4} · d_{Y}(f (x_{1}), f (x_{2}))}{Δ(u)/4} = ∥f ∥_{Lip},

which is a contradiction.

Theorem 4.5. Given k ≥ 1, any n-point metric space (X, d_{X}) can be preprocessed in time O (n^{2+1/k} logn), yielding a data structure requiring storage O (n^{1+1/k}) which can answer in O (n^{1+1/k}) time the following query: Given a metric space (Y, d_{Y}) and a mapping f : X → Y, compute a value A ≥ 0, such that ∥f ∥_{Lip} ≥ A ≥ ∥f ∥_{Lip}/O(k).

Proof. The preprocessing is simply computing the trees {T_{j}}_{j=1}^{s} as in the proof of Theorem 1.2. Denotes the resulting ultrametrics by (U_{1}, ρ_{1}), …, (U_{s}, ρ_{s}). Given f : X → Y, represent it as g_{i} : U_{i} → Y (as a mapping g_{i} is the same mapping as f). Use Lemma 4.4 to compute an estimate A_{i} of ∥g_{i}∥_{Lip}, and return A max_{i} A_{i}. Since all the distances in U_{i} dominate the distances in X, ∥f ∥_{Lip} ≥ ∥g_{i}∥_{Lip} ≥ A_{i}, so ∥f ∥_{Lip} ≥ A. On the other hand, let x, y ∈ X be such that ∥f ∥_{Lip} = \frac{d_{Y}(f (x),f (y))}{d_{X}(x,y)}. By Lemma 4.2, there exists i ∈ \{1, …, s\} such that d_{U_{i}}(x, y) ≤ O(k) · d_{X}(x, y), and hence ∥g_{i}∥_{Lip} ≥ ∥f ∥_{Lip}/O(k), And so A ≥ \frac{1}{16} · ∥g_{i}∥_{Lip} ≥ ∥f ∥_{Lip}/O(k), as required. Since we once more only need that the ultrametric ρ_{j} is defined on X_{j−1} and not on all of X, the preprocessing time and storage space are the same as in Theorem 1.2. By Lemma 4.2 the running time is O (∑ _{j=1}^{s−1} |X_{j}|)= O (n^{1+1/k})(we have a O(|X_{j}|) time computation of the Lipschitz constant on each X_{j}).

5 Concluding Remarks

An s-well separated pair decomposition (WSPD) of an n-point metric space (X, d_{X}) is a collection of pair of subsets {(A_{i}, B_{i})}_{i=1}^{M}, A_{i}, B_{i} ⊂ X, such that

1. ∀x, y ∈ X if x y then (x, y) ∈ ⋃ _{i=1}^{M}(A_{i} × B_{i}).

2. For all i j, (A_{i} × B_{i}) ∩ (A_{j} × B_{j}) = ∅.

3. For all i ∈ {1, …, M}, d_{X}(A_{i}, B_{i}) ≥ s · max{diam(A_{i}), diam(B_{i})}.

The notion of s-WSPD was first defined for Euclidean spaces in an influential paper of Callahan and Kosaraju [11], where it was shown that for n-point subsets of a fixed dimensional Euclidean space there exists such a collection of size O(n) that can be constructed in O(n logn) time. Subsequently, this concept has been used in many geometric algorithms (e.g. [32, 10]), and is today considered to be a basic tool in computational geometry. Recently the definition and the efficient construction of WSPD were generalized to the more abstract setting of doubling metrics [30, 20]. These papers have further demonstrated the usefulness of this tool (see also [18] for a mathematical application).

It would be clearly desirable to have a notion similar to WSPD in general metrics. However, as formulated above, this is impossible to do in “high dimensional” spaces, since any 2-WSPD of an n-point equilateral space must be of size Ω(n^{2}). The present paper suggests that Ramsey partitions might be a partial replacement of this notion which works for arbitrary metric spaces. Indeed, among the applications of WSPD in fixed dimensional metrics are approximate ranking (though this application does not seem to have appeared in print — it was pointed out to us by Sariel Har-Peled), approximate distance oracles [19, 20], spanners [30, 20], and computation of the Lipschitz constant [20]. These applications have been obtained for general metrics using Ramsey partitions in the present paper (spanners were not discussed here since our approach does not seem to beat previously known constructions). We believe that this direction deserves further scrutiny, as there are more applications of WSPD which might be transferable to general metrics using Ramsey partitions.

Acknowledgments. We are grateful to Sariel Har-Peled for letting us use here his insights on the approximate ranking problem. We also thank Yair Bartal for helpful discussions.

Appendices

A The Size-Ancestor data structure

In this appendix we prove Lemma 4.3. Without loss of generality we assume that the tree T does not contain vertices with only one child. Indeed, such vertices will never be returned as an answer for a query, and thus can be eliminated in O(n) time in a preprocessing step.

Our data structure is composed in a modular way of two different data structures, the first of which is described in the following lemma, while the second is discussed in the proof of Lemma 4.3 that will follow.

Lemma A.1. Fix m ∈ , and let T be as in Lemma 4.3. Then there exists a data structure which can be preprocessed in time O (n + \frac{n logn}{m}), and answers in time O(1) the following query: Given ℓ ∈ and a leaf x ∈ V, find an ancestor u of x such that ℓ_{T}(u) < ℓm ≤ ℓ(parent(u)). Here we use the convention ℓ(parent(root)) = ∞.

Proof. Denote by X the set of leaves of T. For every internal vertex v ∈ V, order its children non-increasingly according to the number of leaves in the subtrees rooted at them. Such a choice of labels induces a unique total order on X (the lexicographic order). Denote this order by and let f : {1, …, n} → X be the unique increasing map in the total order . For every v ∈ V, f^{−1} (ℒ_{T}(v)) is an interval of integers. Moreover, the set of intervals {f^{−1} (ℒ_{T}(v)) : v ∈ V}forms a laminar set, i.e. for every pair of intervals in this set either one is contained in the other, or they are disjoint. For every v ∈ V write f^{−1} (ℒ_{T}(v)) = I_{v} = [A_{v}, B_{v}], where A_{v}, B_{v} ∈ and A_{v} ≤ B_{v}. For i ∈ {1, …, ⌊n/m⌋} and j ∈ {1, …, ⌈n/(im)⌉} let F_{i}(j) be the set of vertices v ∈ V such that |I_{v}| ≥ im, I_{v} ∩ [(j − 1)im + 1, jim] ∅, and there is no descendant of v satisfying these two conditions. Since at most two disjoint intervals of length least im can intersect a given interval of length im, we see that for all i, j, |F_{i}(j)| ≤ 2.

Claim A.2. Let x ∈ X be a leaf of T, and ℓ ∈ . Let u ∈ V be the least ancestor of x for which ℓ_{T}(u) ≥ ℓm. Then

u ∈ \{lca(x, v) : v ∈ F_{ℓ}(⌈\frac{f (x)}{ℓm}⌉)\}.

Proof. If u ∈ F_{ℓ}(⌈\frac{f (x)}{ℓm}⌉)then since u = lca(x, u) there is nothing to prove. If on the other hand u F_{ℓ}(⌈\frac{f (x)}{ℓm}⌉) then since we are assuming that that ℓ_{T}(u) ≥ ℓm, and I_{u} ∩ [(⌈\frac{f (x)}{ℓm}⌉− 1) ℓm + 1, ⌈\frac{f (x)}{ℓm}⌉ℓm] ∅ (because f (x) ∈ I_{u}), it follows that u has a descendant v in F_{ℓ}(⌈\frac{f (x)}{ℓm}⌉). Thus u = lca(x, v), by the fact that any ancestor w of v satisfies ℓ_{T}(w) ≥ ℓ_{T}(v) ≥ ℓm, and the minimality of u.

Our data-structure will first of all order the children of vertices non-increasingly according to the number of leaves in their subtrees. To do this we first compute for each vertex u ∈ V the number ℓ_{T}(u). This is done using depth first search in O(n) time. We then sort all the vertices of the tree according to ℓ_{T}(·) in O(n) time using bucket sort (see [15, Ch. 9] — we are using here the fact that the O(n) numbers {ℓ_{T}(u)}_{u∈V} are in the range {0, …, n}). Next, we initialize for each vertex u a new empty list called ChildrenSortedList_{u}. And then scan our list of all vertices sorted (decreasingly) according to ℓ_{T}(·), and when reaching a vertex v in the list, we add v to the end of ChildrenSortedList_{parent(v)}. In the end of this process, for each vertex u the list ChildrenSortedList_{u} is the list of its children, sorted decreasingly according to ℓ_{T}(·), as needed. Computing f, and the intervals {I_{u}}_{u∈V} is now done by a depth-first scan of the tree that respects the order of the children.

We next compute {F_{i}(j) : i ∈ {1, …, ⌊n/m⌋}, j ∈ {1, …, ⌈n/(im)⌉} using the following algorithm:

SUBTREE-COUNT(u) Let v_{1}, …, v_{r} be the children of u with |I_{v_{1}}| ≥ |I_{v_{2}}| ≥ ⋯≥ |I_{v_{r}}|. For i ← ⌊|I_{u}|/m⌋down to ⌊|I_{v_{1}}|/m⌋+ 1 do For j ← ⌊A_{u}/(im)⌋ to ⌈B_{u}/(im)⌉ do

Add u to F_{i}(j)

For h ← 1 to r − 1 do

For i ← ⌊|I_{v_{h}}|/m⌋down to ⌊|I_{v_{h+1}}|/m⌋+ 1 do For j ← ⌈B_{v_{h}}/(im)⌉ + 1 to ⌈B_{u}/(im)⌉ do

Add u to F_{i}(j)

For h ← 1 to r do call SUBTREE-COUNT(v_{h})

Here is an informal explanation of the correctness of this algorithm. The only relevant sets F_{i}(·) which will contain a vertex u ∈ V are those in the range i ∈ [⌊|I_{v_{r}}|/m⌋ + 1, ⌊|I_{u}|/m⌋]; above this range I_{u} does not meet the size constraint, and below this range any F_{i}(j) which intersects I_{u} must also intersect one of the children of u, which also satisfies the size constraint, in which case one of the descendants of u will be in F_{i}(j). In the aforementioned range, we add u to F_{i}(j) only for j such that the interval [(j − 1)im + 1, jim] does not intersect one of the children of u in a set of size larger than im. Here we use the fact that the intervals of the children are sorted in non-increasing order according to their size. Regarding running time, this reasoning implies that each vertex of T, and each entry in F_{i}(j), is accessed by this algorithm only a constant number of times, and each access involves only constant number of computation steps. So the running time is

O (n + ∑_{i=1}^{⌊n/m⌋} ∑_{j=1}^{⌈n/(im)⌉}|F_{i}(j)|) = O (n + \frac{n logn}{m}) .

We conclude with the query procedure. Given a query x ∈ X and ℓ ∈ , access F_{ℓ}(⌈\frac{f (x)}{ℓ}⌉) in O(1) time. Next, for each v ∈ F_{ℓ}(⌈\frac{f (x)}{ℓ}⌉), check whether lca(x, v) is the required vertex (we are thus using here also the data structure for computing the lca of [21, 6]. Observe also that since |F_{i}(j)| ≤ 2, we only have a constant number of checks to do). By Claim A.2 this will yield the required result.

By setting m = 1 in Lemma A.1, we obtain a data structure for the Size-Ancestor problem with O(1) query time. However, the preprocessing time is O(n logn). To improve upon this, we set m = Θ(logn) in Lemma A.1, and deal with the resulting gaps by enumerating all the possible ways in which the remaining m − 1 leaves can be added to the tree. Exact details are given below.

Proof of Lemma 4.3. Fix m = ⌊(logn)/4⌋. Each subset A ⊆ {0, …, m − 1} is represented as a number #A ∈ {0, …, 2^{m} − 1} by #A = ∑ _{i∈A}2^{i}. We next construct in memory a vector enum of size 2^{m}, where enum[#A] is a vector of size m, with integer index in the range {1, …, m}, such that enum[#A][i] = |A ∩ {0, …, i − 1}|. Clearly enum can be constructed in O(2^{m}m) = o(n) time.

For each vertex u we compute and store:

• depth(u) which is the edge’s distance from the root to u.

• ℓ_{T}(u), the number of of leaves in the subtree rooted at u.

• The number #A_{u}, where

A_{u} = {k ∈ {0, …, m − 1} : u has an ancestor with exactly l(u) + k descendant leaves}.

We also apply the level ancestor data-structure, that after O(n) preprocessing time, answers in constant time queries of the form: Given a vertex u and an integer d, find an ancestor of u at depth d (if it exists) (such a data structure is constructed in [7]). Lastly, we use the data structure from Lemma A.1

With all this machinary in place, a query for the least ancestor of a leaf x having at least ℓ leaves is answered in constant time as follows. First compute q = ⌊ℓ/m⌋. Apply a query to the data structure of Lemma A.1, with x and q, and obtain u, the least ancestor of x such that ℓ_{T}(u) ≥ qm. If ℓ_{T}(u) ≥ ℓ then u is the least ancestor with ℓ leaves, so the data-structure returns u. Otherwise, ℓ_{T}(u) < ℓ, and let a = enum[#A_{u}][ℓ − ℓ_{T}(u)]. Note that depth(u) − a is the depth of the least ancestor of u having at least ℓ leaves, thus the query uses the level ancestor data-structure to return this ancestor. Clearly the whole query takes a constant time.

It remains to argue that the data structure can be preprocessed in linear time. We already argued about most parts of the data structure, and ℓ_{T}(u) and depth(u) are easy to compute in linear time. Thus we are left with computing #A_{u} for each vertex u. This is done using a top-down scan of the tree (similar to depth first search). The root is assigned with 1. Each non-root vertex u, whose parent is v, is assigned

#A_{u} ← \begin{cases}1 & if ℓ_{T}(v) ≥ ℓ_{T}(u) + m \\ #A_{v} · 2^{ℓ_{T}(v)−ℓ_{T}(u)}+ 1 (mod 2^{m}) & otherwise. \end{cases}

It is clear that this indeed computes #A_{u}. The computation on each vertex takes constant time (and we do not need to assume constant time exponentiation, since it is possible to construct a lookup table with all the relevant exponents in O(m) time in advance).

Remark A.1. This data structure can be modified in a straightforward way to answer queries to the least ancestor of a given size (in terms of the number of vertices in its subtree). It is also easy to extend it to queries which are non-leaf vertices.

B The metric Ramsey theorem implies the existence of Ramsey partitions

In this appendix we complete the discussion in Section 2 by showing that the metric Ramsey theorem implies the existence of good Ramsey partitions. The results here are not otherwise used in this paper.

Proposition B.1. Fix α ≥ 1 and ψ ∈ (0, 1), and assume that every n-point metric space has a subset of size n^{ψ} which is α-equivalent to an ultrametric. Then every n-point metric space (X, d_{X}) admits a distribution over partition trees {ℛ_{k}} _{k=0}^{∞} such that for every x ∈ X,

Pr[∀ k ∈ , B_{X}(x, \frac{1}{96α} · 8^{−k} diam(X))⊆ ℛ_{k}(x)] ≥ \frac{1 − ψ}{n^{1−ψ}} .

Proof. Let (X, d_{X}) be an n-point metric space. The argument starts out similarly to the proof of Lemma 4.2. Using the assumptions and Lemma 4.1 iteratively, we find a decreasing chain of subsets X = X_{0} X_{1} X_{2} ⋯ X_{s} = ∅ and ultrametrics ρ_{1}, …, ρ_{s} on X, such that if we denote Y_{j} = X_{j−1} \ X_{j} then |Y_{j}| ≥ |X_{j−1} |^{ψ}, for x, y ∈ X, ρ_{j}(x, y) ≥ d_{X}(x, y), and for x ∈ X, y ∈ Y_{j} we have ρ_{j}(x, y) ≤ 6αd_{X}(x, y). As in the proof of Lemma 4.2, it follows by induction that s ≤ \frac{1}{1−ψ} · n^{1−ψ}.

By [5, Lemma 3.5] we may assume that the ultrametric ρ_{j} can be represented by an exact 2-HST T_{j} = (V_{j}, E_{j}), with vertex labels Δ_{T_{j}}, at the expense of replacing the factor 6 above by 12. Let Δ_{j} be the label of the root of T_{j}, and denote for k ∈ , Λ_{j}^{k} = {v ∈ V_{j} : Δ_{T_{j}}(v) = 2^{−k}Δ_{j}}. For every v ∈ V_{j} let ℒ_{j}(v) be the leaves of T_{j} which are descendants of v. Thus 𝒫_{j}^{k} {ℒ_{j}(v) : v ∈ Λ_{j}^{k}} is a 2^{−k}Δ_{j} bounded partition of X (boundedness is in the metric d_{X}). Fix x ∈ Y_{j} and let v be the unique ancestor of X in Λ_{j}^{k}. If z ∈ X is such that d_{X}(x, z) ≤ \frac{1}{12α} · 2^{−k}Δ_{j} then Δ_{T_{j}} (lca_{T_{j}}(x, z))= ρ_{j}(x, z) ≤ 2^{−k}Δ_{j}. It follows that z is a descendant of v, so that z ∈ 𝒫_{j}^{k}(x) = ℒ_{j}(v). Thus 𝒫_{j}^{k}(x) ⊇ B_{X}(x, \frac{1}{12α} · 2^{−k}Δ_{j} ).

Passing to powers of 8 (i.e. choosing for each k the integer ℓ such that 8^{−ℓ−1} diam(x) < 2^{−k}Δ_{j} ≤ 8^{−ℓ} diam(X) and indexing the above partitions using ℓ instead of k), we have thus shown that for every j ∈ {1, …, s} there is a partition tree {ℛ_{k}^{j}} _{k=0}^{∞} such that for every x ∈ Y_{j} we have for all k,

B_{X}(x, \frac{1}{96α} · 8^{−k} diam(X))⊆ ℛ_{k}^{j}(x).

Since the sets Y_{1}, …, Y_{s} cover X, and s ≤ \frac{n^{1−ψ}}{1−ψ} , the required distribution over partition trees can be obtained

by choosing one of the partition trees {ℛ_{k}^{1}} _{k=0}^{∞} , …, {ℛ_{k}^{s}} _{k=0}^{∞} uniformly at random.

Remark B.1. Motivated by the re-weighting argument in [12], it is possible to improve the lower bound in Proposition B.1 for ψ in a certain range. We shall now sketch this argument. It should be remarked, however, that there are several variants of this re-weighting procedure (like re-weighting again at each step), so it might be possible to slightly improve upon Proposition B.1 for a larger range of ψ. We did not attempt to optimize this argument here.

Fix η ∈ (0, 1) to be determined presently, and let (X, d_{X}) be an n-point metric space. Duplicate each point in X n^{η} times, obtaining a (semi-) metric space X′ with n^{1+η} points (this can be made into a metric by applying an arbitrarily small perturbation). We shall define inductively a decreasing chain of subsets X′ = X′_{0} X′_{1} X′_{2} ⋯as follows. For x ∈ X, let h_{i}(x) be the number of copies of x in X′_{i} (thus h_{0}(x) = n^{η}). Having defined X′_{i}, let Y_{i+1} ⊆ X′_{i} be a subset which is α-equivalent to an ultrametric and |Y_{i+1}| ≥ |X′_{i}|^{ψ}. We then define X′_{i+1} via

h_{i+1}(x) = \begin{cases}⌊h_{i}(x)/2⌋ & there exists a copy of x in Y_{i+1} \\ h_{i}(x) & otherwise. \end{cases}

Continue this procedure until we arrive at the empty set. Observe that

|X′_{i+1}| ≤ |X′_{i}| − \frac{1}{2}|X′_{i}|^{ψ} ≤ |X′_{i}| (1 − \frac{1}{2n^{(1+η)(1−ψ)}} ) .

Thus |X′_{i}| ≤ n^{1+η} · (1 − \frac{1}{2n^{(1+η)(1−ψ)}} )^{i−1}. It follows that this procedure terminates after O (n^{(1+η)(1−ψ)} logn) steps, and by construction each point of X appears in Θ (η logn) of the subsets Y_{i}. As in the proof of Proposition B.1, by selecting each of the Y_{i} uniformly at random we get a distribution over partition trees {ℛ_{k}} _{k=0}^{∞} such that for every x ∈ X,

Pr[∀ k ∈ , B_{X}(x, \frac{1}{96α} · 8^{−k} diam(X))⊆ ℛ_{k}(x)] ≥ Ω (\frac{η}{n^{(1+η)(1−ψ)}} ).

Optimizing over η ∈ (0, 1), we see that as long as 1 − ψ > \frac{1}{logn} we can choose η = \frac{1}{(1−ψ) logn} , yielding the probabilistic estimate

Pr[∀ k ∈ , B_{X}(x, \frac{1}{96α} · 8^{−k} diam(X))⊆ ℛ_{k}(x)] ≥ Ω (\frac{1}{(1 − ψ) logn} · \frac{1}{n^{1−ψ}} ).

This estimate is better than Proposition B.1 when \frac{1}{logn} < 1 − ψ < O ( \frac{1}{\sqrt{logn}}).

References

[1] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. In STOC ’05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 553–562, New York, NY, USA, 2005. ACM Press.

[2] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching. Journal of the ACM, 45:891–923, 1998.

[3] B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Near-linear time construction of sparse neighborhood covers. SIAM J. Comput., 28(1):263–277, 1999.

[4] Y. Bartal. Probabilistic approximations of metric space and its algorithmic application. In 37th Annual Symposium on Foundations of Computer Science, pages 183–193, Oct. 1996.

[5] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey type phenomena. Ann. of Math. (2), 162(2):643–709, 2005.

[6] M. A. Bender and M. Farach-Colton. The lca problem revisited. In Proc. 4th Latin Amer. Symp. on Theor. Info., pages 88–94. Springer-Verlag, 2000.

[7] M. A. Bender and M. Farach-Colton. The level ancestor problem simplified. Theoretical Comput. Sci., 321(1):5–12, 2004.

[8] J. Bourgain, T. Figiel, and V. Milman. On Hilbertian subsets of finite metric spaces. Israel J. Math., 55(2):147–152, 1986.

[9] G. Calinescu, H. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. SIAM J. Comput., 34(2):358– 372 (electronic), 2004/05.

[10] P. B. Callahan. Dealing with higher dimensions: the well-separated pair decomposition and its applications. Ph.D. thesis, Dept. Comput. Sci., Johns Hopkins University, Baltimore, Maryland, 1995.

[11] P. B. Callahan and S. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67–90, 1995.

[12] S. Chawla, A. Gupta, and H. Räcke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In SODA ’05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 102– 111, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics.

[13] K. L. Clarkson. Nearest-Neighbor Searching and Metric Space Dimensions. In Nearest-Neighbor Methods for Learning and

    Vision: Theory and Practice. MIT Press. Available at http://cm.bell-labs.com/who/clarkson/nn survey/p.pdf,

2005.

[14] E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. Comput., 28(1):210–236, 1999.

[15] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1990.

[16] P. Erdős. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29–36. Publ. House Czechoslovak Acad. Sci., Prague, 1964.

[17] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004.

[18] C. Fefferman and B. Klartag. Fitting C^{m} smooth functions to data I. Preprint, availabe at

    http://www.math.princeton.edu/facultypapers/Fefferman/FittingData Part I.pdf, 2005.

[19] J. Gudmundsson, C. Levcopoulos, G. Narasimhan, and M. Smid. Approximate distance oracles for geometric graphs. In SODA ’02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 828–837, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics.

[20] S. Har-Peled and M. Mendel. Fast construction of nets in low dimensional metrics, and their applications. In SCG ’05: Proceedings of the twenty-first annual symposium on Computational geometry, pages 150–158, New York, NY, USA, 2005. ACM Press. Available at http://arxiv.org/abs/cs.DS/0409057, to appear in SIAM J. Computing.

[21] D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338–355, 1984.

[22] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[23] P. Indyk. Nearest neighbors in high-dimensional spaces. In Handbook of discrete and computational geometry, second edition, pages 877–892. CRC Press, Inc., Boca Raton, FL, USA, 2004.

[24] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metrics. Geom. Funct. Anal., 15(4):839–858, 2005.

[25] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005.

[26] J. Matoušek. On the distortion required for embedding finite metric space into normed spaces. Israel J. Math., 93:333–344, 1996.

[27] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451–494, 2004.

[28] M. T. Orchard. A fast nearest-neighbor search algorithm. In ICASSP ’91: Int. Conf. on Acoustics, Speech and Signal Processing, volume 4, pages 2297–3000, 1991.

[29] D. Peleg. Informative labeling schemes for graphs. Theoretical Computer Science, 340(3):577–593, 2005.

[30] K. Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In STOC ’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 281–290, New York, NY, USA, 2004. ACM Press.

[31] M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, 2005.

[32] P. M. Vaidya. An O(n logn) algorithm for the all-nearest-neighbors problem. Discrete Comput. Geom., 4(2):101–115, 1989.