希尔伯特按分而治之算法排序？

Question

我正在尝试按照Hilbert顺序对d维数据向量进行排序,以批量加载空间索引.

但是,我不想明确计算每个点的希尔伯特值,特别是需要设置特定的精度.在高维数据中,这涉及诸如32*d比特之类的精度,这使得有效地变得非常混乱.当数据分布不均匀时,这些计算中的一些是不必要的,并且对于部分数据集的额外精度是必要的.

相反,我正在尝试进行分区方法.当您查看2D一阶希尔伯特曲线时

1   4
|   |
2---3

我首先沿着x轴分割数据,这样第一部分(不一定包含一半的对象!)将由1和2组成(尚未排序),第二部分将包含3和4的对象只要.接下来,我将在Y轴上再次分割每一半,但在3-4中反转顺序.

基本上,我想执行一种分而治之的策略(与QuickSort密切相关 - 在均匀分布的数据上,这甚至应该是最优的!),并且只根据需要计算hilbert索引的必要"位".所以假设"1"中有一个对象,那么就不需要计算它的完整表示; 如果对象均匀分布,分区大小将快速下降.

我知道通常的教科书方法转换为长,灰色编码,维度交错.这不是我想要的(有很多这方面的例子).我明确地想要一个懒惰的分而治之的排序.另外,我需要的不仅仅是2D.

有没有人知道以这种方式工作的文章或希尔伯特排序算法？或者一个关键的想法如何让"旋转"正确,哪种表现形式可供选择呢？特别是在更高维度...在2D中它是微不足道的; 1旋转+ y,+ x,而4是-y,-x(旋转和翻转).但是在更高的维度上,我猜这会变得更加棘手.

(结果当然应该与通过他们的hilbert顺序以足够大的精度对对象进行排序时相同;我只是想在不需要时节省计算完整表示的时间,并且必须管理它.人们保留一个相当昂贵的散列图"对象为希尔伯特数".)

对于Peano曲线和Z曲线应该可以采用类似的方法,并且可能更容易实现......我应该首先尝试这些方法(Z曲线已经在运行 - 它确实归结为类似于QuickSort的东西,使用适当的平均值/网格值作为虚拟枢轴并循环通过每次迭代的维度).

编辑:请参阅下文,了解我如何为Z和peano曲线解决它.它也适用于2D希尔伯特曲线.但是对于希尔伯特曲线我还没有旋转和反转.

Answer 1

使用基数排序.将每个1维索引拆分为每个d .. 32大小1 .. 32/d位的部分.然后(从高阶位到低阶位)为每个索引件计算其希尔伯特值并将对象混洗到适当的箱.

这应该适用于均匀和不均匀分布的数据,包括Hilbert排序或Z顺序.并且不需要多精度计算.

关于将索引片段转换为希尔伯特顺序的一个细节:

如果索引存储在双精度中:

来到你的基数排序变量,我建议用两个大小的二进制数组d(一个主要用作堆栈,另一个用于反转索引位)和旋转值扩展zsort(使zilort成为hilbertsort)用于重新排列尺寸).

如果堆栈中的最高值为1,则将pivotize(...升序)更改为pivotize(... descending),然后对于递归的第一部分,将此顶部值推送到堆栈,第二个 - 推送该值的倒数.每次递归后都应该恢复此堆栈.它包含d基数排序过程的最后递归的"决策树" (在反向格雷码中).

d递归后,应使用此"决策树"堆栈重新计算旋转值和反转数组.如何做到这一点的确切方法并非无足轻重.它可以在以下链接中找到:hilbert.c或hilbert.c.

Answer 2

您可以直接从 f(x)=y 计算希尔伯特曲线，而无需使用递归或 L 系统或分而治之。基本上它是格雷码或哈密顿路径遍历。您可以在 Nick 的空间索引希尔伯特曲线四叉树博客或《黑客的喜悦》一书中找到很好的描述。或者看一下单调 n 元格雷码。我已经用 php 编写了一个实现，其中包括摩尔曲线。