Terminal Embeddings in Sublinear Time

Abstract

Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a terminal embedding from one metric space (X,d_X) to another (Y,d_Y) 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(^-2 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^d 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 qR^d in sublinear time O^* (n^1-(^2) + d). To accomplish this, we leverage tools developed in the context of approximate nearest neighbor search.

Tasks

Reproductions