I have a data set of about 20 million coordinates. I want to be able to pass in a latitude, longitude, and distance in miles and return all coordinates that are within the mile range of my given coordinates. I need the response time to ideally be sub 50ms.
I have tried loading all coordinates in memory in a golang service which, on every request, will loop through the data and using haversine filter all coordinates which are within the given miles distance of my given coordinate.
This method sees the results return in around 2 seconds. What approach would be good to increase the speed of the results? I am open to any suggestions.
I am toying around with the idea of grouping all coordinates by degree and only filtering by the nearest to the given coordinates. Haven't had any luck improving the response times yet though. My data set is only a test one too as the real data could potentially be in the hundreds of millions.
Idea would be to have a "grid" that partitions coordinates, so that when you do need to do a lookup you can safely return all coordinates in particular cell, do not return any from the cells too far away from target, and only do per coordinate comparison for coordinates that are in the cells that contains some coordinates within distance and some outside the distance.
Simplified to 1D:
Coordinates are from 1 to 100
you partition into 5 blocks of 20
When somebody looks for all coordinates within distance 25 from 47 you return all coordinates in blocks [30,39], [40,49],[50,59],[60,69] and then after doing per coordinate analysis for blocks [20,29] and [70,79] you additionally return 22,23,24,25,26,27,28,29, 70,71,72.
Unfortunately I have no realistic way to estimate speedup of this approach so you would need to implement it and benchmark it by yourself.
I think that this is more of a data structure problem. One good way to store large sets of geospatial coordinates is with an R-tree. It provides logn M search. I have limited knowledge of Go, but I have used an R-Tree to great effect for similarly sized datasets in a similar use case in a JS application. From a quick search it appears as though there are at least a couple Go R-Tree implementations out there.
MongoDB has various geographic searches $geoNear will allow you to search for points within a specific distance from a point or within a shape.
https://docs.mongodb.com/manual/reference/operator/aggregation/geoNear/
PostGIS for Postgres has something similar, but I am not too familiar with it.