Enhancing Quad Tree for Spatial Index Using Space Filling Curves

Abstract

Spatial indexes, such as those based on the Quad Tree, are important in spatial databases for the effective implementation of queries with spatial constraints, especially when queries involve spatial links. The quaternary 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. Nevertheless, it is not without the disadvantages because the search process in the quad tree suffers from the problem of repetition when reaching the terminal node and return to the behavior of another way in the search and lead to the absorption of large amounts of time and storage. In this paper, the quad tree was improved by combining it with one of the space filling curve types, resulting in reduced storage space requirements and improved implementation time

Keywords

• quad trees
• space filling curves
• spatial index
• z-order curves
• hilbert curves