4 ms·
A dive into spatial search algorithms
- mattnewport 10y agoComing from a games background, I've not heard of an R tree before. Quadtrees (or octtrees for 3D) are probably the most common spatial query data structure used in game engines. I'm surprised they weren't mentioned in the article. Gonna have to do some research on what the pros and cons of an R tree are vs a quadtree now.
- jandrewrogers 10y agoR-trees are relatively slow, particularly if you have a very high mutation rate. Their sole redeeming feature is that they can handle non-point geometries with constant space complexity whereas quad-trees have pathological space complexity for geometries like polygons. If you are just dealing with points, an R-tree is a poor algorithm choice. Quad-trees are pretty close to ideal in terms of performance for that use case.
- phkahler 10y agoI've found octtrees quite useful for geometric primitives. There is the pathological case of long thin objects, but I place those in a large number of small nodes rather than one large node. Insert and delete are generally O(log n).
- santaclaus 10y ago> quad-trees have pathological space complexity for geometries like polygons Any idea what is used in the wild for closest point queries against non-point data (triangle meshes or otherwise)?
- geophile 10y agoQuadtrees are fine. Just don't approximate the polygon to the limit of resolution of the space. I wrote a paper many years ago on a related problem. The conclusion was that a very small number of quads would be optimal. Too many is obviously a problem; too few and you have to filter out a lot of false negatives. The paper was in ACM SIGMOD 89, Redundancy in Spatial Databases.
- norkakn 10y agoI imagine that you are working in a domain where it is true that R-Trees are slow and only have the one redeeming quality. Anything that I've done involving things on a screen have performed better with quadtrees for me, so I'm not discounting your experience at all. In other domains though, R-Trees have many other advantages, and often perform better. http://www.dpi.inpe.br/livros/bdados/artigos/oracle_r_tree.pdf http://www.dpi.inpe.br/livros/bdados/artigos/oracle_r_tree.p... "For these datasets, R-trees consistently outperformed Quadtrees by 2-3 times" ... "In short, a quadtree could be recommended for update-intensive applications using simple poly-gon geometries, high concurrency update databases, or when specialized masks such as touch are frequently used in queries. However, users have to fine-tune the tiling level to obtain best performance. R-trees, which do not require any such tuning, could be used in all other cases to obtain nearly equivalent or better performance."
- deleted 10y ago[deleted]
- dlubarov 10y agoOctrees can be used for non-point geometries too. You just have to store some geometries at non-leaf nodes. When inserting, you search the tree for the deepest voxel which encapsulates the entire geometry (or, equivalently, its bounding box). At least that's how I've always done it. The advantage of R-trees and kd-trees is that you can partition the space more intelligently. With octrees, a voxel is always divided into eight equal children, even if one of the eight children will contain all the points/geometries. It's usually not a big problem, but if you have a few small objects with lots of detail and far from the origin, you might get a poorly-balanced octree with some very deep branches. As you mention, R-trees and kd-trees have slow insertion, but if you're path tracing a static scene and the rendering is going to take hours, you don't really care about that.
- geophile 10y agoThis discussion is incomplete without mentioning space-filling curves. These curves map the data into a 1-d space and then you can use any conventional search structure -- sorted array with binary search, balanced tree, skiplist, b-tree, etc. This allows you great flexibility, including the use of 3rd party libraries of data structures. (A quadtree is basically the z-order space-filling curve combined with a trie of degree 4. Octtree -- degree 8.) This approach also handles non-point data very cleanly. A non-point object gives rise to multiple index entries. (You can tune the number of index entries quite easily.) Space-filling curves also leads to a very nice kNN algorithm: To find the k nearest neighbors of p, first search the index for p. Find k neighbors along the space-filling curve, (these are adjacent in the index), and of these, pick the point q maximizing distance(p, q). All k nearest neighbors of p must be in a circle centered at p with radius distance(p, q). Now search your index again using this circle and pick the k points n1, ..., nk minimizing distance(p, ni).
- robrenaud 10y agoYeah, the effectiveness of that idea mad me a little sad when I worked on google maps. I spent all this time studying computational geometry in college and it went out the window. Use space filling curves and then standard text indexing techniques and you don't need to deal with any fancy geometric algorithms.
- tps5 10y agoDo you have any references to recommend on this subject?
- neel8986 10y agoNice algorithm. I am curious what happens when the dimension becomes really large (more than 100). I have heard about kd tree but as far as I know the performance becomes really bad for d > 16. What should be the strategy of finding nearest neighbours for such high dimensions?
- snovv_crash 10y agoIt often depends on what the actual dimensionality of the problem is. If it can be embedded in a lower dimensional space, as many problems are, then a well tuned kD-Tree can still do a good job up to about 16 dimensions of used space, as you say. Cover trees also work well in this case, and are better at extracting just the salient dimensions than kD-Trees are, especially as the discrepancy between the subspace and data space grows. If the dimensionality gets larger then a better approach is to instead remove overhead and improve parallelism, for example by pushing the problem to the GPU or discretizing the measurement space down to 8-bits or even 1-bit per dimension. I know of products that do both, and solve O(N^2) problems 20x larger than a naïve approach could in the same time. POPCNT runs really fast on GPUs.
- MrQuincle 10y agoEuclidean? Then nearest neighbor itself is rarely what you want: https://link.springer.com/chapter/10.1007%2F3-540-49257-7_15 https://link.springer.com/chapter/10.1007%2F3-540-49257-7_15. Quote from abstract: "We show that under a broad set of conditions (much broader than independent and identically distributed dimensions), as dimensionality increases, the distance to the nearest data point approaches the distance to the farthest data point" In the end - in the physical world - everything maps to 3D give or take a few dimensions that are very small if we have to believe some physicists. You just have to find the mapping. :-)
- argonaut 10y agoFor large dimensions, a normal linear search.
- vvanders 10y agoAlong similar lines Real-Time Collision Detection[1] is a tour-de-force in spatial partitioning algorithms. It's basically data-structures for 2D/3D along with some really good coverage of common floating point numerical issues and cache friendly algorithms. Easily the in the top 3 technical books I've purchased. Each page is solid gold and very little space is wasted. [1] - https://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323 https://www.amazon.com/Real-Time-Collision-Detection-Interac...
- Boothroid 10y agoIn my experience most of the work in this area has been done in that you will rarely find yourself having to think seriously about spatial indexing, and even when the task forces you to, most of the tools one would commonly choose between have different indexing options implemented as standard.
- greg7mdp 10y agoYou should check out the Churchill Challenge (http://churchillnavigation.com/challenge/ http://churchillnavigation.com/challenge/) and the 54 solutions (source code available at https://github.com/churchillnavigation/challenge1 https://github.com/churchillnavigation/challenge1). I came in at #7. Beyond the classic spatial search data structures, the fastest solutions all used SSE instructions (see https://github.com/sDessens/churchill-challange https://github.com/sDessens/churchill-challange for nice writeup). People did try pretty hard to win the grand prize of $5000, and the fastest solution was 7 times faster than the best optimized code that Churchill's team had previously.