Approximate Near Neighbors For General Symmetric Norms
Andoni Alexandr, Nguyen Huy L., Nikolov Aleksandar, Razenshteyn Ilya, Waingarten Erik. Arxiv 2016
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.
Similar Work