Compact Hilbert Curve Index Algorithm Based on Gray Code

doi:10.11947/j.AGCS.2016.F010

Abstract

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

CLC Number:

P208

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.

References

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