# Terminal Embeddings in Sublinear Time

arXiv: https://arxiv.org/abs/2110.08691 · HTML: https://mlsanity.com/paper/2110.08691/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 11 references that are in the map.
- First posted on arXiv 17 Oct 2021.

## Builds on (most cited first, 4 of 4)

- [Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors](https://mlsanity.com/paper/1608.03580/) (2016)
- [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018)
- [On Adaptive Distance Estimation](https://mlsanity.com/paper/2010.11252/) (2020)
- [Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions](https://mlsanity.com/paper/1811.03591/) (2018)

## Built on by (most cited first, 6 of 6)

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations](https://mlsanity.com/paper/2212.11408/) (2022)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [On Outer Bi-Lipschitz Extensions of Linear Johnson-Lindenstrauss Embeddings of Low-Dimensional Submanifolds of ℝN](https://mlsanity.com/paper/2206.03376/) (2022)
- [Dimension-Independent Kernel ε-Covers](https://mlsanity.com/paper/2306.16516/) (2023)
- [Beyond Worst-Case Dimensionality Reduction for Sparse Vectors](https://mlsanity.com/paper/2502.19865/) (2025)

## Abstract (arXiv)

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.