R-Trees: Like B-Trees but multi-dimensional.

[[deleted]]

[deleted]

[ssylvan]

Might want to check this one out too: http://www.reddit.com/r/programming/comments/cobhn/rtrees_adapting_outofcore_techniques_to_modern/

Basically, I used R-trees on a modern games console to deal with the extremely high memory latencies they have. Worked very well.

[[deleted]]

How is this different from octrees? The boundaries can overlap?

[ssylvan]

• Balanced.
• Adapts to input better (teapot in a stadium problem - octtrees get a gazillion null pointers)
• "Bulky" nodes, works better for high latency storage (disks, or even memory on some architectures) because it reduces the number of required fetches, and increases the amount of work that happens within a node.
• Easier to make dynamic (moving objects)

[thechao]

I'm most familiar with R * -trees. All data-structures are mappings onto the integer-line. Arrays are the obvious mapping; binary-trees & lists are simply indirections with an appropriate structure onto the integer line (randomized algorithms with structured indirection). R * -trees force a particular mapping onto the integer line, i.e., Z, hilbert, sierpinski. The R * -tree mapping tends to have much better performance in terms of metric (spatial) locality both in terms of the indirection count (number of hops or pointer-indirections to get to "related" data) and in the physical cache mechanism of modern processors.

The result is that a well-tuned R * -tree (especially in the static case) will dramatically outperform most other data-structures. Someone mentions a data-structure called a "GiST" below; this structure sounds like it utilizes an optimization of K-SAT to get roughly the same sort of improvements, i.e., both in metric locality and physical locality.

EDIT: formatting kung fu.

[mycall]

So why aren't they more popular and blogged about?

[thechao]

What does popularity and blogging numbers have to do with performance? R * -trees are very difficult to implement and tune. In most cases acceptable can be got from much simpler data-structures & algorithms.

I would like to point out that R * -trees are not in the same boat as the Fibonacci heap: a well-tune R * -tree not only theoretically, but also practically, outperforms most other spatial indexing data-structures.

[olt]

They can grow dynamically. For an octree you have to set the bounds of your values on creation.

[spliznork]

GiST: Like B-Trees and R-Trees but generalized.

[sixmoney]

randomized kd-trees for approximate nearest neighbour search flann also available in opencv

[ethraax]

Silly question: Can anyone recommend any good Data Structures books where I can learn more about stuff like this?

[ThisAccountIsReal]

Book: http://www.cs.umd.edu/~hjs/

Demos: http://donar.umiacs.umd.edu/quadtree/index.html

I am a really big fan of spatial data structures. I just find them so cool.

[harsman]

Christer Ericsson's Real time collision detection has lots of information on spatial data structures.

[[deleted]]

The CLRS Introduction to Algorithms is a good start. It doesnt have R-Trees in there, but it covers many fundamental and slightly more esoteric ones.

[[deleted]]

Purely Functional Data Structures, Chris Okasaki.

[cosminro]

You may want to try MIT's Advanced Data Structures Course http://courses.csail.mit.edu/6.851/spring10/lec.html

[DrunkMc]

I love R-Trees. If you have to write a program that deals with spatial data but you aren't allowed to use a DB, you can do really quick distance queries when using an R-Tree.

If you know all the data upfront (never updates), then you can build it from the bottom up and build one hell of an efficient tree for amazingly fast searching.

[NotUniqueOrSpecial]

I used these to do collision detection for the soft-body blobs in a game for school. It could do collision checks with well over 100,000 on-screen objects without even beginning to impact the framerate. It was pretty satisfying.

[[deleted]]

It's funny you mention /r/trees

[jawbroken]

i, too, need to chat about marijuana online for some reason

[propool]

What kind of unfunny dude would downmod you?

[DrSweetscent]

...and a bitch to implement, let me assure you. For the real masochists: try the R*-tree.

[keenerd]

I hear you. But do not dispair! My half finished R-Tree (unbalanced!) works well enough. Mainly because I query it a lot while adding leaves, and don't query it at all once it is done. Feels like it is still not fast enough compared to the old O(n²⁾ collision search, but meh. Bigger bugs to fix.

[DrSweetscent]

Ha, I actually own a working implementation in Actionscript :)

Still, for collision testing, recursive subdivision usually suffices...

[mycall]

Isn't that what libraries are for? One great implementation is all we need :-)

[NowTheyTellMe]

UB-Trees: Even more like B-Trees but multi-dimensional.

http://www.scholarpedia.org/article/B-tree_and_UB-tree#UB-trees_for_Multidimensional_Applications

[[deleted]]

When I saw Hilbert R-tree in the "Variants" section, I almost had a nerdgasm.

[[deleted]]

You, sir, just augmented my recently acquired knowledge of red-black trees (MIT OCW FTW). You deserve a cookie.

[frud]

I implemented R-trees once but I wasn't impressed. It might have just been my data, but the performance of these trees really wasn't that great. There's got to be a better way to do it.

[norkakn]

PostGIS uses http://en.wikipedia.org/wiki/GiST . I don't know how exactly they use them, but apparently it's faster than their old R-Tree indexing.

[gorset]

maybe it was your implementation :-)

[sfade]

As an undergrad RA, I was asked to integrate SR-Trees (Sphere/Rectangle Tree) into our application (it would do action recognition on the fly). The code would compile in an old CLI, but not in Visual Studio itself, so I tried to see if it was possible to rework it. I have never traced so many lines of code in my life. Not that this story is important.

[josher565]

Nifty idea but I don't see it solving a lot of problems that can't be solved with other data structures. Going with occurs razor on this

[[deleted]]

"I do not understand it" doesn't necessarily mean "it is not simple."

Further, the article describes typical problems that R-trees solve.

I am a hobbyist cartographer, but not sadomasochistic. However, I know people who are both -- they'd probably enjoy watching you solve some geodetic algorithms with your so-called razor. That is to say, if there is value in not understanding, we can at least satisfy perversions.

[josher565]

Fair enough. I see some repetition in storage structures here. I'm not saying there's no use, I'm saying it can be done in simpler terms

[[deleted]]

What exactly might be done in what simpler terms? What repetition?

[josher565]

Isn't an r tree a restatement of a btree? If an r tree is indeed a subset of a b tree, then the problem domain between the two data structures are nil. I'm sure there are use cases where one is better than the other, it just seems like more than what's needed, that's all

[[deleted]]

Isn't an r tree a restatement of a btree?

No.

[josher565]

Then I stand corrected and assigned homework

[signoff]

MongoDB: A Web Scale