Data structures that spatially subdivide (3D) space

[Sagekilla]

So for my honors thesis I'm working on (among other things) accelerating the force evaluation in
the N-Body simulation.

The obvious data structure to use for accelerating the force sum is the Octree, used in the Barnes-Hut
algorithm. Another interesting data structure is the K-d tree, which works well on certain types of data
but is usually a bit worse than the Octree because it creates ridiculously deep tree structures for interesting
problem sizes (N ~= 32k, which I can get running in real time on a quad core i7).

Can anyone recommend any other data structures for spatial subdivision? I'm trying to explore as many as I can
to see what the various properties of each data structure are.

I should note that my concern will not be doing any sort of searching, inserting, or removal. The force evaluation
algorithm (which works independent of data structure) simply relies on being able to walk the data structure.
So the only thing I need to be able to do is to construct the data structure and provide the root to the data structure.

[Derek]

So for my honors thesis I'm working on (among other things) accelerating the force evaluation in
the N-Body simulation.

The obvious data structure to use for accelerating the force sum is the Octree, used in the Barnes-Hut
algorithm. Another interesting data structure is the K-d tree, which works well on certain types of data
but is usually a bit worse than the Octree because it creates ridiculously deep tree structures for interesting
problem sizes (N ~= 32k, which I can get running in real time on a quad core i7).

Can anyone recommend any other data structures for spatial subdivision? I'm trying to explore as many as I can
to see what the various properties of each data structure are.

I should note that my concern will not be doing any sort of searching, inserting, or removal. The force evaluation
algorithm (which works independent of data structure) simply relies on being able to walk the data structure.
So the only thing I need to be able to do is to construct the data structure and provide the root to the data structure.

Is ~15 levels "ridiculously deep"? That's what a balanced binary tree (which KD-trees are) of 32K elements will have. Octrees and KD-Trees are pretty similar, the main difference is that KD-Trees divide one dimension at a time while trying to maintain a roughly balanced tree, while Octrees divide all three dimensions at once, which I think would make them somewhat less balanced (probably easier to implement though). That said I have no idea how either performs when the points are moving around, I didn't have to worry about that when I implemented a KD-Tree.

Wait, if you just need to walk the data structure, why not just use a linked list? Tree structures are useful for searching and sorting, if you're not doing either of those then you don't need anything nearly that complicated.

[Sagekilla]

Is ~15 levels "ridiculously deep"? That's what a balanced binary tree (which KD-trees are) of 32K elements will have. Octrees and KD-Trees are pretty similar, the main difference is that KD-Trees divide one dimension at a time while trying to maintain a roughly balanced tree, while Octrees divide all three dimensions at once, which I think would make them somewhat less balanced (probably easier to implement though). That said I have no idea how either performs when the points are moving around, I didn't have to worry about that when I implemented a KD-Tree.

Wait, if you just need to walk the data structure, why not just use a linked list? Tree structures are useful for searching and sorting, if you're not doing either of those then you don't need anything nearly that complicated.

For what I'm doing, yes 15 levels is extremely deep. The Octree is only 5 levels deep by comparison, and the cost for walking the tree
is quite expensive for deep trees. Also, using a linked list is pointless for me since that has the same, if not worse, performance than
the standard pairwise algorithm (Which runs in O(n^2)). The KDtree and Octree allow for O(n log n) performance because of how they
treat collections of bodies which are close in proximity as single composite bodies.

Since I'm using the trees to accelerate force evaluation, searching and sorting are useless for me. The main thing I need to do is subdivide the bodies in such
a way that I can make use of properties of the Taylor series of the gravitational potential to do only O(log(n)) evaluations for each body relative to the tree instead
of n evaluations.

The tree walking itself is a non-trivial algorithm which includes computing multipole expansions and passing them both up and down the tree. But this part works
generically independent of the underlying tree structure. The biggest determinant in the performance of the tree depends on the structure of the tree.


Also, I just realized I can use a BSP tree to do this. It seems like the natural generalization to the KDtree but I can subdivide the n-body system according to the
underlying geometry, rather than being forced to use axis aligned planes.

[Yakk]

What is expensive -- walking the tree, or doing the things you do when walking the tree?

The branching factor on an Octtree is 8fold, so 5 deep is 8^5 = 32768 sections.
The branching factor on a K-D tree is 2fold, so 15 deep is 2^15 = 32768 sections.

Setting up a K-D tree so that you clump 3 layers "together" is pretty trivial. And if your problem is that the steps you do as you walk the tree is expensive, then doing them every 3 steps in the tree in a K-D tree should give you Octtree level performance.

Call that the "leap" count. Some trees have a smaller or larger branching factor -- a larger leap and a smaller branching factor is equivalent to a smaller leap and larger branching factor.

---

You are trying to use the K-D tree/Octtree to sort bodies into clumps, do internal forces in the clumps, and then do inter-clump forces? You are aware that this won't give you the true values, right? (a clump of bodies that isn't perfectly spherical cannot, in general, be treated as a point mass) I suppose you can determine the variance from the point mass approximation as a function of distance...

---

BSP will act like a KDTree in branching factor.

---

You could simply boost the branching factor upwards from an octtree somehow and get even faster performance, if you don't like the idea of the "leap" parameter above.

[Sagekilla]

Yes, im aware that using any tree data structure to accelerate the force evaluation will introduce force and potential errors. Hence me saying that im doing a multipole expansion when i walk the tree. Actually walking the tree is cheap. The expensive part is computing the force of a tree node on a body within the collective system. I use an acceptance criteria based on the ratio of the distance between a node and a body and the radius of the cell node. If this ratio is less than an opening parameter, theta, i use the approximation otherwise i refine the calculation.

I already have all the infrastructure for doing the computations. The interesting part is now seeing how different spatial subdividers react to different system geometries. That was why i was askimg for advice on alternative data structurws to explore.


Sorry about the typos, on my phone and its refusing to do autocorrect AND its autoscrolling to the enebof the line making manual corrections near impossible. Ill fix them when i get to my computer.

(Seriously, youd think a galaxy nexus wouldnt be this much of a pain to rwply to xkcd fora threads)

[Derek]

I suspect that difference between the data structures will be a small constant, they're all based on the same idea. Just pick one and go with it. If performance really is that big a deal implement all three and test it. But I really doubt it will be a big difference.

[Carnildo]

I suspect that difference between the data structures will be a small constant, they're all based on the same idea.

I expect that under certain circumstances there'll be significant performance differences. The relationship between an octree and a BSP tree is like that between a naive binary tree and a fully balanced binary tree: they've got the same average-case performance, but very different worst-case performances -- but at the same time, an octree (like a naive binary tree) is faster and easier to build and update.

[Derek]

You should be able to make a roughly balanced octree. Just place the dividing point such that the orthogonal planes through it each divide the objects in half. Then the worst case scenario is that each level (8 branches) divides the objects into two groups (opposite corners). Not as good as a BSP or KD Tree, but still gives you log performance.