餘弦相似性LSH和隨機超平面

Question

我使用隨機超平面讀取了有關最近鄰居搜索的幾個解決方案，但我仍然對這個桶如何工作感到困惑。我有100百萬個文件，形式爲100維向量和100萬個查詢。對於每個查詢，我需要根據餘弦相似性找到最近的鄰居。蠻力的方法是找到cosine查詢的全部1億個文檔的值，並選擇值接近1的那些。我正在努力使用隨機超平面的概念，在那裏我可以把文檔放在桶中，這樣我就不會必須爲每個查詢計算cosine值1億次。

Answer 1

以幾何方式思考。想象你的數據像高維空間中的點。

創建隨機超平面（更高維度的飛機），使用您的想象力做減少。

這些超平面削減您的數據（點），創建分區，在一些點正在從別人離開的位置（在分區的每一個點，將是一個粗略的估計）。

現在桶應該根據超平面形成的分區進行填充。因此，每個存儲桶包含的點數比點集的總大小要少得多（因爲之前討論的每個分區都包含的點數少於您的點集的總大小）。因此，當你提出一個查詢時，你檢查比總的大小少得多的點（在桶的協助下）。這就是所有的收穫，因爲檢查更少的點數，意味着你比暴力方法更好（更快），它會檢查所有點。