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 or read more about core development to add your support to a road-map item.
Other Roadmap Items
Indexed Nearest Neighbor Searches
Currently nearest-neighbor searching is carried out with ad hoc tricks that expand a search radius until a candidate set is generated, then finding the closest value in the candidate set. A directly indexed approach would be optimally fast.
The ISO SQL/MM model includes an extension for a topological coverage: a geometry model in which nodes and edges are the basic building blocks and area covers are built up from those primitives. This allows very fast tests for adjacency and geometry unions, as well as editing and simplifying shared lines.
The support for dimensions higher than X/Y is uneven as currently implemented. Most operations support clean handling of the Z dimension (but a few do not). A reasonable number of important functions do not support handling of the M dimension. This item would fix functions not handling higher dimensions.