4
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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"? $\endgroup$
    – jmlarson
    Commented Nov 9, 2017 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.