Re: [Algorithms] Cache-oblivious layout (was: BSP tree, or what?)

[Marc B. R. <mar...@or...>]

My original testing was a very simple "proof of concept" and the results
were
"Promising...needs further investigation"...which never happened, so take
this info for what it's worth.

> That sounds interesting. Could you expand on this a bit?

Originally I used this technique in 2D for paging in data for grids and
quadtrees. I got the idea from [1].  Started thinking about a 3D version
after reading [2].

> In what order are the nodes stored this way?

What I did in my test was to take the 3D coordinate of a node, convert it to
a Hilbert index and used the (sorted) Hilbert-indices to layout the memory.
There are probably MUCH better methods.

Conceptually, you layout memory as a Hilbert curve walk of the space would
'touch' the node in question. Well, actually there is no reason to restrict
to Hilbert...let's say some space-filling curve. I'm thinking that, say a
Morton curve might be better for dynamic trees.

> What was the performance gain, in what kind of situations did it
> behave well/badly ?

This is all from memory, so I can't give any solid data.  The test was as
follows:

* Forest of octrees (I believe they were 'region' octrees). By forest I mean
an 'n' by 'n'
  grid.
* The trees were static, but contained moving objects in addition to static
objects.

And my timings were "visit all nodes along this line within radius 'R'", and
the Hilbert layout performed consistent better, except in the trivial case
(line is roughly a linear memory walk).  The gains were modest, but this was
on something like (guessing here) a Pentium 3.

Most of the papers I was referencing at the time came from nearest and
approx-nearest neighbors research.
-----

[1]   "Fractals for Secondary Key Retrieval"
 
http://www.intelligence.tuc.gr/~petrakis/courses/multimedia/papers/fractals.
pdf

[2]   "Linear Clustering of Object with Multiple Attributes"
 
http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources
/PAPERS+BOOK/jagadish-sigmod-90-P332.pdf