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 = n(o(1)), and every d-dimensional symmetric norm parallel to . parallel to, there exists a data structure for poly(log logn)-approximate nearest neighbor search over parallel to . parallel to 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.