莫頓代碼是否對更高維度最有效？

Question

對於我當前的輸入數據（點數爲3D），我使用Morton code來提高訪問點列表時的緩存一致性。

我有一些其他的數據是6D和7D。莫頓代碼對於這些維度來說仍然是一個很好的技術嗎？或者還有其他技術嗎？其他空間填充曲線技術比3D本身的Morton計算更復雜，我想知道人們是否使用6D/7D或更高版本的替代技術。

Answer 1

你應該嘗試行主或索引索引。它們還保留了空間局部性，但它們可以更高效地計算出來，即使在更高維度上也是如此。

您可以在書籍「藝術彙編語言」第5章第211-216頁更深入地閱讀有關行列和主列索引的更深入的細節（但幾何意義不大）。相關章節可在線獲取here。

關於您可以考慮的各種空間索引技術，包括上面提到的，有很好的paper：Samet，H. 2017.排序空間數據。國際地理百科全書。 1-11。

希爾伯特和格雷指數在這裏不是一個選項，因爲它們比莫頓（它們的大部分實現包含隱式莫頓編碼）計算速度慢。 基本上，一個適當的莫頓（lookup-table or magic numbers based）實現和行主/列主索引是最快的。