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

当数据个数比较大的时候，线性搜索寻找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

    实验发现投影方向的选择可以