Minihash && LSH

有空補自己的了解和思考

LSH

參考文獻

https://blog.csdn.net/icvpr/article/details/12342159

下面為摘抄

LSH的基本思想是：将原始資料空間中的兩個相鄰資料點通過相同的映射或投影變換（projection）後，這兩個資料點在新的資料空間中仍然相鄰的機率很大，而不相鄰的資料點被映射到同一個桶的機率很小。也就是說，如果我們對原始資料進行一些hash映射後，我們希望原先相鄰的兩個資料能夠被hash到相同的桶内，具有相同的桶号。對原始資料集合中所有的資料都進行hash映射後，我們就得到了一個hash table，這些原始資料集被分散到了hash table的桶内，每個桶會落入一些原始資料，屬于同一個桶内的資料就有很大可能是相鄰的，當然也存在不相鄰的資料被hash到了同一個桶内。是以，如果我們能夠找到這樣一些hash functions，使得經過它們的哈希映射變換後，原始空間中相鄰的資料落入相同的桶内的話，那麼我們在該資料集合中進行近鄰查找就變得容易了，我們隻需要将查詢資料進行哈希映射得到其桶号，然後取出該桶号對應桶内的所有資料，再進行線性比對即可查找到與查詢資料相鄰的資料。換句話說，我們通過hash function映射變換操作，将原始資料集合分成了多個子集合，而每個子集合中的資料間是相鄰的且該子集合中的元素個數較小，是以将一個在超大集合内查找相鄰元素的問題轉化為了在一個很小的集合内查找相鄰元素的問題，顯然計算量下降了很多。

其他參考文獻

https://www.jianshu.com/p/535c537a5766