I used to use a kind of self-made QuadTree for spatial indexing (long before I got the word quadtree "). For ordinary kinds of spatial data (I deal with street map data) they are fast to create and query fast, but they scan too a lot of leaf nodes during queries, in particular with reasonable node sizes (50-100), my quadrants, as a rule, produce about 300 results for a point query, i.e. 3-6 leaf nodes are applied (very rough approximate result, result you vary greatly).
My current preferred data structure is the R * tree. I wrote and tested the implementation myself, getting very good results. My R * tree building code is very slow compared to my QuadTree code, but the bounding fields on the leaf nodes are very well organized; at least half of the query space is answered by only one leaf node (i.e. if you are doing a random point query, there is a good chance to return only one leaf node), and something like 90% of the space is covered by two nodes or less. Thus, with a node size of 80 elements, I usually get 80 or 160 results from a point query, with the average closer to 160 (since multiple queries return 3-5 nodes). This is true even in dense urban areas of the map.
I know this because I wrote a visualizer for my R * tree and the graphical objects inside it, and I tested it on a large dataset (600,000 road segments). It works even better with point data (and other data where bounding fields rarely overlap). If you implement the R * tree, I urge you to visualize the results, because when I wrote, I had several errors that reduced the efficiency of the tree (without affecting the correctness), and I was able to tune some of the solutions to get better results. Be sure to check on a large data set, as this will show problems that are not enough for a small data set. This can help reduce the branching (node size) of the tree for testing to see how well the tree works when it is at several levels.
I would be happy to provide you with the source code, except that I will need permission from my employer. You know how it is. In my implementation, I support forced reintegration, but my PickSplit and add-on penalty have been changed.
Original paper Tree R *: an effective and reliable access method for points and rectangles , for some reason skips points (there are no periods and points on the "i"). Moreover, their terminology is a bit strange, for example. when they say "extreme," they mean "perimeter."
The R * tree is a good choice if you need a data structure that can be modified. If you do not need to modify the tree after it is created, consider bulk loading algorithms . If you only need to slightly modify the tree after bulk loading, the usual R-tree algorithms will be good enough. Note that the R * -tree and R-tree data are structurally identical; only the algorithms for inserting (and possibly deleting, I forgot) are different. The R-tree has been the original data structure since 1984; here is a link to the R-tree .
kd-tree looks efficient and not too complicated to implement, but it can only be used for point data.
By the way, the reason I focus on leaf nodes is because
- I need to deal with disk spatial indexes. You can usually cache all internal nodes in memory because they make up a small fraction of the size of the index; therefore, the time taken to scan them is tiny compared to the time required for a node sheet that is not cached.
- I save a lot of space without preserving the bounding fields for elements in the spatial index, which means that I have to actually check the source geometry of each element to respond to the request. Thus, it is even more important to minimize the number of affected leaf nodes.