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