# Nearest neighbor with lower value

I have a collection of p points in n-space, and a p-vector of scalar values corresponding to each point. In this example, p is much larger than n.

Is it possible to build an R-tree (or some other data structure) in order to quickly find the nearest neighbor with a smaller value?

Importantly, is it possible to build such a structure so that it can easily be updated with additional points and values?

A couple of possibilities:

• Compute all pairwise distances for the initial set of points, and store (for each point) the index/distance to the closest, better point. As new points arrive, find the distance from these points to all existing points. This allows one to update the index/distance old points (and store the closest, better point for the new points as well).
• Building an R-tree and querying the k nearest neighbors and hope one has a smaller function value. Otherwise, increase k.

Both approaches waste effort.

I've looked into http://libspatialindex.github.io/ and http://scikit-learn.org/stable/ and I haven't seen an appropriate data structure.

• What $p$-vector in your description means? Commented Nov 20, 2017 at 17:09
• I meant there is a scalar associated with each of the p points. Commented Nov 21, 2017 at 2:33

I hope I understand you right: You have $p$ $n$-dimensional points $m_i$, each with a scalar value $v_{m_i}$ attached to it. When a query $q$ comes in you want to find the nearest neighbor $m_i$ to $q$ where $v_{m_i} < v_q$.

I guess the most efficient way would be to use distance browsing (aka best-first-search). With distance browsing you can iteratively retrieve the points $m_i$ in ascending distance to $q$ until you decide to stop (in your case when $v_{m_i} < v_q$). As you retrieve more points only the necessary pages of the R-Tree are resolved.

With most of the existing R-Tree implementations you have to implement it yourself. The basic idea works as follows:

1. Initialize a priority queue $P(q)$ where objects (points and R-tree pages) are ordered by their minimum distance to $q$.
2. Throw the root of the R-Tree in $P(q)$
3. Repeat: retrieve the first entry from $P(q)$.
• if its a page, resolve it and put all children in $P(q)$
• if its a point, check if $v_{m_i} < v_q$ (if yes, you are done)

Update 1

I see, it seems additionally to finding the nearest neighbor to an incoming query, you want to maintain the nearest neighbor $nn(m_i)$ for each point $m_i$, correct?

This part will be a bit more tricky, since you will have to alter the R-Tree. I think the most efficient way would be to store triplets $\langle m_i, nn(m_i), \mathrm{dist}(m_i, nn(m_i))\rangle$ in the R-Tree with $m_i$ being used as spatial key (so only $m_i$ is used to build the R-Tree). Additionally, you will have to alter the R-Tree such that an entry $e$ not only carries information about its bounding box, but also the largest dist_max(e) from any of its children. Now, when a new query $q$ comes in, you want to find all $m_i$ which have $q$ as their nearest neighbor with lower distance. So basically you want to find all $m_i$ that have $q$ in their $\mathrm{dist}(m_i, nn(m_i))$ range and then only update those where $v_q < v_{m_i}$. Again this can be done by distance browsing, resolving entries $e$ where mindist(e, q) < dist_max(e). After this step is done, and you include $q$ in you database, you will have to update the dist_max(e) from all pages that $q$ lies in.

Sorry, this might be a bit confusing, and is really hard to explain without a whiteboard or a 5 page long explanation. I hope the basic idea becomes clear. This is a rather efficient approach, but you should be really sure, that you need the efficiency before going this route.

Update 2

As a priority queue you can use the basic implementation from the programming language of your choice. For example in Java

PriorityQueue(int initialCapacity, Comparator< ? super E > comparator)

The comparator has to be defined such that entries in the queue are ordered according to their mindist to $q$.

• Yes, you understand correctly. How does the minimum distance get updated as new points appear? Can you spell out what is required when "initializing a priority queue"?
– jmlarson
Commented Nov 9, 2017 at 19:08