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?

• If you imagine a 2D example, are you asking what would be closest if you move a new point up one axis? In which case doesn't the value of $ϵ$ determine which is the nearest neighbor? Commented Oct 24, 2017 at 9:09
• In a 2D example, I would like to find my nearest neighbor as I travel along one axis. Reduce my example to two features, $[A,B]$. I would like to find the point that keeps $A$ as constant as the data in the dataset allows, but with a higher or lower value for B. Commented Oct 24, 2017 at 9:15
• So the nearest neighbor given that your point can move along the WHOLE axis? In that case why not just exclude the feature you want to adjust and do NN with the remaining feature? Commented Oct 24, 2017 at 9:17
• Search along the axis until the first (nearest) occurence is found. Commented Oct 24, 2017 at 9:24

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.

• Do I understand you correctly, that this approach filters the data, and that once that step is performed, a common nearest neighbor search is to be applied? Commented Oct 24, 2017 at 11:19
• Yes, that's the case. Commented Oct 24, 2017 at 12:07