一般对称范数的近似最近邻

Nov, 2016

Approximate Near Neighbors for General Symmetric Norms

Alexandr Andoni, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten

TL;DR每个对称赋范空间都可以采用双对数逼近的方式建立有效的最近邻搜索数据结构。我们的算法的主要技术是一个对称范数到低维度“top-k”范数的迭代乘积的低扭曲嵌入。同时，我们证明这些方法无法推广到一般范数。

Abstract

We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation