Approximate Near Neighbors for General Symmetric Norms
This work addresses the challenge of efficient nearest neighbor search in high-dimensional spaces for symmetric norms, which is incremental as it extends existing methods to a broader class of norms.
The paper tackles the problem of nearest neighbor search for general symmetric norms by developing a data structure that achieves doubly-logarithmic approximation with efficient query time and space, specifically poly(log log n)-approximation, n^{o(1)} query time, and n^{1+o(1)} space for n-point datasets in d = n^{o(1)} dimensions. It also demonstrates that these techniques are not applicable to general norms.
We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every $n$, $d = n^{o(1)}$, and every $d$-dimensional symmetric norm $\|\cdot\|$, there exists a data structure for $\mathrm{poly}(\log \log n)$-approximate nearest neighbor search over $\|\cdot\|$ for $n$-point datasets achieving $n^{o(1)}$ query time and $n^{1+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.