OfflineReverseGeocode

https://github.com/AReallyGoodName/OfflineReverseGeocode has been ported to many languages and was popular as an example. Turns out it was posted by others here not myself but I don’t think thats a big deal.

A kd-tree is the generalized data structure that can do log(n) lookups of nearest in any dimensions. I wrote an implementation for nearest to a geographical point years ago (since ported to many other languages): https://github.com/AReallyGoodName/OfflineReverseGeocode A less generalized solution is to grid things up (quad tree and oct trees) as you implied above but the kd-tree is the generalized solution without edge cases (what if the majority of points of interest end up in a single grid square in your example?). A kd-tree is essentially what a sort list is for one dimensional data but instead supports multiple dimensions.

I did the same years ago. We were providing realtime suburb data for a fleet of trains. Each train received a GPS coordinate once per minute, we took this and displayed the suburb. So 1440 updates per day per train. For the fleet it was going to be over $100 a day in API costs. We were going to not display suburb data because of cost. In the end I found a creative commons placename database (geonames.org). For placenames with >500 people it's ~10MB of data and that covers the entire planet (surprisingly small). I then wrote a KD-Tree based library to look it up the nearest point in this table extremely efficiently (log(N) time). I'll admit i haven't updated or maintained it. The server running it has been chugging along well though >5years later. https://github.com/AReallyGoodName/OfflineReverseGeocode

Read the wiki page on it, run through the psuedocode on pen and paper a few times and then implement it. Source: I did this when I wrote a library for reverse geocoding which uses a kd tree. https://github.com/AReallyGoodName/OfflineReverseGeocode

Online geocoding service are always the worst way to go. You only use the online services if you don't have an alternative dataset. The osm datasets actually aren't that big, the entire PBF formatted dataset is <30GB. You can fit that on any system (not in RAM of course but hard disk access is still a million times quicker than using an online service). There are simple scripts to keep the dataset in sync on your server. Also it's just completely fucking ridiculous to send a request over the internet to perform a calculation. I encountered the issue myself ages ago where i had a task to reverse geocode for a railways GPS system for every train every minute. Google and other services would have costed millions of dollars every year, used massive amounts of bandwidth and been waaay too slow. I wrote a library - https://github.com/AReallyGoo