近似最近邻搜索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使用教程
- 下一篇： 有趣、好玩、有料的网站收藏