Terminal Embeddings in Sublinear Time

Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a terminal embedding from one metric space (𝑋, 𝑑 𝑋 ) to another (𝑌 , 𝑑 𝑌 ) with a set of designated terminals 𝑇 ⊂ 𝑋. Such an embedding 𝑓 is said to have distortion 𝜌 ⩾ 1 if 𝜌 is the smallest value such that there exists a constant 𝐶 > 0 satisfying ∀𝑥 ∈ 𝑇 ∀𝑞 ∈ 𝑋, 𝐶𝑑 𝑋 (𝑥, 𝑞) ⩽ 𝑑 𝑌 ( 𝑓 (𝑥), 𝑓 (𝑞)) ⩽ 𝐶𝜌𝑑 𝑋 (𝑥, 𝑞).

When 𝑋, 𝑌 are both Euclidean metrics with 𝑌 being 𝑚-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 𝑚 = 𝑂(𝜀 -2 log 𝑛) for 𝑛 := |𝑇 |. This generalizes the Johnson-Lindenstrauss lemma, which only preserves distances within 𝑇 and not to 𝑇 from the rest of space. The downside of prior work is that evaluating their embedding on some 𝑞 ∈ R 𝑑 required solving a semidefinite program with Θ(𝑛) constraints in 𝑚 variables and thus required some superlinear poly(𝑛) runtime. Our main contribution in this work is to give a new data structure for computing terminal embeddings. We show how to pre-process 𝑇 to obtain an almost linear-space data structure that supports computing the terminal embedding image of any 𝑞 ∈ R 𝑑 in sublinear time 𝑂 * (𝑛 1-Θ(𝜀 2 ) + 𝑑). To accomplish this, we leverage tools developed in the context of approximate nearest neighbor search.