Enhancing Quad Tree for Spatial Index Using Space Filling Curves

Hussain, Ali A.; Hassan, Rehab F.

doi:10.30684/etj.v38i1B.264

	Enhancing Quad Tree for Spatial Index Using Space Filling Curves
Engineering and Technology Journal
Article 3, Volume 38, 1B, 2020, Pages 15-25 PDF (1.27 M)
DOI: 10.30684/etj.v38i1B.264
Authors
Ali A. Hussain¹; Rehab F. Hassan²
¹Department of Computer Science, University of Technology, Baghdad, Iraq
²Department Computer Science, University of Technology, Baghdad, Iraq
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

References
[1] M. M. Sardadi, M. M. Rahim, Z. Jupri, D. Daman, “Quad tree spatial indexing use to make faster showing geographical map in mobile geographical information system technology using an oracle 10g application server and map viewer applications,” IJCSNS International Journal, Vol.8, No.10, 81310, 2008. [2] S. S. Baboo, V.Narmadha, “Efficient data storage and searching for location based services using quad trees and H-ordering,” International Journal of Computer Science and Mobile Computing, Vol.3 Issue.4, 810-816, 2014. [3] M.M. Sardadi, M.S. Mohd Rahim, Z. Jupri, D. Daman, “Choosing R-tree or quad tree spatial data indexing in one oracle spatial database system to make faster showing geographical map in mobile geographical information system technology,” International Journal of Humanities and Social Sciences, 2009. [4] H. Lim, C. Yim, E. S. lander, “Priority Area-based quad-tree packet classification algorithm and its mathematical framework,” International Journal Applied Mathematics & Information Sciences Appl. Konkuk University, Math. Inf. Sci. 7, No. 1, 2013. [5] G. S. Kumar, D. N. Kumar, A. V. Paramkusam, “A fast motion estimation algorithm based on hybrid quad tree structure,” International Journal of Mechanical Engineering and Technology (IJMET), Volume 8, Issue 7, July 2017, 642–648, Article ID: IJMET_08_07_072, 2017. [6] X. G. Zhou, H. S. Wang, “A quad tree spatial index method with inclusion relation for the incremental updating of vector land cover Database,” The International Archives of the Photogrammetry, Remote Sensing and Spatial, Information Sciences, Volume XLII-4, 2018 [7] F. Hou, C. Huang, J. Lu, “A multi-dimensional data storage using quad-tree and Z-ordering,” International Conference on Computer Science and Electronics Engineering (ICCSEE), 2013. [8] N. Xiao, “GIS algorithms theory and applications for geographic information science & technology,” California, USA, ISBN 978-1-4462-7432-3, 2016. [9] S. SIERANOJA, P. Frenti, “Constructing a high-dimensional kNN-graph using a Z-order curve,” International Journal of Mechanical Engineering and Technology (IJMET), Volume 8, Issue 7, Hyderabad, Telangana, India, pp. 642–648, 2018. [10] H. Haverkort, S. Thite, L. Toma, “Star-quad trees and guard-quad trees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions,” Computational Geometry 43, 493–513, 2010. [11] S. W. Qasem, A. A Touir, “Cardinal neighbor quad tree: a new quad tree-based structure for constant-time neighbor finding,” International Journal of Computer Applications, Vol. 132, No.8, 0975- 8887, 2015.
Statistics Article View: 352 PDF Download: 432