Is Morton code the most efficient for higher dimensions?

Question

For my current input data, which is points in 3D, I'm using Morton code to improve the cache coherence when accessing the point list.

I have some other data that is 6D and 7D. Is Morton code still a good technique for such dimensions? Or are there any other techniques? The other space filling curve techniques were more complex to compute than Morton in 3D itself, I'm wondering if folks use an alternative technique for 6D/7D or higher.

Answer 1

You should try row-major or row-prime indexing. They also preserve spatial locality, but they can be computed more efficiently, even in higher dimensions.

You can read about row-major and column-major indexing in deeper detail (but in less geometrical sense) in the book The Art of Assembly Language, chapter 5, page 211-216. The relevant chapter is available online here.

And there is a good paper about various spatial indexing techniques you can consider, including the mentioned ones: Samet, H. 2017. Sorting Spatial Data. The International Encyclopedia of Geography. 1–11.

Hilbert and Gray index are not an option here, since they are slower to compute than Morton (most implementations of them contain an implicit Morton encoding). Basically a proper Morton (lookup-table or magic numbers based) implementation, and the row-major/column-major indexing are the fastest.