How to find the next nearest neighbor in a given direction Imagine a data set with three features $A, B, C$.
A nearest neighbor algorithm can find what array $[a,b,c]$ is most similar (in terms of a given metric, e.g. euclidean distance) to $[x,y,z]$.
What method can be used to find the most similar array, given the requirement that one of the features is changed in a given direction, e.g. $[x, y+\epsilon, z]$. The original array $[x,y,z]$ is not allowed to be returned again.
The simplest way I can think of would be to perform nearest neighbor searches with increasing $\epsilon$ until a new array is found. However, this would be computationally expensive. What is a better method?
 A: Let's consider $Q=(x,y,z)$ to be your query point and $P_i=(a_i,b_i,c_i)$ are all possible neighbors for $i=1,\dots n$.
For the first call, it is clear that you had to calculate the distance for all possible neighbors $d_i=||Q-P_i ||$.
If you change the $Q'\gets Q + \Delta$ where $\Delta=(0,\epsilon,0)$ or any other vector.
Then, we can analyze
$$
d_i' = ||Q+\Delta - P_i||
$$
We can inspect the bounds as follows:
$$
d_i'\in [d_i-||\Delta||, d_i+||\Delta||]
$$
considering that in best case, $\Delta$ is towards $P_i$, and that in the worst case $\Delta$ goes directly from $P_i$.
Using this, you can calculate the upper bound for $$\min_i d_i'\leq \min_i (d_i+||\Delta||)$$ Note that:
$$
\min_i (d_i+||\Delta||) = ||\Delta|| + \min_i d_i
$$
where $\min_i d_i$ is the distance to the nearest neighbor in the previous step.
Having this bound, you can filter only those indices that have a chance to outperform it, i.e.
$$
\left\{i':d_{i'}-||\Delta||\leq ||\Delta|| + \min_i d_i\right\}
$$
If you have sorted the nearest neighbors in the first step, your list of candidates will be on the top.
Among these indices, you can find the new nearest neighbor.
