Terminal Embeddings in Sublinear Time

Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a it terminal embedding from one metric space (X,dX) to another (Y,dY) with a set of designated terminals Tsubset 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 beginequation* forall x∈ T forall q∈ X, C dX(x, q) ≤ dY(f(x), f(q)) ≤ C ρ dX(x, q) . endequation* 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(ε-2log 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∈ ℝd required solving a semidefinite program with Theta(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∈ℝd in sublinear time O^* (n1-Theta(ε2) + d). To accomplish this, we leverage tools developed in the context of approximate nearest neighbor search.