Approximate Nearest Neighbor in Ultra-High Dimensional $\ell_\infty$

Nathan White; Tian Zhang

Source-linked AI summary

Approximate Nearest Neighbor in Ultra-High Dimensional $\ell_\infty$

Nathan White, Tian Zhang

arXiv:2609.09427v1Sep 8, 2026cs.DS

TL;DR

In ultra-high-dimensional ANN, d far exceeds n, and query time should not depend on d; reading an entire query can itself take Ω(d) time. The paper introduces subset embeddings: selected original coordinates that preserve dataset pairwise distances within a distortion factor. For any c ≥ 1, an ℓ∞ subset embedding with distortion O(c) uses n^(1+1/c) coordinates; for sufficiently large c,n, some datasets require n^(1+Ω(1/c)) coordinates at distortion at most c.

Problem
In ultra-high-dimensional ANN, d far exceeds n, and query time should not depend on d; reading an entire query can itself take Ω(d) time.
Source: §1 · p. 2
Method
The paper introduces subset embeddings: selected original coordinates that preserve dataset pairwise distances within a distortion factor.
Source: §1.2 · p. 4
Results
For any c ≥ 1, an ℓ∞ subset embedding with distortion O(c) uses n^(1+1/c) coordinates; for sufficiently large c,n, some datasets require n^(1+Ω(1/c)) coordinates at distortion at most c.
Source: §1.2 · p. 4, §3.1 · p. 8
Takeaways & Limitations
The subset-embedding coordinate bound is matched up to constants in the exponent’s dependence on 1/c.
Source: §1.2 · p. 4
The direct approach of applying a high-dimensional ANN structure to the reduced embedding exceeds O(n^2 log d) space and needs additional steps.
Source: §1.3 · p. 5

Abstract

from arXiv · show

We study the approximate nearest neighbor problem under $\ell_\infty$ in the ultra-high dimensional setting where the dimension $d$ is significantly larger than the number of points $n$. Thus, we desire data structures with no dependence on $d$ in the query time. [Herold-Nanongkai-Spoerhase-Varma-Wu, SoCG 2025] introduce this problem and give data structures in $\ell_p$: for $p=1,2$, they give $(1+\varepsilon)$-approximation data structures with space $\tilde{O}(n\log d/\text{poly}(\varepsilon))$ and query time $\tilde{O}(n/\text{poly}(\varepsilon))$. Since any data structure must have query time $\Omega(\min \{n,d\})$, this query time is nearly tight. However, their results are inefficient for $\ell_\infty$, with query time $\Omega(nd)$. In order to handle the challenges of $\ell_\infty$, we introduce a notion of subset embeddings, which embed points by simply selecting a subset of dimensions. In particular, we show one may preserve all pairwise distances of an $n$ point dataset up to a factor of $O(c)$ by computing distances on only $n^{1+1/c}$ coordinates. We also show a matching lower bound: for any $c > 1$, there exists a set of $n$ points in $\mathbb{R}^{d}$ such that any subset embedding for the set with approximation $c$ must have at least $n^{1+\Omega(1/c)}$ coordinates. Using our subset embeddings, we give data structures for approximate nearest neighbor in $\ell_\infty$ with space $O(n^2\log d)$, query time $\tilde{O}(n^{1+1/c})$, and approximation $O(c\log\log n)$ for any $c \geq 1$. Finally, we give another data structure for the approximate nearest neighbor under $\ell_\infty$ with the same space and query time as our subset embedding approach, but with approximation $O(c^{\log_2 3}) \approx O(c^{1.58})$. This allows us to achieve $O(1)$-approximation with query time e.g.~$n^{1.01}$

1 Introduction

Ultra-high-dimensional ANN in ℓ∞ requires query time independent of dimension, but existing approaches can be prohibitively costly there. The paper introduces subset embeddings and uses them to obtain ANN data structures with different approximation–query-time trade-offs.

1.1 Main Results

For any c < 3, randomized ℓ∞ ANN with success probability at least 0.5001 for every dataset and query requires query time Ω(d).The introduction also notes a 3-approximation with query time O(n^2) and no dependence on d.Source: §1.1 · p. 3
The reported performance specifies approximation O(c log log n), query time Õ(n^(1+1/c)), and storage space O(n^2 log d).A second structure offers O(1)-approximation with query time O(n^1.01), or O(log n)-approximation with query time Õ(n).Source: §1.1 · p. 3

1.3 Related Work

Subset embeddings select original coordinates to preserve dataset pairwise distances, unlike transforms that use the entire query or rely on distances in the original space.The paper contrasts this deterministic ℓ∞ feature selection with importance sampling for ℓp with small p [HNS+25].Source: §1.2 · p. 4, §1.3 · pp. 5–6

1.2 Technical Overview

For any n-point dataset and c ≥ 1, a subset embedding preserves pairwise ℓ∞ distances within distortion O(c) using n^(1+1/c) coordinates.For sufficiently large c and n, some datasets require n^(1+Ω(1/c)) coordinates for distortion at most c.Source: §1.2 · p. 4
The greedy embedding selects a coordinate witnessing a farthest pair not yet approximated; its witness graph has girth that bounds the number of selected coordinates.The proof connects the greedy order to a graph with few edges, yielding an embedding of size n^(1+O(1/c)).Source: §1.2 · p. 4

1.3 Related Work

The direct route of applying a high-dimensional ANN structure to the reduced embedding exceeds the target O(n^2 log d) space bound, so additional steps are needed.The paper also contrasts its approach with prior ℓp results that become inefficient for large p, with ℓ∞ query time Ω(nd).Source: §1 · p. 2, §1.3 · p. 5

2 Preliminaries

The preliminaries specify the computational and coordinate-access assumptions used by the data structures, define notation for restricted vectors, and state an existing ℓ∞ ANN benchmark.

The algorithms use the word-RAM model, assuming each coordinate x_i of an input point can be represented in O(1) words.Source: §2 · p. 6
Queries provide only coordinates from a stored list; access costs O(log k), simplified to O(log n) when k = O(n^2).Source: §2 · p. 6
The notation xS denotes vector x restricted to coordinate set S, with coordinates listed in increasing index order.Source: §2 · p. 6
The cited ℓ∞ ANN structure has approximation O(log log d), query time O(d polylog n), and storage O(n1.01d).Source: §2 · p. 6

3 Subset Embeddings

Subset embeddings preserve pairwise ℓ∞ distances by selecting original coordinates, supporting distance estimation without projecting onto new dense vectors. The section gives near-linear-size embeddings at larger distortion, a greedy construction and a graph-based lower bound.

3 Subset Embeddings

A β-approximate nearest neighbor under an α-distortion subset embedding yields an αβ-approximation in the original space.This connects pairwise-distance preservation on the dataset to ANN approximation for an arbitrary query.Source: §3 · p. 7

3.1 Results for ℓ∞Subset Embeddings

An isometric subset embedding needs at most n(n − 1)/2 coordinates, and some datasets require that many whenever distortion is below 2.The construction adds a coordinate realizing each pair's distance; the lower bound shows this dimension is tight for distortion c < 2.Source: §3.1 · pp. 7–8
For every n-point dataset and c ≥ 1, an ℓ∞ subset embedding with distortion O(c) uses n^(1+1/c) coordinates.Theorem 6 gives O(log n) distortion with O(n) coordinates and O(1) distortion with n^1.01 coordinates.Source: §3.1 · p. 8

3.2 Subset Embedding Construction

The greedy construction repeatedly selects a coordinate realizing the largest-distance pair still unresolved within the target distortion.Its witness graph has girth greater than α + 1; bounding the edges of such a graph bounds the number of selected coordinates.Source: §3.2 · pp. 8–11

3.3 Lower Bound

A constructed high-girth graph dataset requires every coordinate in its construction to preserve pairwise distances within factor c.The lower-bound argument builds vectors from graph distances after removing each edge, then shows omitting a coordinate violates the target distortion.Source: §3.3 · p. 12

4 ANN Data-Structure Constructions

The constructions use coordinate subsets and repeated candidate filtering to obtain ℓ∞ approximate-nearest-neighbor data structures with query time independent of d. They trade approximation and query time against space, with different guarantees from the two constructions.

4 ANN Data-Structure Constructions

A 3-approximate search within a candidate set S uses O(n^2 log d) space and O(|S|^2) query time.The structure stores, for each pair of dataset points, a coordinate witnessing their ℓ∞ distance.Source: §4 · p. 13

4.1 ANN from Subset Embeddings and Proving Theorem 2

Partitioning X into groups, querying each group’s subset embedding, and refining the resulting candidates avoids the naive approach’s excess space.The algorithm stores a subset embedding and an ANN structure for each group, then searches among the candidates.Source: §4.1 · p. 14
O(n^1+1/c) query time and O(n^2 log d) space yield an O(c log log n)-approximate neighbor.The construction partitions the dataset into groups and uses subset embeddings of distortion O(c).Source: §4.1 · pp. 14–15

4.2 Proof of Theorem 3

Repeatedly filtering groups with 3-approximate searches gives O(n^1+1/c log c) query time and 3 · c^log 3 approximation, using O(n^2 log d) space.The group-size exponent doubles at each step, and each step increases the approximation by a factor of 3.Source: §4.2 · pp. 15–16

A Proofs of Lower Bounds

The lower bounds show that achieving approximation below 3 in ultra-high-dimensional ℓ∞ requires query time linear in d. They also establish a general Ω(min{n, d}) query-time requirement for deterministic ANN with finite approximation.

A Proofs of Lower Bounds

A deterministic algorithm with query time o(d) can be forced to fail for c < 3 using two points that differ on an unqueried coordinate.The adversarial query changes that coordinate so the algorithm’s output is not a c-approximation.Source: A Proofs of Lower Bounds · p. 19
For some dataset and query distribution μ, any deterministic data structure answering at least a 0.5001 fraction of queries correctly must use Ω(d) query time, establishing the distributional deterministic lower bound.The optimizer-derived deterministic structure succeeds with probability at least 0.5001 over q~μ, and its query time lower-bounds Rr’s.Source: A Proofs of Lower Bounds · p. 19
For finite approximation, some datasets require deterministic query time Ω(min{n, d}); the same lower bound for randomized algorithms follows by Yao’s Minimax Principle.The deterministic construction uses standard basis vectors.Source: A Proofs of Lower Bounds · p. 20