Wyobraźmy sobie, że mamy przestrzeń euklidesową, dwuwymiarową - dzielimy ją losową linią prostą. Jeśli jakiś punkt w tej przestrzeni leży po lewej stronie prostej to dostaje kod 1, jeśli po prawej stronie to dostaje kod 0. Dzielimy przestrzeń drugą linią prostą - jeśli punkt leży po lewej do dostaje kod 1, jeśli po prawej do kod 0. Iterując w ten sposób dostajemy binarny kod o długości równej liczbie prostych które użyliśmy. LSH ma tę własciwość, że jeśli w oryginalnej przestrzeni dwa punkty leżą blisko siebie, to odległość hamming między ich wektorami będzie niska.
Właściwości
Istnieje teoretyczne twierdzenie, które mówi, że jeśli wzrasta długość hasha (czyli liczba podziałów przestrzeni) to odległość hamminga między dwoma wektorami binarnymi zbiega do odległości między tymi wektorami w oryginalnej przestrzeni. Źródło: Deep Supervised Hashing for Fast Image Retrieval
Implementacja
W Implementing LSH Functions in Tensorflow oraz Deep Learning of Binary Hash Codes for Fast Image Retrieval twierdzą, że jeśli pomnożyć wektor dense przez losowy W, b + sigmoid to to będzie prosta i szybka implementacja LSH.