Approximate Nearest Neighbor in Ultra-High Dimensional ${\ell }_{\infty }$

Abstract

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+\epsilon )$-approximation data structures with space $\tilde{O}(n\log d/\text{poly}(\epsilon ))$ and query time $\tilde{O}(n/\text{poly}(\epsilon ))$. 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\ge 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}$