Approximate Near Neighbors For General Symmetric Norms

Andoni Alexandr, Nguyen Huy L., Nikolov Aleksandar, Razenshteyn Ilya, Waingarten Erik. Arxiv 2016

[Paper]    
ARXIV

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}(loglogn)$-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

• Asymmetric Deep Supervised Hashing
• Locality-sensitive Hashing Scheme Based On P-stable Distributions
• On Symmetric And Asymmetric Lshs For Inner Product Search
• Clustering Hamming Embedding Generalized LSH And The Max Norm