﻿ 紧致的Hilbert曲线Gray码索引算法
 文章快速检索 高级检索

1. 信息工程大学地理空间信息学院, 郑州 450052;
2. 95989部队, 北京 100076

Compact Hilbert Curve Index Algorithm Based on Gray Code
CAO Xuefeng1, WAN Gang1, ZHANG Zongpei2
1. Institute of Geospatial Information, Information Engineering University, Zhengzhou 450052, China;
2. Troops 95989, Beijing 100076, China
Foundation support: The National Natural Science Foundation of China (Nos. 41371384; 41491465)
First author: CAO Xuefeng (1983—), male, lecturer, majors in discrete global grid. E-mail: CAO_Xue_Feng@163.com
Abstract: 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.
Key words: hilbert curve     gray code     spatial index     discrete global grid

Hilbert曲线编码的经典方法是由文献[1]针对二维空间构造提出的。该算法是基于Morton码的二进制位操作法，算法复杂度为O(n2)。文献[3]根据Hilbert曲线的空间层次分解特征，通过栅格空间层次分解与构造域状态转移向量，设计了二维空间中Hilbert码的递归生成算法，算法复杂度为O(max (n))。文献[4]设计了基于状态转移矩阵的Hilbert码快速生成算法，将Hilbert状态转移矩阵转换为C++中的数组运算, 减少了Hilbert码计算过程中的嵌套循环及迭代处理，将算法复杂度降为O(n)。上述编码方法都只是在二维空间中进行讨论的。文献[5]研究了n维Hilbert曲线的生成问题，提出基于静态演化规则、自底向上的生成算法，算法复杂度为O(nlogn)。文献[6]设计了任意维空间中具有线性复杂度的Hilbert码算法。

1 Hilbert曲线索引算法 1.1 Hilbert曲线

Hilbert曲线因其良好的空间局部性得到比较深入的研究，出现了各种曲线构造和编码算法，其中最经典是文献[12]提出的算法[12]，文献[13]对其进行实现[13]，文献[14]提出了改进该算法[14]，使其得到广泛应用。下面对Butz算法[15]进行简要分析，特别是考察其几何构造特点。

(1) 取k阶Hilbert曲线的一个副本，逆时针旋转90°放置于左下方2k×2k网格中；

(2) 取k阶Hilbert曲线的一个副本，顺时针旋转90°放置于左上方2k×2k网格中；

(3) 取k阶Hilbert曲线的一个副本，放置于右侧的两个2k×2k网格中；

(4) 将4个2k×2k网格中的k阶Hilbert曲线依次连接起来。

1.2 基于Gray码的Hilbert曲线构造方法

1.2.1 Gray码

Gray码对数字进行排序后，在给定底数时相邻数字的排序码仅在1个bit上不同。根据Gray码构造规则，给出关于Gray码的一些性质[9]

(1) Gray码编码：Gray码序列的生成函数为

(1)

(2) Gray码逆变换：对于非负整数i，令m=log2(i+1)，则i的二进制表示需要m bit，存在

(2)

(3) Gray码维度变化：序列g(i) 由g(i)=tsb (i) 给出，其中tsb是i的二进制表达中trailing set的比特数。

(4) Gray码对称性：给定nN和0≤i < 2n，存在

(3)

(5) g(i) 的对称性：序列g(i) 是对称的，使得对于0≤i < 2n-2，存在g(i)=g(2n-2-i)。

1.2.2 入口点

Gray码的顺序可以视为Rn空间中单位超立方体上顶点的次序。在2维空间中递归构造Hilbert曲线时，需要放大到曲线上每一个点 (子超立方体)，然后利用经过变换、旋转的初始曲线将其代替，必须通过2n个子超立方体确定Hilbert曲线的方向。这些子Hilbert曲线的朝向必须使曲线从当前子超立方体的出口到下一个子超立方体的入口之间连续。此外，父级超立方体的入口和出口必须与第1个子超立方体的入口、最后一个子超立方体的出口相一致。

(4)

1.2.3 旋转和反射

(5)

1.2.4 T变换

(6)

(1) 变换入口点和出口点：利用T(e, d)ef对应的变换到Bn(对应n比特的正整数集合) 上Gray码序列的第一个和最后一个，即

(7)

(2) T(e, d)逆变换：T(e, d)的逆变换是其自身的T(e, d)变换，如下式给出

(8)

(9)

(10)

(11)

1.3 基于Gray码的Hilbert索引算法

(12)

l的每一bit表示点p是否落入相对某一给定坐标轴的下方或上方的点集中。由此，lm-1可以指示出点p位于哪一个子超立方体内，也即通过点p所属超立方体的顶点可获得Hilbert曲线的顶点。

(1) 对空间做旋转和反射，有lm-1=T(e, d)(lm-1)；

(2) 确定关联的子超立方体的Hilbert索引，有wm-1=gc(1(lm-1)。

(13)

2 紧致Hilbert曲线索引

2.1 Gray码排序算法

 gc (i) 8 10 12 14 20 26 28 30 i 15 12 8 11 16 19 23 20 gcr (i) 3 2 0 1 4 5 7 6 [gc (i)][2] 001000 001010 001100 001110 011000 011010 011100 011110 [i][2] 001111 001100 001000 001011 010000 010011 010111 010100 [gcr(i)][2] 011 010 000 001 100 101 111 110

U={u0 < … < uu‖-1}表示掩模μ中无约束位标识的集合，对于所有0≤k≤‖μ‖，存在bit (u, uk)=1，同时令π表示μ下的模式。对于abI，用i表示ab之间的最重要的不匹配位，即i=max{k|bit (a, k)(bit (b, k)}，iU

(14)

2.2 紧致Hilbert曲线索引计算方法

(15)

μ=[αn-1α0][2](d+1)，其中

(16)
(17)

3 试验分析

3.1 适用范围

Moore的Hilbert索引实现存在一个约束，即nm≤64，其中，n表示维数，m表示每个维度上的网格数为2m，即网格总数为2nm。当维数为3，则Moore的Hilbert索引每个维度上的网格数为不超过221，最多支持263个网格单元。与Moore的Hilbert索引实现[14]相比，紧致Hilbert曲线索引对维数和每个维度上的网格数据没有限制。

3.2 存储消耗

3.3 索引构造耗时

 图 1 索引构造耗时比较 Fig. 1 The time consuming of index construction

3.4 排序性能

 图 2 紧致Hilbert曲线索引和常规Hilbert索引的排序性能比较 Fig. 2 The sorting performance compare between compact Hilbert index and standard Hilbert index

4 结束语

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

﻿

 [1] FALOUTSOS C, ROSEMAN S. Fractals for Secondary Key Retrieval[C]//Proceeding of the 8th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Philadelphia:ACM, 1989:247-252. [2] CHEN H L, CHANG Y I. All-Nearest-Neighbors Finding Based on the Hilbert Curve[J]. Expert Systems with Applications, 2011, 38(6): 7462–7475. DOI:10.1016/j.eswa.2010.12.077 [3] 陆锋, 周成虎. 一种基于空间层次分解的Hilbert码生成算法[J]. 中国图象图形学报, 2001, 6A(5): 465–469. LU Feng, ZHOU Chenghu. An Algorithm for Hilbert Ordering Code Based on Spatial Hierarchical Decomposition[J]. Journal of Image and Graphics, 2001, 6A(5): 465–469. [4] 李绍俊, 钟耳顺, 王少华, 等. 基于状态转移矩阵的Hilbert码快速生成算法[J]. 地球信息科学, 2014, 16(6): 846–851. LI Shaojun, ZHONG Ershun, WANG Shaohua, et al. An Algorithm for Hilbert Ordering Code Based on State-Transition Matrix[J]. Journal of Geo-Information Science, 2014, 16(6): 846–851. [5] 李晨阳, 段雄文, 冯玉才. N维Hilbert曲线生成算法[J]. 中国图象图形学报, 2006, 11(8): 1068–1075. LI Chenyang, DUAN Xiongwen, FENG Yucai. Algorithm for Generating N-Dimensional Hilbert Curve[J]. Journal of Image and Graphics, 2006, 11(8): 1068–1075. [6] 刘辉, 冷伟, 崔涛. 高维Hilbert曲线的编码与解码算法设计[J]. 数值计算与计算机应用, 2015, 36(1): 42–58. LIU Hui, LENG Wei, CUI Tao. Development of Encoding and Decoding Algorithms for High Dimensional Hilbert Curve[J]. Journal on Numerical Methods and Computer Applications, 2015, 36(1): 42–58. [7] 程承旗, 张恩东, 万元嵬, 等. 遥感影像剖分金字塔研究[J]. 地理与地理信息科学, 2010, 26(1): 19–23. CHENG Chengqi, ZHANG Endong, WAN Yuanwei, et al. Research on Remote Sensing Image Subdivision Pyramid[J]. Geography and Geo-Information Science, 2010, 26(1): 19–23. [8] 余接情, 吴立新. 适应性球体退化八叉树格网及其编码[J]. 地理与地理信息科学, 2012, 28(1): 14–18. YU Jieqing, WU Lixin. Adaptable Spheroid Degenerated-Octree Grid and Its Coding Method[J]. Geography and Geo-Information Science, 2012, 28(1): 14–18. [9] 曹雪峰. 地球圈层空间网格理论与算法研究[D]. 郑州: 解放军信息工程大学, 2012. CAO Xuefeng. Research on Earth Sphere Shell Space Grid Theory and Algorithms[D]. Zhengzhou:The PLA Information Engineering University, 2012. [10] 张宗佩. 地月圈层立体网格理论与应用研究[D]. 郑州: 解放军信息工程大学, 2015. ZHANG Zongpei. Research on Earth-Lunar Sphere Shell Space Grid Theory and Application[D]. Zhengzhou:The PLA Information Engineering University, 2015. [11] 万刚, 曹雪峰, 李科, 等. 地理空间信息网格理论与技术[M]. 北京: 测绘出版社, 2016. WAN Gang, CAO Xuefeng, LI Ke, et al. Geospatial Information Grid Theory and Technology[M]. Beijing: Surveying and Mapping Press, 2016. [12] BUTZ A R. Alternative Algorithm for Hilbert's Space-Filling Curve[J]. IEEE Transactions on Computers, 1971, 20(4): 424–426. [13] THOMAS S W. Utah Raster Toolkit[EB/OL].[2016-02-03]. http://web.mit.edu/afs/athena/contrib/urt/src/urt3.1/urt-3.1b.tar.gz. [14] MOORE D. Fast Hilbert Curve Generation, Sorting, and Range Queries[EB/OL].[2016-05-01]. http://www.tiac.net/~sw/2008/10/Hilbert/moore/index.html. [15] GRAY F. Pulse Code Communication:US, 2632058[P]. 1953-03-17. [16] FILL J A, JANSON S. The Number of Bit Comparisons Used By Quicksort:An Average-Case Analysis[C]//Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. New York:AVM, 2004:300-307.
http://dx.doi.org/10.11947/j.AGCS.2016.F010

0

#### 文章信息

CAO Xuefeng, WAN Gang, ZHANG Zongpei

Compact Hilbert Curve Index Algorithm Based on Gray Code

Acta Geodaetica et Cartographica Sinica, 2016, 45(S1): 90-98
http://dx.doi.org/10.11947/j.AGCS.2016.F010