近似最近邻搜索ANN(Approximate Nearest Neighbor)
目前ANN近似近邻搜索有两种比较流行的方法：树方法和哈希方法。
特点概括
基于树的方法的一些特点概括：
递归了划分数据：分而治之。Recursively partition the data: Divide and Conquer。
查询时间为：\( O(log n) \)(with constants exponential in dimension)
随着数据维数的增加，基于树的ANN其表现性能会急剧的下降，Performance degrades with high-dimensional data。
需要的存储开销很大，Large storage needs，因为需要存储树结构(?)。
在运行的时候，需要保存原始数据，Original data is required at run-time。同样会增加内存的开销。
哈希方法的一些特点：
数据库中的每一个item都被用一个编码来表达。Each item in database represented as a code。
可以极大的降低内存空间。Significant reduction in storage。
查询时间为：\( O(1) \)或是线性的。Expected query time: O(1) or sublinear in n。
4.Compact codes preferred。
Precision-Recall权衡
如果想要得到较高的精度，则需要较长的编码。For high precision, longer codes (i.e. large \( m \)) preferred。
编码长度m增长的话，则item碰撞的概率会成倍的减小，从而导致召回率下降。 Large m reduces the probability of collision exponentially → low recall
为了得到较高的召回率，则需要多个哈希表。Many tables (large L) necessary to get good recall → Large storage
总结
以上是生活随笔为你收集整理的近似最近邻搜索ANN(Approximate Nearest Neighbor)的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： Ubuntu下git使用教程
- 下一篇： 有趣、好玩、有料的网站收藏