Kosinusähnlichkeit LSH und zufällige Hyperebene

Question

Ich lese einige Lösungen über die nächste Nachbarsuche in High-Dimensionen mit zufälligen Hyperebene, aber ich bin immer noch verwirrt darüber, wie die Eimer arbeiten. Ich habe 100 Millionen Dokumente in Form von 100-dimensionalen Vektoren und 1 Million Abfragen. Für jede Abfrage muss ich den nächsten Nachbarn basierend auf der Kosinusähnlichkeit finden. Der Brute-Force-Ansatz besteht darin, den Wert der Abfrage mit allen 100 Millionen Dokumenten zu finden und diejenigen mit einem Wert nahe 1 auszuwählen. Ich kämpfe mit dem Konzept der zufälligen Hyperebenen, wo ich die Dokumente in Eimer legen kann, damit ich es nicht mache müssen cosine Wert 100 Millionen mal für jede Abfrage berechnen.

Answer 1

Denken Sie in einer geometrischen Weise. Stellen Sie sich Ihre Daten wie Punkte in einem hochdimensionalen Raum vor.

Erstellen Sie zufällige Hyperebenen (nur Ebenen in einer höheren Dimension), machen Sie die Reduktion mit Ihrer Phantasie.

Diese Hyper schneiden Ihre Daten (die Punkte), die Schaffung Partitionen, wo einige Punkte abgesehen von anderen positioniert ist (jeden Punkt in seiner Partition, wäre eine grobe Annäherung sein).

Nun sollten die Buckets entsprechend den durch die Hyperebenen gebildeten Partitionen bestückt werden. Daher enthält jeder Bucket viel weniger Punkte als die Gesamtgröße des Pointsets (weil jede Partition, über die ich schon gesprochen habe, weniger Punkte enthält als die Gesamtgröße Ihres Pointsets).

Als Konsequenz, wenn Sie eine Abfrage stellen, überprüfen Sie viel weniger Punkte (mit Hilfe der Eimer) als die Gesamtgröße. Das ist der ganze Vorteil hier, da das Überprüfen weniger Punkte bedeutet, dass Sie viel besser (schneller) als der Brute-Force-Ansatz machen, der alle Punkte überprüft.