Quad-splitting algorithm for a window query on a Hilbert curve

Space-filling curves, particularly, Hilbert curves, have been extensively used to maintain spatial locality of multi-dimensional data in a wide variety of applications. A window query is an important query operation in spatial (image) databases. Given a Hilbert curve, a window query reports its corresponding orders without the need to decode all the points inside this window into the corresponding Hilbert orders. Given a query window of size p x q on a Hilbert curve of size T x T, Chung et al. have proposed an algorithm for decomposing a window into the corresponding Hilbert orders, which needs O(n log T) time, where n = max(p,q). By employing the properties of Hilbert curves, the authors present an efficient algorithm, named as Quad-Splitting, for decomposing a window into the corresponding Hilbert orders on a Hilbert curve without individual sorting and merging steps. Although the proposed algorithm also takes O(n log T ) time, it does not perform individual sorting and merging steps which are needed in Chung et al.'s algorithm. Therefore experimental results show that the Quad-Splitting algorithm outperforms Chung et al.'s algorithm.