Terminal Embeddings in Sublinear Time

Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a { terminal embedding} from one metric space (X,dX) to another (Y,dY) with a set of designated terminals T⊂ X. Such an embedding f is said to have distortion ρ≥ 1 if ρ is the smallest value such that there exists a constant $C>0$ satisfying {equation*} ∀ x∈ T\ ∀ q∈ X,\ C d_X(x, q) ≤ d_Y(f(x), f(q)) ≤ C ρ d_X(x, q) . {equation*} When $X,Y$ are both Euclidean metrics with Y being m-dimensional, recently (Narayanan, Nelson 2019), following work of (Mahabadi, Makarychev, Makarychev, Razenshteyn 2018), showed that distortion 1+ε is achievable via such a terminal embedding with m = O(ε⁻²log n) for $n := |T|$. This generalizes the Johnson-Lindenstrauss lemma, which only preserves distances within T and not to T from the rest of space. The downside of prior work is that evaluating their embedding on some q∈ Rᵈ required solving a semidefinite program with Θ(n) constraints in~m variables and thus required some superlinear poly(n) runtime. Our main contribution in this work is to give a new data structure for computing terminal embeddings. We show how to pre-process T to obtain an almost linear-space data structure that supports computing the terminal embedding image of any qᵈ in sublinear time O^* (n1-Θ(ε²) + d). To accomplish this, we leverage tools developed in the context of approximate nearest neighbor search.