最近邻查找最优算法_MIT-高维近似近邻（ANN）的接近最优化算法

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

作者是MIT的Alexandr Andoni 和Piotr Indyk。2008年的一篇很经典的文章....citation高达2510。

从NN到ANN

Nearest Neighbor （NN）近邻问题的定义：给定n点集合，搞个数据结构，当给定一个query时，返回最接近query的数据。

对于NN，一般的解法如下：

• 1~2维：Voronoi diagrams
• 10维：kd trees, metric trees, ball-trees, spill trees
• 更高维：近似最近邻查找Approximate Nearest Neighbor (ANN)，矢量量化方法等。

高维的NN会有维度灾难，所以有人提出了Approximate Nearest Neighbor (ANN)。ANN已经挺准啦，而且知道了ANN就可以算NN，先用ANN找出所有近似近邻，然后选择最靠近的作为NN的解）。ANN的时间复杂度是sub-linear的，不过空间复杂度还是挺高的。

从ANN到LSH

局部敏感的哈希算法locality-sensitive hashing