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

作     者：曹雪峰 万刚 张宗佩 CAO Xuefeng;WAN Gang;ZHANG Zongpei

作者机构：信息工程大学地理空间信息学院 95989部队 

基　　金：国家自然科学基金(41371384 41491465) 

出 版 物：《测绘学报》 (Acta Geodaetica et Cartographica Sinica)

年 卷 期：2016年第45卷第B12期

页      码：90-98页

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

主 题 词：Hilbert曲线 Gray码 空间索引 全球离散网格 

学科分类：081603[081603] 081802[081802] 07[理学] 08[工学] 070503[070503] 0818[工学-交通运输类] 0705[理学-地理科学类] 0816[工学-纺织类] 

核心收录：

D　O　I：10.11947/j.AGCS.2016.F010

馆 藏 号：203222039...