text: In recent years, considerable advances have been made in the study of properties of metric spaces in terms of their doubling dimension. This line of research has not only enhanced our understanding of finite metrics, but has also resulted in many algorithmic applications. However, we still do not understand the interaction between various graph-theoretic (topological) properties of graphs, and the doubling (geometric) properties of the shortest-path metrics induced by them. For instance, the following natural question suggests itself: graph @math with @math such that the shortest path metric @math on @math is still doubling, and which agrees with @math on @math . This is often useful, given that unweighted graphs are often easier to reason about. We show that for any metric space @math , there is an graph @math with shortest-path metric @math such that -- for all @math , the distances @math , and -- the doubling dimension for @math is not much more than that of @math , where this change depends only on @math and not on the size of the graph. We show a similar result when both @math and @math are restricted to be trees: this gives a simpler proof that doubling trees embed into constant dimensional Euclidean space with constant distortion. We also show that our results are tight in terms of the tradeoff between distortion and dimension blowup.
  @cite_18: We present a simple deterministic data structure for maintaining a set S of points in a general metric space, while supporting proximity search (nearest neighbor and range queries) and updates to S (insertions and deletions). Our data structure consists of a sequence of progressively finer e-nets of S, with pointers that allow us to navigate easily from one scale to the next.We analyze the worst-case complexity of this data structure in terms of the "abstract dimensionality" of the metric S. Our data structure is extremely efficient for metrics of bounded dimension and is essentially optimal in a certain model of distance computation. Finally, as a special case, our approach improves over one recently devised by Karger and Ruhl [KR02].
  @cite_4: 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 dimension of X is then defined as dim (X) = log sub 2 spl lambda . A metric (or sequence of metrics) is called doubling precisely when its doubling dimension is bounded. This is a robust class of metric spaces which contains many families of metrics that occur in applied settings. We give tight bounds for embedding doubling metrics into (low-dimensional) normed spaces. We consider both general doubling metrics, as well as more restricted families such as those arising from trees, from graphs excluding a fixed minor, and from snowflaked metrics. Our techniques include decomposition theorems for doubling metrics, and an analysis of a fractal in the plane according to T. J. Laakso (2002). Finally, we discuss some applications and point out a central open question regarding dimensionality reduction in L sub 2 .
  @cite_7: We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [16]. Let Z ∞ d be the infinite graph whose vertex set is Zd and which has an edge (u,v) whenever ||u-v|| ∞ = 1. Let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of Z ∞d . The growth rate of G, denoted ρ G , is the minimum ρ such that every ball of radius r > 1 in G contains at most rρ vertices. By simple volume arguments, dim(G) = Ω(ρ G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ G ) for every graph G.Previously, it was not known whether dim(G) could be upper bounded by any function of ρ G , even in the special case of trees. We show that a weaker form of Levin's conjecture holds by proving that, for every graph G, dim(G) = O(ρ G log ρ G ). We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) =Ω(ρ G log ρ G ). For families of graphs which exclude a fixed minor, we salvage the strong form, showing that dim(G) = O(ρ G ). This holds also for graphs without long induced simple cycles. Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces due to Linial[15].
  @cite_9: We present a tree data structure for fast nearest neighbor operations in general n-point metric spaces (where the data set consists of n points). The data structure requires O(n) space regardless of the metric's structure yet maintains all performance properties of a navigating net (Krauthgamer & Lee, 2004b). If the point set has a bounded expansion constant c, which is a measure of the intrinsic dimensionality, as defined in (Karger & Ruhl, 2002), the cover tree data structure can be constructed in O (c6n log n) time. Furthermore, nearest neighbor queries require time only logarithmic in n, in particular O (c12 log n) time. Our experimental results show speedups over the brute force search varying between one and several orders of magnitude on natural machine learning datasets.
  @cite_21: We consider the problem of name-independent routing in doubling metrics. A doubling metric is a metric space whose doubling dimension is a constant, where the doubling dimension of a metric space is the least value α such that any ball of radius r can be covered by at most 2α balls of radius r 2.Given any δ>0 and a weighted undirected network G whose shortest path metric d is a doubling metric with doubling dimension α, we present a name-independent routing scheme for G with (9+δ)-stretch, (2+1 δ)O(α) (log δ)2 (log n)-bit routing information at each node, and packet headers of size O(log n), where δ is the ratio of the largest to the smallest shortest path distance in G.In addition, we prove that for any e ∈ (0,8), there is a doubling metric network G with n nodes, doubling dimension α ≤ 6 - log e, and Δ=O(21 en) such that any name-independent routing scheme on G with routing information at each node of size o(n(e 60)2)-bits has stretch larger than 9-e. Therefore assuming that Δ is bounded by a polynomial on n, our algorithm basically achieves optimal stretch for name-independent routing in doubling metrics with packet header size and routing information at each node both bounded by a polylogarithmic function of n.
  @cite_1: In this article we introduce the notion of nearest-neighbor-preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest-neighbors. We give two examples of such embeddings for Euclidean metrics with low “intrinsic” dimension. Combining the embeddings with known data structures yields the best-known approximate nearest-neighbor data structures for such metrics.
  @cite_3: 
  @cite_0: 
  @cite_19: We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms for the following problems: approximate nearest neighbor search, well-separated pair decomposition, spanner construction, compact representation scheme, doubling measure, and computation of the (approximate) Lipschitz constant of a function. In all cases, the running (preprocessing) time is near linear and the space being used is linear.
  @cite_12: 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 natural analog to the dimension of a Euclidean space. If we could embed metrics with low doubling dimension into low dimensional Euclidean spaces, they would inherit several algorithmic and structural properties of the Euclidean spaces. Unfortunately however, such a restriction on dimension does not suffice to guarantee embeddibility in a normed space.In this paper we explore the option of bypassing the embedding. In particular we show the following for low dimensional metrics: Quasi-polynomial time (1+e)-approximation algorithm for various optimization problems such as TSP, k-median and facility location. (1+e)-approximate distance labeling scheme with optimal label length. (1+e)-stretch polylogarithmic storage routing scheme.
  @cite_20: A Lipschitz embedding of a mctric space (X, d) into another one (Y, 8) is an application : X -»• Y such that : 3 1. B 6 ]0, + oo [. Vx. x ' e X, Ad(x, x ' ) 6( (x), f x' ) Bd(x, x'). We dcscribe here three mcthods to obtain Lipschitz embeddings of the metric space (R*, || ||) into some metric space (R", || || ). The third method allows us to minimize, for k = 1, the rank ofsuch an embedding (i.c. to obtain the minimal value of the integer n).
  @cite_17: We present a new data structure that facilitates approximate nearest neighbor searches on a dynamic set of points in a metric space that has a bounded doubling dimension. Our data structure has linear size and supports insertions and deletions in O(log n) time, and finds a (1+e)-approximate nearest neighbor in time O(log n) + (1 e)O(1). The search and update times hide multiplicative factors that depend on the doubling dimension; the space does not. These performance times are independent of the aspect ratio (or spread) of the points.
summary: The notion of doubling dimension was introduced by Assouad @cite_20 and first used in algorithm design by Clarkson @cite_0 . The properties of doubling metrics and their algorithmic applications have since been studied extensively, a few examples of which appear in @cite_4 @cite_7 @cite_18 @cite_12 @cite_19 @cite_9 @cite_17 @cite_1 @cite_21 @cite_3 .