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

摘要：

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

关键词：Hilbert曲线、Gray码、空间索引、全球离散网格

所属期刊栏目：45

分类号：P208(一般性问题)

资助基金：国家自然科学基金41371384,41491465The National Natural Science Foundation of China .41371384,41491465

在线出版日期：2017-05-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：90-98