I have a scenario, where I have x million longitude latitude points.
When a new long/lat point is added I want to know efficiently which other points are within a user configured distance parameter, so I can add them to a list.
got anything better than bounding boxes?
I would love to see algorithms, references and a few implementations ;) thank you kindly!
There are quite a few options that are better, mostly based around space partitioning.
A common, and often very good option (which isn t too tough to implement) is to use a KD-Tree. Quadtrees are easier to implement, but slower for searching. Depending on the distribution of your data, and your requirements, other space partitioning algorithms may perform better, have lower memory requirements, or other issues that are related.
A colleague told me that he had good experience with using Morton-Code as a spatial index on GIS data, maybe that is something worth investigating.
This quick-and-dirty approach may save you some grief: Divide the surface of the earth into 1 degree boxes. You will then have a 180x360 element array and you will only need to search a small number of boxes, including the box containing the new point and all the boxes immediately around it for which one of the corners is within the user-specified distance. You will find that there are some tricks you can use to quickly figure out what boxes to use without considering them all. Just don t forget latitude and longitude wrap-around.
If your "only" have millions of points, and they aren t clustered into hot-spots, that might get you through.
A theoretically superior way: You could map each point into three dimensional space and then store them in an octree, which would let you quickly find nearby points to within an arbitrary distance. Of course, the distance in three-dimensional space will be slightly different than the great-circle distance on the globe, so you will have to calculate a conversion factor. That should be simple, though. You don t mention an implementation language, but there is almost certainly going to be a well-tested octree implementation for any language you are working in. If you don t mind inserting the third-party code, this solution is the way to go.
If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.: algorithm A: O(n) algorithm B: O(log(n)) algorithm C: O(n log(n)) How do ...
I m using Electro in Lua for some 3D simulations, and I m running in to something of a mathematical/algorithmic/physics snag. I m trying to figure out how I would find the "spin" of a sphere of a ...
There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7. There s some documentation and a tiny Wikipedia ...
As a learning experience I recently tried implementing Quicksort with 3 way partitioning in C#. Apart from needing to add an extra range check on the left/right variables before the recursive call, ...
Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...
I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the ...
Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child. Now if our input is ...
I was trying to speed up a certain routine in an application, and my profiler, AQTime, identified one method in particular as a bottleneck. The method has been with us for years, and is part of a "...
