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_5: We show that the vertices of an edge-weighted undirected graph can be labeled with labels of size O(n) such that the exact distance between any two vertices can be inferred from their labels alone in O(log^@?n) time. This improves the previous best exact distance labeling scheme that also requires O(n)-sized labels but O(loglogn) time to compute the distance. Our scheme is almost optimal as exact distance labeling is known to require labels of length @W(n).
@cite_31: We consider distance labeling schemes for trees: given a tree with n nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, by looking only at the labels, the distance in the tree between the two nodes. A lower bound by [, J. Alg., 2004] and an upper bound by Peleg [Peleg, J. Graph Theory, 2000] establish that labels must use Theta(log^2(n)) bits. [, ESA, 2001] show that for very small approximate stretch, labels use Theta(log(n) log(log(n))) bits. Several other papers investigate various variants such as, for example, small distances in trees [, SODA, 2003]. We improve the known upper and lower bounds of exact distance labeling by showing that 1 4*log^2(n) bits are needed and that 1 2*log^2(n) bits are sufficient. We also give (1 + epsilon)-stretch labeling schemes using Theta(log(n)) bits for constant epsilon > 0. (1 + epsilon)-stretch labeling schemes with polylogarithmic label size have previously been established for doubling dimension graphs by Talwar [Talwar, STOC, 2004]. In addition, we present matching upper and lower bounds for distance labeling for caterpillars, showing that labels must have size 2*log(n) - Theta(log(log(n))). For simple paths with k nodes and edge weights in [1,n], we show that labels must have size (k - 1) k*log(n) + Theta(log(k)).
@cite_20: 
Exact distance labelings were studied in the precession of bits (i.e. not asymptotically) see e.g. @cite_31 . Another type of labeling studied is adjacency labeling @cite_20 , where given two labels one can compute whether the vertices are adjacent. Efficiency of the labeling algorithms has also been studied @cite_5 .