W-Hilbert: A W-shaped Hilbert curve and coding method for multiscale geospatial data index

Abstract

Space-filling curves (SFCs) are commonly used in discrete global grid systems (DGGSs) and applied to efficient indices and queries of massive geospatial data. Although Hilbert curves have the best locality preservation and clustering properties among SFCs, they have two major problems when applied to a multiscale data index or query. (1) Poor clustering in multiscale space reduces the index efficiency, and (2) the complexity of the child-code calculation reduces the query efficiency. We propose a multiscale W-shaped Hilbert curve (W-Hilbert) with its coding and calculation methods to solve these problems. We conducted three comparative experiments with the existing multiscale U-shaped Hilbert curve (U-Hilbert). (1) W-Hilbert demonstrated more satisfactory clustering properties in the multiscale grid space than U-Hilbert. (2) The average child-code query efficiency of W-Hilbert was 2.84 times that of U-Hilbert. (3) For the spatial index and query of multiscale urban building data, the average spatial query efficiency of W-Hilbert was 52.22% higher than that of U-Hilbert. Overall, W-Hilbert is an effective method for massive geospatial data index and management.

Keywords

• Discrete global grid system
• Hilbert curve
• Multiscale
• Clustering property
• Spatial index