紧致的Hilbert曲线Gray码索引算法

Hilbert曲线具有良好的聚簇性,使其成为设计全球立体网格多维数据索引的重要工具。但当数据集在不同维度上的分布密度存在较大差异时,常规Hilbert曲线索引会出现大量的冗余。对此,本文基于Gray码推导分析了Hilbert曲线索引的构造特点,进而设计实现了紧致Hilbert曲线索引算法,在保持Hilbert曲线良好聚簇性的同时,避免了数据维度分布差异带来的索引冗余问题。试验结果表明,相比常规Hilbert索引,紧致Hilbert曲线索引计算复杂度相当,在实例数据测试中编码耗时减少约40%,索引存储空间减少约46%,排序速度约为Hilbert排序的4.3倍。

Compact Hilbert Curve Index Algorithm Based on Gray Code

Hilbert curve has best clustering in various kinds of space filling curves,and has been used as an important tools in discrete global grid spatial index design field.But there are lots of redundancies in the standard Hilbert curve index when the data set has large differences between dimensions.In this paper,the construction features of Hilbert curve is analyzed based on Gray code,and then the compact Hilbert curve index algorithm is put forward,in which the redundancy problem has been avoided while Hilbert curve clustering preserved.Finally,experiment results shows that the compact Hilbert curve index outperforms the standard Hilbert index,their 1 computational complexity is nearly equivalent,but the real data set test shows the coding time and storage space decrease 40％,the speedup ratio of sorting speed is nearly 4.3.