一种基于迭代法的非均匀Hilbert空间填充曲线快速生成算法

A Fast Generation Algorithm of Non-uniform Hilbert Space-Filling Curve Based on an Iteration Approach

Hilbert空间填充曲线主要用于构建二维空间的数据索引,在实际应用中以均匀曲线为主。而现实中的空间数据分布通常具有显著的非均匀特征,使用均匀Hilbert曲线进行填充可能产生大量的编码冗余,降低空间索引效率,而现有的非均匀Hilbert曲线生成算法的实现和适用范围受到多种因素的约束。设计并实现了一种基于迭代法的非均匀Hilbert空间填充曲线快速生成算法,包含非均匀划分、子空间排序、中心点生成、连接线生成共4个子算法,依次实现对原始空间的非均匀划分和顺次编码排序,在此基础上连接各子空间的中心点,形成非均匀的Hilbert曲线。相比现有的均匀Hilbert曲线生成算法,所提算法充分顾及了空间数据的分布差异,支持自适应的空间划分,能够生成更轻量级的非均匀Hilbert曲线。相比现有的非均匀Hilbert曲线生成算法,所提算法可以通过程序实现,并能够较好地适用于空间信息检索及其他领域。实验结果表明,所提算法与现有算法相比,具有更广的应用范围、更低的空间消耗率、更高的编码排序效率和曲线生成效率,从而证明了所提算法的有效性与高效性。

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 distribution 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 efficiency of spatial indexing.Furthermore,the implementation and applicability of the existing generation algorithms of non-uniform Hilbert curves are constrained by various factors.Methods We design and implement 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-algorithms successively achieve non-uniform partition of the original space and sequential coding sortation.Subsequently,they connect the centroids of each subspace to form a non-uniform Hilbert curve.Results Compared 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 proposed 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 consumption rates,higher efficiency in coding soration and curve generation.