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:
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.
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
The PostGIS spatial index currently works exclusively in the X/Y plane. For data such as fleet tracking the “Z” or “time” dimension can serve as a useful query restriction. Higher dimensional indexes are needed.
Business Intelligence Utilities
Functions to aggregate collections of records in useful ways for reporting, such as heat maps, influence polygons and clustering.
Geometry matching function in PostGIS are currently biased toward exact matches. However, spatial data is often “logically equivalent but physically disjoint” – the machine representations are close but not exact even though the geometries represent the same features.