  We consider the problem of matching a metric space $(X,d_X)$ of size $k$ with
a subspace of a metric space $(Y,d_Y)$ of size $n \geq k$, assuming that these
two spaces have constant doubling dimension $\delta$. More precisely, given an
input parameter $\rho \geq 1$, the $\rho$-distortion problem is to find a
one-to-one mapping from $X$ to $Y$ that distorts distances by a factor at most
$\rho$. We first show by a reduction from $k$-clique that, in doubling
dimension $\log_2 3$, this problem is NP-hard and W[1]-hard. Then we provide a
near-linear time approximation algorithm for fixed $k$: Given an approximation
ratio $0<\varepsilon\leq 1$, and a positive instance of the $\rho$-distortion
problem, our algorithm returns a solution to the
$(1+\varepsilon)\rho$-distortion problem in time $(\rho/\varepsilon)^{O(1)}n
\log n$. We also show how to extend these results to the minimum distortion
problem in doubling spaces: We prove the same hardness results, and for fixed
$k$, we give a $(1+\varepsilon)$-approximation algorithm running in time
$($dist$(X,Y)/\varepsilon)^{O(1)}n^2\log n$, where dist$(X,Y)$ denotes the
minimum distortion between $X$ and $Y$.
