Approximate Near Neighbors for General Symmetric 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 = 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.