NGHIÊN CỨU CÁC KỸ THUẬT CỦA HÌNH HỌC TÍNH TOÁN  CHO THUẬT TOÁN TÌM KIẾM PHẠM VI HAI CHIỀU  HỖ TRỢ BÀI TOÁN TRUY VẤN CƠ SỞ DỮ LIỆU

Lê Thị Thuấn

doi:10.34238/tnu-jst.7336

NGHIÊN CỨU CÁC KỸ THUẬT CỦA HÌNH HỌC TÍNH TOÁN CHO THUẬT TOÁN TÌM KIẾM PHẠM VI HAI CHIỀU HỖ TRỢ BÀI TOÁN TRUY VẤN CƠ SỞ DỮ LIỆU

Thông tin bài báo

Ngày nhận bài: 15/02/23 Ngày hoàn thiện: 31/03/23 Ngày đăng: 07/04/23

Các tác giả

Lê Thị Thuấn , Trường Đại học Khánh Hòa

Tóm tắt

Ngày nay, với sự phát triển mạnh về khoa học và công nghệ, cơ sở dữ liệu đa phương tiện ra đời với dung lượng rất lớn, vì vậy việc tối ưu hóa truy vấn dữ liệu là một bài toán nhận được sự quan tâm của các nhà nghiên cứu. Hãy xem xét mối tương quan giữa cơ sở dữ liệu với hình học bằng phương pháp chuyển đổi các bản ghi trong một cơ sở dữ liệu thành các điểm trong không gian đa chiều và chuyển đổi các truy vấn về các bản ghi thành các truy vấn lên tập các điểm này. Nghiên cứu đã ứng dụng các kỹ thuật của hình học tính toán để xây dựng cây KD và thuật toán tìm kiếm phạm vi 2 chiều - cây KD, đồng thời đề xuất phương pháp tập điểm chung để cải tiến thuật toán được đề xuất. Thuật toán được đề xuất sẽ áp dụng trong việc tối ưu hóa truy vấn dữ liệu, một vấn đề còn nhiều thách thức hiện nay. Áp dụng thuật toán để xây dựng chương trình tìm kiếm trên phạm vi hai chiều – cây KD cũng cho thấy tiềm năng của nghiên cứu này cho nhiều vấn đề trong thực tế liên quan đến bài toán tối ưu hóa truy vấn dữ liệu.

Từ khóa

Hình học tính toán; Phạm vi truy vấn; Cây KD; Tập điểm chung; Cấu trúc dữ liệu hình học

Toàn văn:

PDF

Tài liệu tham khảo

[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

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu



Ghi nhớ