<p><strong>ε is the approximation parameter</strong>.</p>

<p>LSH (as <a href="http://www.cs.ubc.ca/research/flann/" rel="nofollow noreferrer">FLANN</a> &amp; <a href="https://gsamaras.wordpress.com/projects/#geraf" rel="nofollow noreferrer">kd-GeRaF</a>) is designed for high dimensional data. In that space, <a href="https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm" rel="nofollow noreferrer">k-NN</a> doesn't work well, in fact it is almost as slow as brute force, because of the <a href="https://math.stackexchange.com/questions/346775/confusion-related-to-curse-of-dimensionality-in-k-nearest-neighbor">curse of dimensionality</a>.</p>

<p>For that reason, we focus on solving the <a href="https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor" rel="nofollow noreferrer"><strong>aproximate</strong> k-NN</a>. Check Definition 1 from our <a href="http://arxiv.org/pdf/1603.09596.pdf" rel="nofollow noreferrer">paper</a>, which basically say that it's OK to return an approximate neighbor lying in (1 + ε) further distance than the exact neighbor.</p>

<p>Check the image below:</p>

<p><a href="https://i.stack.imgur.com/YTYKH.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/YTYKH.jpg" alt="enter image description here"></a></p>

<p>here you see what does it mean finding the exact/approximate NN. In the traditional problem of NNS (Nearest Neighbor Search), we are asked to find the exact NN. In the modern problem, the approximate NNS, we are asked to find some neighbor inside the (1+ε) radius, thus either the exact or approximate NN would be a valid answer!</p>

<p>So, with a high probability, LSH will return a NN inside that (1+ε) radius. For ε = 0, we actually solve the exact NN problem.</p>
What is the ε (epsilon) parameter in Locality Sensitive Hashing (LSH)?
<p>I've read the <a href="http://www.cs.princeton.edu/courses/archive/spring13/cos598C/Gionis.pdf" rel="nofollow">original paper</a> about Locality Sensitive Hashing.</p>

<p>The complexity is in function of the parameter ε, but I don't understand what it is.</p>

<p>Can you explain its meaning please?</p>