Question about the "epsilon" parameter in the query function. about pynndescent HOT 2 CLOSED

Imagine you are searching for neighbors and you come across item $a$ which has a distance of $1.1$. In your current set of neighbors the furthest distance is currently $1.0$, so $a$ can't be in the nearest neighbor list.

But what if $a$ had a neighbor $b$ whose distance to you was only $0.9$? That is in your nearest neighbor list. But if you had already discarded $a$ for being too far away you would never get round to checking any of its neighbors so you could very easily miss $b$ (you would need it to be in the neighbor list of another item that you did check).

What $\varepsilon > 0$ does is allow for situations like the above where you explore the neighbors of $a$ as long as its distance is not much bigger than your current neighbors. The definition of "bigger" gets more generous as you increase $\varepsilon$.

But you don't want to set $\varepsilon$ too high: this means you end up searching everything which is exceptionally wasteful (and hence slow). Imagine an item $c$ which has a distance to you of $10000$: it would be very unlikely that $c$ had any neighbors that were worth searching so you really would want to avoid looking at its neighbors without any regrets.

Hope this helps.

from pynndescent.

Thank you!

from pynndescent.