We investigate for which metric spaces the performance of distance labeling and of @math -embeddings differ, and how significant can this difference be. Recall that a distance labeling is a distributed representation of distances in a metric space @math , where each point @math is assigned a succinct label, such that the distance between any two points @math can be approximated given only their labels. A highly structured special case is an embedding into @math , where each point @math is assigned a vector @math such that @math is approximately @math . The performance of a distance labeling or an @math -embedding is measured via its distortion and its label-size dimension. We also study the analogous question for the prioritized versions of these two measures. Here, a priority order @math of the point set @math is given, and higher-priority points should have shorter labels. Formally, a distance labeling has prioritized label-size @math if every @math has label size at most @math . Similarly, an embedding @math has prioritized dimension @math if @math is non-zero only in the first @math coordinates. In addition, we compare these their prioritized measures to their classical (worst-case) versions. We answer these questions in several scenarios, uncovering a surprisingly diverse range of behaviors. First, in some cases labelings and embeddings have very similar worst-case performance, but in other cases there is a huge disparity. However in the prioritized setting, we most often find a strict separation between the performance of labelings and embeddings. And finally, when comparing the classical and prioritized settings, we find that the worst-case bound for label size often translates'' to a prioritized one, but also a surprising exception to this rule.
@cite_30: We study the problem of embedding weighted graphs of pathwidth k into lp spaces. Our main result is an O(kmin 1p,12 )-distortion embedding. For p=1, this is a super-exponential improvement over the best previous bound of Lee and Sidiropoulos. Our distortion bound is asymptotically tight for any fixed p >1. Our result is obtained via a novel embedding technique that is based on low depth decompositions of a graph via shortest paths. The core new idea is that given a geodesic shortest path P, we can probabilistically embed all points into 2 dimensions with respect to P. For p>2 our embedding also implies improved distortion on bounded treewidth graphs (O((klogn)1p)). For asymptotically large p, our results also implies improved distortion on graphs excluding a minor.
@cite_29: Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic methodology, which has been successfully applied for approximation algorithms [N. Linial, E. London, and Y. Rabinovich, Combinatorica, 15 (1995), pp. 215--245], online algorithms [N. , Proceedings of the 52th Annual IEEE Symposium on Foundations of Computer Science, FOCS '08, IEEE Computer Society, Washington, DC, 2011, pp. 267--276], distributed algorithms [M. , Distrib. Comput., 25 (2012), pp. 189--205], and for computing sparsifiers [Y. Shavitt and T. Tankel, IEEE ACM Trans. Netw., 12 (2004), pp. 993--1006]. However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric, and one could not specify in advance which vertices points should enjoy a better service (i.e., stretch distortion, label size dimension) than that given by the worst-case guarantee. In this paper...
@cite_3: It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an O(log n) space label for each vertex and then we can determine if one vertex can reach another considering their two labels only.The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from 0, …, N , it approximates distances within a factor (1 + e) in O(log log (nN) + 1 e) time. Our scheme can be extended to find and route along correspondingly short dipaths.
@cite_2: 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 probability measure. This provides a refined and unified framework for the two primary methods of constructing Frechet embeddings for finite metrics, due to Bourgain (1985) and Rao (1999). We prove that any n-point metric space (X, d) embeds in Hilbert space with distortion (O ( _ X n ) , ) where α X is a geometric estimate on the decomposability of X. As an immediate corollary, we obtain an (O ( ( _ X ) n ) ) distortion embedding, where λ X is the doubling constant of X. Since λ X ≤ n, this result recovers Bourgain’s theorem, but when the metric X is, in a sense, “low-dimensional,” improved bounds are achieved.
@cite_16: This paper contains the cornerstone theorem of the series. We study the structure of graphs with no minor isomorphic to a fixed graph L, when L is non-planar. (The case when L is planar was studied in an earlier paper.) We find that every graph with no minor isomorphic to L may be constructed by piecing together in a tree-structure graphs each of which "almost" embeds in some surface in which L cannot be embedded.
@cite_25: We study a novel separator property called k-path separable. Roughly speaking, a k-path separable graph can be recursively separated into smaller components by sequentially removing k shortest paths. Our main result is that every minor free weighted graph is k-path separable. We then show that k-path separable graphs can be used to solve several object location problems: (1) a small-worldization with an average poly-logarithmic number of hops; (2) an (1 + e)-approximate distance labeling scheme with O(log n) space labels; (3) a stretch-(1 + e) compact routing scheme with tables of poly-logarithmic space; (4) an (1 + e)-approximate distance oracle with O(n log n) space and O(log n) query time. Our results generalizes to much wider classes of weighted graphs, namely to bounded-dimension isometric sparable graphs.
@cite_17: We describe a method for preprocessing a weighted planar undirected graph and representing the results of the preprocessing so as to facilitate subsequent approximate distance queries. For any 0 2 n distances. By using compressed representation of the distances, the number of bytes required is about .5ne-1(9 + 3 log e-1)log 2 n (at the expense of a small increase in query time).
For distortion @math in planar graphs, Thorup @cite_3 and Klein @cite_17 constructed distance labels of size @math . Abraham and Gavoille @cite_25 generalized this result to @math -minor-free graphs, achieving label size @math . @math is a function that depends on @math only, taken from the structure theorem of Robertson and Seymour @cite_16 . No low-dimension embedding into @math with distortion @math is known for planar graphs or even treewidth- @math graphs. If one allows larger distortion, Krauthgamer al @cite_2 proved that planar graphs embed with distortion @math into @math , or more generally that @math -minor-free graphs embed with distortion @math into @math . Abraham al @cite_30 showed that @math -minor-free graphs embed with distortion @math into @math . Turning to priorities, Elkin al @cite_29 constructed prioritized versions of distance labeling with distortion @math . Specifically, for planar and @math -minor-free graphs they achieve label sizes of @math and @math , respectively. No prioritized embeddings are known, nor lower bounds thereof.