Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian
Main Article Content
Abstract
Tóm tắt. Bài báo này đề cập đến khái niệm và một số phương pháp đánh chỉ mục trong cơ sở dữ liệu không gian (spatial datadase – SDB). Là một trong những mô hình cơ sở dữ liệu được quan tâm hiện nay, SDB cho phép xử lý các đối tượng dữ liệu không gian, chẳng hạn dữ liệu bản đồ, dữ liệu multimedia... để từ đó có thể xây dựng nên những kho dữ liệu không gian. Một trong những bài toán cơ bản trong SDB chính là việc tối ưu hoá quá trình lưu trữ dữ liệu và truy vấn. Trong bài báo này, chúng tôi sẽ trình bày về hai phương pháp đánh chỉ mục điển hình liên quan đến vấn đề đánh chỉ mục giải bài toán trên, R-tree và Q-tree. Từ đó, ý tưởng kết hợp hai phương pháp này sẽ chính là định hướng chủ đạo cho việc tối ưu hoá lưu trữ dữ liệu cũng như truy vấn trên cơ sở dữ liệu không gian.
Từ khóa: Spatial database, spatial indexing, R-tree, Q-tree, QR-Tree.References
[2] Manolopoulos, Y. (1996). QR-tree-a hybrid spatial data structure, Proceedings of the 1st International Conference on Geographic Information Systems in Urban, Regional and Environmental Planning, Samos Island, Greece, pp. 3–7.
[3] Rauber A., Tomish P., Riedel H., and Kouba Z. Integrating Geo-Spatial Data into OLAP Systems Using a Set-based Quad-Tree Representation. In Proc. of the 4th Int. Conf. onInformation technology for Balanced Automation Systems in Production and Transportation, BASYS, 2000.
[4] D. Pfoser, C. S .Jensen, and Y. Theodoridis. Novel approaches in query processing for moving objects. Proceedings of the 26th International Conference on Very Large Databases (VLDB), September 2000.
[5] Papdias D., Kalnis P., Zhang J., and Tao Y. Efficient OLAP Operations in Spatial Data Warehouse. In Proc. of the 6th International Symposium on Spatial and Temporal Databases, SSTD, 2001.
[6] K. Chakarabarti and S.Mehrotra. The hybrid tree: An index structure for high dimensional feature spaces. Proceedings of he Fourteenth International Conference on data engineering (ICDE’99), 1999.
Yuni Xia, Sunil Prabhakar. Q+Rtree: Efficient Indexing for Moving Object Databases. In Proc. of the 8th International Symposium on Spatial and Temporal Databases, SSTD, 2004.