Using space-filling curves to improve the quad tree for spatial indexing
DOI:
https://doi.org/10.29304/jqcm.2019.11.3.610Keywords:
Space filling curve,, quad trees,, Z-order curves,, Hilbert curve (H-curve),, multi-dimensional,, data structure.Abstract
Spatial indexes, like the ones that are based on Quad Tree, are important in spatial data-bases for the effective implementation of queries with spatial constraints, particularly in the case where queries include spatial links. The quad trees are a very interesting subject, given the fact that they give the ability to solve problems in a way that focuses only on the important areas with the highest density of information. But it is not without the disadvantages because the search process in the quartile suffers from the problem of repetition when reaching the terminal node and return to the behaviour of another way in the search and lead to the absorption of large amounts of time and storage. A database management system can handle data very easily if the object is one-dimension (sequential).
In this paper, improve the quad tree by combining one of the space filling curve types, including the Hilbert curve and the Z-ordering curve with a quad tree. It will convert from two-dimensional to one-dimensional and sequentially search and end the problem of repetition whenever it reaches a terminal node Ordinary quad tree. Resulting in reduced storage space requirements and improved implementation time.