Approximate near neighbors for general symmetric norms
Alexandr Andoni, Huy Lê Nguyễn, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten · 2017
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 (loglogn)-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.