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

• 作者: 万刚 张宗佩 曹雪峰
• 来源期刊: 测绘学报
• 学科: 地球科学
• 关键词: Hilbert曲线 Gray码 空间索引 全球离散网格
• 年，卷（期）: 2016,（z1）
• 页码范围: 90-98
• 页数: 9页
• 分类号: P208
• 字数: 7888字
• 语种: 中文
• DOI: 10.11947/j.AGCS.2016.F010

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	万刚	信息工程大学地理空间信息学院	68	667	13.0	24.0
2	曹雪峰	信息工程大学地理空间信息学院	27	111	7.0	8.0