The Research On Hierarchical Evolution Relationship And Grid Index Of Three-dimensional Hilbert Curve

The Discrete Global Grid System(DGGS)is a new global-oriented multi-resolution data fusion and geoscience simulation solution with grid coding and its operation as the core.Space filling curve(SFC)is a one-dimensional curve that can recursively cover a specified area,which is an important approach for designing discrete global grid coding.Based on extensive researches and application comparisons,it can be found that the Hilbert SFC has been widely applied thank to its greatest spatial clustering.However,problems such as high computation complexity and low efficiency can be detected when the existing Hilbert space permutation code operation method is applied for achieving coordinate conversion,proximity search,window query and the like grid space computation.This paper studies the three-dimensional Hilbert curve spatial permutation code operation approach and its application in the discrete global grid index with the hierarchical evolution relationship of the three-dimensional Hilbert curve as a starting point.Main contents of the paper are presented as follows:1.The concept of state vector is proposed against the formal description of the hierarchical evolution relationship of the 3D Hilbert curve,so as to record the filling state of the 3D Hilbert curve.On this basis,the mapping relationship between the state vector between the upper and lower hierarchies can be derived,so that the formal description of the evolution relationship can be accomplished with the state matrix and the evolution matrix.State and evolution matrices are applied to the conversion of spatial coordinates to Hilbert code for improving the existing algorithm.The proposed algorithm is proved to be less time-consuming in conversion with higher efficiency in converting spatial coordinate to Hilbert code,according to the comparative experiment conducted with the existing algorithm.2.A new method for computing the proximity grid Hilbert code is proposed on the basis of searching for a common parent grid element,so as to address the problem of low computational efficiency of the existing proximity grid Hilbert code.Based on the hierarchical subjection and spatial topology attributes implicitly included in the Hilbert code,the proposed method is to compute the proximity grid Hilbert code through looking for the common parent grid element,rather than converting the Hilbert code into coordinates or permutation code in other forms like the existing algorithm.The experimental results show that the conversion algorithm of the proposed method with higher efficiency in conversion is more in line with the requirement of fast proximity query.3.Targeted at the problem of conversing from the query window to the Hilbert code segment,the filling starting rule of Hilbert sub-curve is firstly analyzed.And then,the spatial topological relationship of the octagonal molecular window is analyzed quantitatively.On this basis,a monotone increasing code segment directly-generating algorithm is put forward.Compared with the existing traversal algorithm,the proposed algorithm has a significantly-decreased number of computations with greater improvement in efficiency without traversing all grid elements for solving.In addition,compared with the multi-dimensional tree algorithm,the proposed algorithm can directly generate monotone increasing code segments without performing additional sort operations on the code segments,making it more efficient to be used with one-dimensional indexing technologies such as B+ tree.The advantages of complexity and efficiency of the proposed algorithm are verified from theoretical analysis and comparative experiments.4.A spatio-temporal data index ST-Hcode based on Hilbert code is proposed against the problem of applying grid data index based on Hilbert code,by taking spatio-temporal data as an example.To begin with,a global spatio-temporal multi-resolution grid model was constructed by loop nesting subdivision;then,index organization was performed on spatio-temporal data with Hilbert code as the key value based on the three-dimensional Hilbert curve;finally,a data query method corresponding to the proposed Hilbert space permutation code algorithm was designed.Moreover,a number of comparative experiments were designed to test the performance and efficiency of the ST-Hcode index.According to the experimental result,the ST-Hcode index can better maintain the spatio-temporal proximity and show higher query efficiency in real data sets in comparison to the existing method.