Indexed Nearest Neighbor Searches
Indexed Nearest Neighbor Searches Summary
Finding the nearest object in a set is a common operation for spatial joins. Currently, solutions to this problem involve a sub-query function that guesses at a bounding box size that might contain some candidate features, then reduces the candidate set to the nearest single feature. If the box is too small, no features are found, and the process is started again with a larger box.
It is possible to find the nearest neighbor directly by traversing the R-Tree index of a set, and since PostGIS uses an R-Tree index, this approach is directly applicable. There are papers explaining the process:
- http://citeseer.ist.psu.edu/roussopoulos95nearest.html
- http://citeseer.ist.psu.edu/91356.html
The maintainers of the PostgreSQL GiST infrastructure have proposed modifying the GiST structure to support this kind of tree-traversal directly in the index API (See “Change GiST interface to support tree traversing” here). This work would be put into place prior to implementing the nearest-neighbor functionality in PostGIS.
Funding
This roadmap item is currently unfunded.
Add your support for this item by contacting us for a quote and discussion of the particular features you need.
Get a quote now!
Get a quote on road-map development and add your support to a road-map item.
Other Roadmap Items
The LRS functions in PostGIS are a mismatched combination of functions that operate on measures and functions that use length as a proxy to measure. A re-work to formalize the LRS handling is needed.
A POINTPATCH type, and associated index and functions, for handling the management of multi-terrabyte collections of LIDAR point data.
The geodetic GEOGRAPHY operations are currently very CPU intensive, because they involved multiple trancendental math calls. Performance could be improved through caching of calculations, both at a low level (coordinates) and a high level (data structures).