tailieunhanh - Do TPR* tree: A density optimal method for TPR* tree

This paper proposes a density optimal method, named as DO-TPR*-tree, which improves the performance of the original TPR*-tree significantly. In this proposed method, the search algorithm will enforce firing up MBR adjustment on a node, if the condition, based on density optimal for the area of its MBR, is satisfied at a query time. | Journal of Computer Science and Cybernetics, , (2015), 43–53 DOI: DO-TPR*-TREE: A DENSITY OPTIMAL METHOD FOR TPR*-TREE NGUYEN TIEN PHUONG1 , DANG VAN DUC2 Institute of Information Technology, Vietnam Academy of Science and Technology 1 phuongnt@; 2 dvduc@ Abstract. This paper proposes a density optimal method, named as DO-TPR*-tree, which improves the performance of the original TPR*-tree significantly. In this proposed method, the search algorithm will enforce firing up MBR adjustment on a node, if the condition, based on density optimal for the area of its MBR, is satisfied at a query time. So, all queries occurred after that time will be prevented from being misled as to an empty space of this node. The definition of Node Density Optimal is also introduced to be used in search algorithm. The algorithm of this method is proven to be correct in this paper. Several experiments and performed comparative evaluation are carried out. In the environment with less update rates (due to disconnected) or high query rates, the method can highly enhance query performance and runs the same as the TPR*-tree in other cases. Keywords. DO-TPR*-tree, MODB, R-tree, TPR-tree, TPR*- 1. INTRODUCTION The recent advances of technologies in mobile communications, GPS and GIS have increased users’ attention to an effective management of location information on the moving objects. Their location data has a spatio-temporal feature, which means spatial data is continuously changing over time [1]. So it needs to be stored in a database for efficient use. Such a database is commonly termed as the moving object database [2]. A moving object database is an extension of a traditional database management system that supports the storage of location data for continuous movement. The number of moving objects in the database can be very large. Therefore, to ensure the system performance while updating or processing queries, it is needed to reduce