  A distance labeling scheme is an assignment of bit-labels to the vertices of
an undirected, unweighted graph such that the distance between any pair of
vertices can be decoded solely from their labels. We propose a series of new
labeling schemes within the framework of so-called hub labeling (HL, also known
as landmark labeling or 2-hop-cover labeling), in which each node $u$ stores
its distance to all nodes from an appropriately chosen set of hubs $S(u)
\subseteq V$. For a queried pair of nodes $(u,v)$, the length of a shortest
$u-v$-path passing through a hub node from $S(u)\cap S(v)$ is then used as an
upper bound on the distance between $u$ and $v$.
  We present a hub labeling which allows us to decode exact distances in sparse
graphs using labels of size sublinear in the number of nodes. For graphs with
at most $n$ nodes and average degree $\Delta$, the tradeoff between label bit
size $L$ and query decoding time $T$ for our approach is given by $L = O(n \log
\log_\Delta T / \log_\Delta T)$, for any $T \leq n$. Our simple approach is
thus the first sublinear-space distance labeling for sparse graphs that
simultaneously admits small decoding time (for constant $\Delta$, we can
achieve any $T=\omega(1)$ while maintaining $L=o(n)$), and it also provides an
improvement in terms of label size with respect to previous slower approaches.
  By using similar techniques, we then present a $2$-additive labeling scheme
for general graphs, i.e., one in which the decoder provides a
2-additive-approximation of the distance between any pair of nodes. We achieve
almost the same label size-time tradeoff $L = O(n \log^2 \log T / \log T)$, for
any $T \leq n$. To our knowledge, this is the first additive scheme with
constant absolute error to use labels of sublinear size. The corresponding
decoding time is then small (any $T=\omega(1)$ is sufficient).
