# Approximate Near Neighbors for General Symmetric Norms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2016.

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

- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Statistical-Computational Trade-offs for Density Estimation](https://mlsanity.com/paper/2410.23087/) (2024)

## Abstract (arXiv)

We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every n, d = no(1), and every d-dimensional symmetric norm |·|, there exists a data structure for poly(log log n)-approximate nearest neighbor search over |·| for n-point datasets achieving no(1) query time and n1+o(1) space. The main technical ingredient of the algorithm is a low-distortion embedding of a symmetric norm into a low-dimensional iterated product of top-k norms. We also show that our techniques cannot be extended to general norms.