A dive into #spatial_search_algorithms – Vladimir Agafonkin
▻https://medium.com/@agafonkin/a-dive-into-spatial-search-algorithms-ebd0c5e39d2a
Spatial indices are a family of algorithms that arrange geometric data for efficient search. Spatial data has two fundamental query types: nearest neighbors and range queries. Both serve as a building block for many geometric and #GIS problems.
K nearest neighbors
R-tree
https://cdn-images-1.medium.com/max/800/1*DkXjkWxMkT41Tupa8SUMCQ.png https://cdn-images-1.medium.com/max/800/1*kJBBppwt8vrLjQ0zqoMg9g.png https://cdn-images-1.medium.com/max/800/1*HGrNIlYjee5z6uhOX53zzQ.png https://cdn-images-1.medium.com/max/800/1*hJj3HZmiKXiXkK12ha26Rw.png
K-d tree
K nearest neighbors (kNN) queries
https://cdn-images-1.medium.com/max/800/1*UzBafKxaJzsgvqg8MZd0Tg.png https://cdn-images-1.medium.com/max/800/1*-gWKwkPTQqmItVSihxDriQ.png https://cdn-images-1.medium.com/max/800/1*PPecx9vIJY-XgIqbON7UkA.png
Custom kNN distance metrics
https://cdn-images-1.medium.com/max/800/1*Qr7YzmZ_P15IJ8BFcDRN2Q.png https://cdn-images-1.medium.com/max/800/1*eWhMCp7HFyBVbIGpKMjikQ.png
In future articles in the series, I’ll cover extending the kNN algorithm to geographic objects, and go into detail on tree packing algorithms (how to sort points into “boxes” optimally).