Что такое параметр ε (epsilon) в локальном хешировании (LSH)?

Question

Я прочитал оригинальную статью о хешировании с учетом локальных особенностей.

Сложность зависит от параметра ε, но я не понимаю, что это такое.

Можете ли вы объяснить его значение, пожалуйста?

Answer 1

ε - параметр аппроксимации.

LSH (как FLANN & kd-GeRaF) предназначен для данных больших размеров. В этом пространстве k-NN не работает хорошо, фактически он почти такой же медленный, как грубая сила, из-за проклятия размерности.

По этой причине мы сосредоточены на решении приблизительного k-NN. Проверьте определение 1 из нашей статьи, в котором в основном говорится, что можно возвращать приблизительного соседа, лежащего на расстоянии (1 + ε), чем точный сосед.

Проверьте изображение ниже:

здесь вы видите, что значит найти точное / приблизительное NN. В традиционной проблеме NNS (Поиск ближайшего соседа) нас просят найти точную NN. В современной задаче, приближенной NNS, нас просят найти соседа в радиусе (1 + ε), таким образом, точный или приблизительный NN будет правильным ответом!

Таким образом, с высокой вероятностью LSH вернет NN внутри этого (1 + ε) радиуса. Для ε = 0 мы фактически решаем точную проблему NN.