什麼是最近鄰的快速近似？

Question

假設我有一個巨大的（幾百萬）n個向量的列表，給定一個新的向量，我需要找到一個非常接近的集合，但它不需要是最接近的。 （最近鄰居發現最近並且運行n次）

哪些算法能夠以精度爲代價非常快地近似最近鄰居？

編輯：既然它可能會有所幫助，我應該提及的數據大多數時間都很順利，隨機維度中出現尖刺的可能性很小。

Answer 1

有存在更快algoritms然後爲O（n ）通過任意距離搜索最接近的元素。詳情請查詢http://en.wikipedia.org/wiki/Kd-tree。

Answer 2

的 「近鄰」 LSH庫在網上搜索發現 http://www.mit.edu/~andoni/LSH/ http://www.cs.umd.edu/~mount/ANN/ http://msl.cs.uiuc.edu/~yershova/MPNN/MPNN.htm

Answer 3

如果您正在使用高維向量，如SIFT或SURF或多媒體領域中使用的任何描述符，我建議您考慮LSH。

Wei Dong的博士論文（http://www.cs.princeton.edu/cass/papers/cikm08.pdf）可能會幫助您找到更新的KNN搜索算法，即LSH。與更傳統的LSH不同，比如早先由MIT研究人員發佈的E2LSH（http://www.mit.edu/~andoni/LSH/），他的算法使用多次探測來更好地平衡召回率和成本之間的權衡。

Answer 4

對於近似最近鄰居，最快的方法是使用局部敏感散列（LSH）。 LSH有許多變種。您應該根據數據的距離度量選擇一個。 LSH查詢時間的大O與數據集大小無關（不考慮輸出結果的時間）。所以它非常快。這LSH library實現L2（歐幾里得）空間的各種LSH。

現在，如果您的數據的維度小於10，那麼如果您想要精確的結果，則首選kd tree。