The Nearest Neighbor Search (NNS) problem asks to design a data structure that preprocesses an n-point dataset X lying in a metric space ℳ, so that given a query point q ∈ ℳ, one can quickly return a point of X minimizing the distance to q. The efficiency of such a data structure is evaluated primarily by the amount of space it uses and the time required to answer a query. We focus on the fast query-time regime, which is crucial for modern large-scale applications, where datasets are massive and queries must be processed online, and is often modeled by query time poly(d log n) when ℳ is a d-dimensional normed space. Our main result is such a randomized data structure for NNS in 𝓁_p^d spaces, p > 2, that achieves p^{O(1) + log log p} approximation with fast query time and poly(dn) space. Our data structure improves, or is incomparable to, the state-of-the-art for the fast query-time regime from [Bartal and Gottlieb, TCS 2019] and [Krauthgamer, Petruschka and Sapir, FOCS 2025].

Metric decompositions are a fundamental tool in the design of algorithms involving distances. We study fast algorithms for sampling from probabilistic metric decompositions of n-point sets in 𝓁_∞ and 𝓁₂ spaces of high dimension d. For 𝓁_∞, we design a padded-decomposition algorithm that runs in time Õ(nd²), which is near-linear in n, and achieves padding parameter Õ(log n). Our algorithm constructs a new sparse neighborhood cover that is based on geometric properties of 𝓁_∞ [Indyk, JCSS'01], and utilizes recent reductions between covers and decompositions [Conroy and Filtser, STOC'25]. For 𝓁₂, we design a separating-decomposition algorithm that achieves near optimal separation Õ(√{log n}) in almost-linear time n^{1+o(1)}. Our bounds improve over known algorithms with similar running time by a factor Ω(√{log n}), and the techniques have additional applications to spanners and nearest-neighbor search.

Lipschitz decomposition is a useful tool in the design of efficient algorithms involving metric spaces. While many bounds are known for different families of finite metrics, the optimal parameters for $n$-point subsets of $\ell_p$, for $p > 2$, remained open, see e.g. [Naor, SODA 2017]. We make significant progress on this question and establish the bound $β=O(\log^{1-1/p} n)$. Building on prior work, we demonstrate applications of this result to two problems, high-dimensional geometric spanners and distance labeling schemes. In addition, we sharpen a related decomposition bound for $1

Metric embedding is a powerful tool used extensively in mathematics and computer science. We devise a new method of using metric embeddings recursively, which turns out to be particularly effective in $\ell_{p}$ spaces, $p \lt 2$, yielding state-of-theart results for Lipschitz decomposition, for Nearest Neighbor Search, and for embedding into $\ell_{2}$. In a nutshell, our method composes metric embeddings by viewing them as reductions between problems, and thereby obtains a new reduction that is substantially more effective than the known reduction that employs a single embedding. We in fact apply this method recursively, oftentimes using double recursion, which further amplifies the gap from a single embedding. Index Terms-Metric Embedding, Lipschitz Decomposition, Nearest Neighbor Search, $\ell_{p}$ norm