Given millions of GPS points located in the same area. What would be the least cost method to extract all the neighboring points of each entry in the dataset ( i.e. all the points that are within a given range of another one) ?
It is to be noted that this process will only be done once for the entire dataset.
The size of the distance matrix would grow quadratically, not exponentially, but there's no need for it. The idea with a surrounding box sounds reasonable. Since the boxes might turn out to be sparingly occupied, I'd use a hashtable with the concatenated coordinates as keys.
Maybe you can exploit knowledge about particular cell base stations, only distances are of interest whose base stations are nearby,
Regards,
Joachim
Dear Amira Benlecheb
Differential correction is a frequent method of error correction. Remember the core idea behind the need for three satellites to reliably determine two-dimensional locations. Differential correction is similar in that it improves GPS readings by using known distances between two or more sensors.
Kind Regards
Qamar Ul Islam
I'd try using kd-tree (https://en.wikipedia.org/wiki/K-d_tree) .
I have successfully used kd-tree in the past to create a data structure capable of handling millions of 3D points from a LiDAR scan. There are also some libraries that can help you implement it:
1. https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html it's not optimal in terms of performance but can handle millions of points
2.https://github.com/storpipfugl/pykdtree#:~:text=pykdtree%20is%20a%20kd%2Dtree,spatial. Haven't tried this one but it looks promissing.
I am sure there are also similar libraries for C++ / R implementation.
Good luck!
https://gis.stackexchange.com/questions/418689/fastest-way-to-extract-the-neighbours-of-a-gps-point-among-millions-of-other-poi
- Badges
- Science topic