STUDYING TECHNIQUES OF COMPUTATIONAL GEOMETRY  FOR TWO-DIMENSION RANGE SEARCH ALGORITHM  ASSISTING THE QUERY FOR DATABASE

Lê Thị Thuấn

doi:10.34238/tnu-jst.7336

STUDYING TECHNIQUES OF COMPUTATIONAL GEOMETRY FOR TWO-DIMENSION RANGE SEARCH ALGORITHM ASSISTING THE QUERY FOR DATABASE

About this article

Received: 15/02/23 Revised: 31/03/23 Published: 07/04/23

Authors

Le Thi Thuan , University of Khanh Hoa

Abstract

Nowadays, the rapid development of science and technology leads to the creation of enormous multimedia databases. Therefore, optimizing database queries has much attention from communication research. At ﬁrst sight it seems that databases have little to do with geometry. Nevertheless, queries about data in a database can be interpreted geometrically. To this end we transform records in a database into points in a multi-dimensional space, and we transform the queries about the records into queries on this set of points. This paper proposed an approach based on computational geometry techniques for building KD-trees, two-dimensional range search algorithm (search KD trees algorithm) and general sets of points to improve the algorithm. The algorithm also applies to data query optimization, a problem that is still challenging today. Applying build KD-trees algorithm and search KD-trees algorithm to build a search application on two-dimensional range search shows the potential of this research for many real-world problems related to database query optimization.

Keywords

Computational geometry; Range searching; KD-trees; General sets of points; Geometric data structures

Full Text:

PDF (Tiếng Việt)

References

[1] M. McKenney, R. Frye, M. Dellamano, K. Anderson, and J. Harris, “Multi-core parallelism for plane sweep algorithms as a foundation for GIS operations,” GeoInformatica, vol. 21, no. 1, pp. 151–174, 2017.

[2] H. Da, N. Alechins, M. Jackson, and Glen Hart, "A Method for Maching Caned arced and Authoritative Geospatial Data,” Transactions in GIS, vol. 21, no. 2, 2017, Art. no. 406427.

[3] A. Eldawy, Y. Li, M. F. Mokbel, and R. Janardan, “CG_Hadoop: computational Geometry in mapreduce,” in Proceedings of the international conference on advances in geographic information systems, ACM SIGSPATIAL, 2013, pp. 284–293.

[4] H. K. Chen and W. S. Chen, “GPU-accelerated blind and robust 3D mesh watermarking by geometry image,” Int. J. Multimedia Tools Appl., vol. 75, no. 16, pp. 10077–10096, 2016.

[5] K. G. Larsen and R. Williams, “Faster online matrix-vector multiplication,” in Proceedings of the 28th ACM–SIAM Symposium on Discrete Algorithms (SODA’17), SIAM, Philadelphia, 2017, pp. 2182–2189.

[6] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry, Springer, 2008.

[7] M. A. Mahmood, “A Proposed Hybrid Spatial Data Structure based on KD Tree and Quad Tree,” Jokull, vol. 69, no. 6, pp. 2-6, 2019.

[8] M. Otair, “Approximate K-Nearest Neighbour Based Spatial Clustering Using K-D Tree,” International Journal of Database Management Systems (IJDMS), vol. 5, no. 1, pp. 97-108, 2013.

[9] T. M. Chan and Z. Huang, “Dynamic Colored Orthogonal Range Searching,” Schloss Dagstuhl-Leibniz-Zentrum Informatik, vol. 204, pp. 1-13, 2021.

[10] T. M. Chan, “Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back,” Discrete & Computational Geometry, vol. 61, pp. 899–922, 2019.

[11] J. E. Goodman, J. O'Rourke, and C. D. Tóth, Handbook of Discrete and Computational Geometry, CRC Press LLC, 2017.

[12] M. Skrodzki, The k-d tree data structure and a proof for neighborhood computation in expected logarithmic time, Cornell University, 2019, doi: 10.48550/arXiv.1903.04936.

DOI: https://doi.org/10.34238/tnu-jst.7336

Refbacks

There are currently no refbacks.



Remember me