Using space-filling curves to improve the quad tree for spatial indexing

Authors

  • Ali Abid Hussan Azeez Department of Computer Science, University of Technology, Baghdad, Iraq.
  • Rehab Flaih Hassan Department of Computer Science, University of Technology, Baghdad, Iraq.

DOI:

https://doi.org/10.29304/jqcm.2019.11.3.610

Keywords:

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.

Downloads

Download data is not yet available.

Downloads

Published

2019-09-10

How to Cite

Azeez, A. A. H., & Hassan, R. F. (2019). Using space-filling curves to improve the quad tree for spatial indexing. Journal of Al-Qadisiyah for Computer Science and Mathematics, 11(3), Comp Page 94–104. https://doi.org/10.29304/jqcm.2019.11.3.610

Issue

Section

Computer Articles