Stream / generate nearest neighbors

[dfuhry]

I am storing polygons / linestrings and I would like to stream (generate) nearest neighbors. This requires first iterating through nearest bounding boxes in order, with true-distance comparisons between the geometries they contain, and at some point cutting off that search.

Right now with the nearest() method I can get a fixed number of nearest neighbor bounding boxes to my query bounding box via the method's second parameter:

https://rtree.readthedocs.io/en/latest/tutorial.html#nearest-neighbors

But I cannot stream bounding boxes out with a generator. If I pass the length of the dataset as the second parameter then I can iterate through that list, but this is very slow for large datasets because it returns all boxes in the dataset sorted by distance, whereas in practice I likely need only the first few. (However the exact number I need depends on exact distance checks between the contained geometries, so I don't exactly know it beforehand.)

I'm not sure whether the inability to generate / yield a list of nearest-neighbor bounding boxes is a libspatialindex limitation, or only one of this library.

[hobu]

I think this is just an Rtree limitation and could be implemented.

[dfuhry]

Thank you for the insight. Any idea how?

I see that Index.nearest() passes the num_results value as an input parameter to libspatialindex's Index_NearestNeighbors_id().

That method here:

https://github.com/libspatialindex/libspatialindex/blob/main/src/capi/sidx_api.cc#L1607

passes it to RTree::nearestNeighborQuery():

https://github.com/libspatialindex/libspatialindex/blob/main/src/rtree/RTree.cc#L575

which finally does the work of iterating through the data structure with a priority queue and accumulating results until count >= k. (That is, until the number of found closest tree items count reaches the requested number k, which is the num_results we passed in originally.)

It seems to me we might need to either call some similar libspatialindex method to nearestNeighborQuery() which could iterate results rather than returning a fixed number (which I don't immediately see), or basically reimplement nearestNeighborQuery() in python-rtree, i.e. by using a priority queue to pass through the nodes of the tree, starting at the root, and yielding nodes in order of distance to the query object. I'm not sure whether you see any easier way.

[FreddieWitherden]

We could add an API to allow iteration although it would requite quite a bit of new infrastructure on the libspatialindex side of things. The state for an NN query would need to be moved out into its own object so it can be persisted between API calls.

With that said, if you typically only need a handful you're probably better off asking for the mean + one standard deviation count. This should be low overhead (just one API call) and may well be sufficient most of the time. If that fails go and ask for twice as many, and so on and so forth.

Regards, Freddie.