近似最近邻问题相关算法总结

http://blog.csdn.net/guoyilin/article/details/39668183

2014

当数据个数比较大的时候，线性搜索寻找KNN的时间开销太大，而且需要读取所有的数据在内存中，这是不现实的。因此，实际工程上，使用近似最近邻也就是ANN问题。

这里总结下常见的使用方法和相关的论文。每个方法都会有自己的优点。

第一, Tree-Based Method， 筛选候选子集。

1. Vantage-Point Tree

    Paper: http://www.pnylab.com/pny/papers/vptree/vptree/

    算法的代码和说明：http://stevehanov.ca/blog/index.php?id=130

    实际使用VP tree中可能回溯会比较多，特别是nearest neighbor's distance is not very small compare with farthest distance in all data.

2. K-d Tree

    kd tree 适用于维度比较低的情况，因为在维度高的情况下，kdtree的深度将会非常深，这样的tree的效率太低， 存储空间也大。

3. Randomized K-d tree

    见lowe 的 FLANN算法，http://www.cs.ubc.ca/research/flann/， 思想大概是用forest的思想来提升kdtree的recall

4. Random Projection Tree

    采用随机投影方法将每个节点中的数据投影到一维子空间，在子空间中进行划分。该方法实践中效果比较好。算法性能比较优秀。

    paper： Large-scale music similarity search with spatial trees

    实验发现投影方向的选择可以限制在-1, 0,1之间，在保证效果的情况下，进一步缩小投影方向的存储空间。

第二，lsh方法

根据使用的距离度量方法，选择合适的lsh。 要注意在保证recall的情况下，该算法可能几乎是线性搜索。

第三，Product Quantization

see paper: Product quantization for nearest neighbor search.

方法比较巧妙，后续有不少论文，主要思想是在子空间中进行k-means，这样划分的空间比较密集，利用k-means中心点能够对数据进行较好的近似，能够有效压缩数据。缺点是query的的时候，需要和每个数据进行比较。 当然论文提出可以先筛选初步的子集，在子集中使用该方法。实验效果比较该算法性能还不错。

可能还有更多的方法谈论该问题。后续补上。