一种基于迭代法的非均匀Hilbert空间填充曲线快速生成算法
A Fast Generation Algorithm of Non-uniform Hilbert Space-Filling Curve Based on an Iteration Approach
杨飞 1华一新 1杨振凯 1李响 1赵鑫科 1张晓楠2
作者信息
- 1. 信息工程大学地理空间信息学院,河南 郑州,450052
- 2. 空军航空大学航空基础学院,吉林 长春,130022
- 折叠
摘要
Hilbert空间填充曲线主要用于构建二维空间的数据索引,在实际应用中以均匀曲线为主.而现实中的空间数据分布通常具有显著的非均匀特征,使用均匀Hilbert曲线进行填充可能产生大量的编码冗余,降低空间索引效率,而现有的非均匀Hilbert曲线生成算法的实现和适用范围受到多种因素的约束.设计并实现了一种基于迭代法的非均匀Hilbert空间填充曲线快速生成算法,包含非均匀划分、子空间排序、中心点生成、连接线生成共4个子算法,依次实现对原始空间的非均匀划分和顺次编码排序,在此基础上连接各子空间的中心点,形成非均匀的Hilbert曲线.相比现有的均匀Hilbert曲线生成算法,所提算法充分顾及了空间数据的分布差异,支持自适应的空间划分,能够生成更轻量级的非均匀Hilbert曲线.相比现有的非均匀Hilbert曲线生成算法,所提算法可以通过程序实现,并能够较好地适用于空间信息检索及其他领域.实验结果表明,所提算法与现有算法相比,具有更广的应用范围、更低的空间消耗率、更高的编码排序效率和曲线生成效率,从而证明了所提算法的有效性与高效性.
Abstract
Objectives:The Hilbert space-filling curve is primarily employed for constructing data indices in 2D spaces,with a predominant utilization of uniform curves in practical applications.However,the distribu-tion of spatial data in real-world often exhibits a significant non-uniform character.The use of uniform Hilbert curves for space-filling may result in substantial encoding redundancy,thereby reducing the efficien-cy of spatial indexing.Furthermore,the implementation and applicability of the existing generation algo-rithms of non-uniform Hilbert curves are constrained by various factors.Methods:We design and imple-ment a fast generation algorithm of non-uniform Hilbert space-filling curve based on an iterative approach.Following the sequential steps in generation,the proposed algorithm includes four sub-algorithms,which are non-uniform partition,subspace sortation,centroid generation,and link generation.These sub-algo-rithms successively achieve non-uniform partition of the original space and sequential coding sortation.Sub-sequently,they connect the centroids of each subspace to form a non-uniform Hilbert curve.Results:Com-pared to the existing generation algorithms of uniform Hilbert curve,the proposed algorithm takes into full consideration of the differences in spatial data distribution,supports adaptive spatial partition,and generates more lightweight non-uniform Hilbert curves.Compared to the existing generation algorithms of the pro-posed non-uniform Hilbert curve,the proposed algorithm is programmatically implementable and well-suited for spatial information retrieval and other domains.Conclusions:Comparative experimental results demonstrate that the proposed algorithm can exhibit a broader range of applications,lower spatial consump-tion rates,higher efficiency in coding soration and curve generation.
关键词
空间信息检索/空间填充曲线/非均匀Hilbert曲线/迭代法/空间划分/空间分异性Key words
spatial information retrieval/space-filling curve/non-uniform Hilbert curve/iteration ap-proach/spatial partition/spatial differentiation引用本文复制引用
基金项目
国家重点研发计划(2016YFB0502300)
出版年
2024
NETL
NSTL
万方数据