Was ist der ε (Epsilon) Parameter im Locality Sensitive Hashing (LSH)?

Question

Ich habe die original paper über Locality Sensitive Hashing gelesen.

Die Komplexität ist in Funktion des Parameters ε, aber ich verstehe nicht, was es ist.

Können Sie bitte seine Bedeutung erklären?

Answer 1

ε ist der Näherungsparameter.

LSH (wie FLANN & kd-GeRaF) ist für hohe dimensionale Daten ausgelegt. In diesem Raum funktioniert k-NN nicht gut, in der Tat ist es fast so langsam wie rohe Gewalt, wegen der curse of dimensionality.

Aus diesem Grund konzentrieren wir uns auf die Lösung aproximate k-NN. Prüfe Definition 1 aus unserer paper, die grundsätzlich besagt, dass es in Ordnung ist, einen ungefähren Nachbarn, der in (1 + ε) liegt, um eine weitere Entfernung zurückzugeben, als der genaue Nachbar.

Überprüfen Sie das Bild unten:

hier sehen Sie, was es bedeutet, die genaue/ungefähre NN zu finden. Im traditionellen Problem der NNS (Nearest Neighbour Search) werden wir nach dem genauen NN gefragt. Im modernen Problem, dem Näherungs-NNS, werden wir gebeten, einen Nachbarn innerhalb des (1 + ε) Radius zu finden, daher wäre entweder das exakte oder das ungefähre NN eine gültige Antwort!

Also, mit einer hohen Wahrscheinlichkeit, LSH wird eine NN innerhalb dieser (1 + ε) Radius zurückgeben. Für ε = 0 lösen wir tatsächlich das exakte NN-Problem.