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

doi:10.11947/j.AGCS.2016.F010

测绘学报 ›› 2016, Vol. 45 ›› Issue (S1): 90-98.doi: 10.11947/j.AGCS.2016.F010

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

曹雪峰¹, 万刚¹, 张宗佩²

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

收稿日期:2016-08-20 修回日期:2016-10-20 出版日期:2016-12-31 发布日期:2017-03-29
作者简介:曹雪峰(1983-),男,讲师,研究方向为全球离散格网。E-mail:CAO_Xue_Feng@163.com
基金资助:
国家自然科学基金（41371384；41491465）

Compact Hilbert Curve Index Algorithm Based on Gray Code

CAO Xuefeng¹, WAN Gang¹, ZHANG Zongpei²

1. Institute of Geospatial Information, Information Engineering University, Zhengzhou 450052, China;
2. Troops 95989, Beijing 100076, China

Received:2016-08-20 Revised:2016-10-20 Online:2016-12-31 Published:2017-03-29
Supported by:
The National Natural Science Foundation of China (Nos. 41371384;41491465)

摘要/Abstract

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

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

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

中图分类号:

P208

曹雪峰, 万刚, 张宗佩. 紧致的Hilbert曲线Gray码索引算法[J]. 测绘学报, 2016, 45(S1): 90-98.

CAO Xuefeng, WAN Gang, ZHANG Zongpei. Compact Hilbert Curve Index Algorithm Based on Gray Code[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1): 90-98.

参考文献

[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.
[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.

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

Compact Hilbert Curve Index Algorithm Based on Gray Code

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

[1]	吴宇豪, 曹雪峰, 余岸竹, 孙万忠. 三维Hilbert曲线层级演进模型与编码计算[J]. 测绘学报, 2022, 51(1): 104-114.
[2]	吴政, 武鹏达, 李成名. 对等网络下自适应层级的矢量数据时空索引构建方法[J]. 测绘学报, 2019, 48(11): 1369-1379.
[3]	赖广陵, 童晓冲, 丁璐, 秦志远. 三维空间格网的多尺度整数编码与数据索引方法[J]. 测绘学报, 2018, 47(7): 1007-1017.
[4]	曹雪峰, 万刚, 张宗佩. Hilbert曲线层级演进关系[J]. 测绘学报, 2016, 45(S1): 77-84.
[5]	付仲良, 胡玉龙, 翁宝凤, 彭瑞. M-Quadtree索引:一种基于改进四叉树编码方法的云存储环境下空间索引方法[J]. 测绘学报, 2016, 45(11): 1342-1351.
[6]	王金鑫, 郑亚圣, 李耀辉, 禄丰年, 刘俊楠. 利用球体剖分瓦块构建真三维数字地球平台[J]. 测绘学报, 2015, 44(6): 694-701.
[7]	吴明光. 一种空间分布模式驱动的空间索引[J]. 测绘学报, 2015, 44(1): 108-115.
[8]	段红伟孟令奎黄长青李颖李继园 . 基于SPARQL查询的地理语义空间索引构建方法[J]. 测绘学报, 2014, 43(2): 193-199.
[9]	王晏民,郭明. 大规模点云数据的二三维混合索引方法[J]. 测绘学报, 2012, 41(4): 0-590.
[10]	龚俊,朱庆,张叶廷,李晓明,周东波. 顾及多细节层次的三维R树索引扩展方法[J]. 测绘学报, 2011, 40(2): 249-255.
[11]	童晓冲;贲进;秦志远;张永生 . 基于全球离散网格框架的局部网格划分[J]. 测绘学报, 2009, 38(6): 0-481.