MI-HCS: Monotonically Increasing Hilbert Code Segments for 3D Geospatial Query Window

Abstract

Window queries are basic but important query tasks in geospatial databases. The Hilbert curve has good clustering properties, which can be used to effectively improve the execution efficiency of window queries. The ideal goal of a window query using Hilbert curve code is to quickly convert the query window to the corresponding monotonic continuous Hilbert code segments. However, existing algorithms have shortcomings in conversion calculations and Hilbert code segments properties. We propose the state vectors that are used to describe the filling rules of a three-dimensional Hilbert curve. In addition, we designed a direct generation algorithm for monotonically increasing Hilbert code segments (MI-HCS) for a three-dimensional window query. The MI-HCS algorithm is characterized by the direct generation of a monotonically increasing code segment set without the need to traverse all grid elements or the requirement of separate sorting steps. For a given query window $W\left ({{x,y,z,l,w,h} }\right)$ and a Hilbert curve of size $T\times T\times T$ , the maximum complexity of our MI-HCS algorithm is $O\left ({{\alpha _{1} \times \alpha _{2} \times \left ({{\log _{2} T+1} }\right)} }\right)$ , where $\alpha _{1} = \textrm {median}\left ({{l,w,h} }\right)$ and $\alpha _{2} = \textrm {max}\left ({{l,w,h} }\right)$ . The experimental results of the MI-HCS algorithm complexity are consistent with the specific theoretical analysis. The experimental results show that the Hilbert code segment generation efficiency of the proposed MI-HCS algorithm is 260.5% to 423.9% higher than that of existing algorithms.

Keywords

• Hilbert curve
• octrees
• spatial ordering code
• window query