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