A Fast Generation Algorithm of Non-uniform Hilbert Space-Filling Curve Based on an Iteration Approach
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.
spatial information retrievalspace-filling curvenon-uniform Hilbert curveiteration ap-proachspatial partitionspatial differentiation
NETL
NSTL
万方数据
