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. 
 A: 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:


*

*Initialize a priority queue $P(q)$ where objects (points and R-tree
pages) are ordered by their minimum distance to $q$.

*Throw the root of the R-Tree in $P(q)$

*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$.
