Journal of Computer Science and Cybernetics, V.31, N.1 (2015), 43–53DOI: 10.15625/1813-9663/31/1/4630DO-TPR*-TREE: A DENSITY OPTIMAL METHOD FORTPR*-TREENGUYEN TIEN PHUONG1, DANG VAN DUC2Institute of Information Technology, This paper proposes a density optimal method, named as DO-TPR*-tree, which improvesthe performance of the original TPR*-tree significantly. In this proposed method, the search algorithmwill enforce firing up MBR adjustment on a node, if the condition, based on density optimal for thearea of its MBR, is satisfied at a query time. So, all queries occurred after that time will be preventedfrom being misled as to an empty space of this node. The definition of Node Density Optimal is alsointroduced to be used in search algorithm. The algorithm of this method is proven to be correctin this paper. Several experiments and performed comparative evaluation are carried out. In theenvironment with less update rates (due to disconnected) or high query rates, the method can highlyenhance query performance and runs the same as the TPR*-tree in other cases.Keywords. DO-TPR*-tree, MODB, R-tree, TPR-tree, TPR*-1. INTRODUCTIONThe 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 locationdata 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 asthe moving object database [2]. A moving object database is an extension of a traditional databasemanagement system that supports the storage of location data for continuous movement. The numberof moving objects in the database can be very large. Therefore, to ensure the system performancewhile updating or processing queries, it is needed to reduce the cost of object updates and have anefficient indexing method.Some efforts to reduce the cost of object updates have been proposed, such as the RUM-tree [3],or FD-tree [4]. The RUM-tree processes updates in a memo-based approach that avoids disk accessesfor purging old entries during an update process. Therefore, the cost of an update operation in theRUM-tree is reduced to the cost of only an insert operation [3]. Whereas, the FD-tree, a tree indexthat is aware of the hardware features of the flash disk (or SSD), has been proposed to optimize theupdate performance by reducing small random writes while preserving the search efficiency [4].Most of the indexing methods are based on the traditional spatial indexes, especially the R-tree[5], R*-tree [6] and its extension, which is typical TPR-tree [7]. Many efforts have been done topropose efficient index structures for future time queries, such as TPR*-tree [8]. The Bdual-tree [9]was presented to enhance the update performance of the previous methods. In particular, the Bdual-tree works well in the overall performance aspects. However, the TPR*-tree is reported to providea best performance in terms of the query processing times [9]. The research aims at improving thequery processing times, so this method will be compared with the TPR*-tree in section 4.c 2015 Vietnam Academy of Science & Technology44 NGUYEN TIEN PHUONG, DANG VAN DUCIn the TPR*-tree, the MBR adjustment is a solution to better performance, but its execution isonly fired up while having update operations. That is, the TPR*-tree cannot adjust the MBR of anode N, if no indexed object in N changes its location or velocity. The size of the empty space innode N enlarges continuously for a long time, if N is a node without updates. Therefore, if queryprocesses frequently searches into a sub-tree with rare updates, their response times will get longer.The goal of this paper is to introduce the density optimal method for TPR*-tree, named as DOTPR*-tree,which improves the performance of the original TPR*-tree significantly. In our proposedmethod, the search algorithm will enforce firing up MBR adjustment on N, if the condition, basedon density optimal for the area of N’s MBR, is satisfied at a query time. So, some of queries canbe prevented from being misled as to an empty space of N. The algorithm of the method is alsoproven to be correct in this paper. Several experiments are carried out for performance evaluation.The results show that in the environment with less update rates (due to disconnected) or high queryrates, this method is faster than the original method.This paper is organized as follows. Section 2 briefly reviews the TPR*-treeas related work, andthen introduces the research motivation. Section 3 proposes the method in detail. In the section4, the results of performance evaluation for justifying the effectiveness of our approach are shown.Finally, section 5 summarizes and concludes this paper.2. RELATED WORK AND RESEARCH MOTIVATION2.1. TPR-treeThe TPR-tree [7], which has been devised based on the R*-tree [6], predicts the future-time positionsof moving objects by storing the current position and velocity of each object at a specific time point.According to [8], a moving object Ois represents a minimum bounding rectangle (MBR)ORthat denotes its extent at reference time 0, and a velocity bounding rectangle (VBR) OV ={OV 1-,OV 1+,OV 2−,OV 2+} where OV i−(OV i+) describes the velocity of the lower (upper) boundary of ORalong the i-th dimension (1 ≤ i ≤ 2).2 NGUYEN TIEN PHUONG, DANG VAN DUCquery processing times [9]. The research aims at improving the query processing times, so this method willbe compared with the TPR*-tree in section 4.In the TPR*-tree, the MBR adjustment is a solution to better performance, but its execution is only firedup while having update operations. That is, the TPR*-tree cannot adjust the MBR of a node N, if noindexed object in N changes its location or velocity. The size of the empty space in node N enlargescontinuously for a long time, if N is a node without updates. Therefore, if query processes frequentlysearches into a sub-tree with rare updates, their response times will get longer.The goal of this paper is to introduce the density optimal method for TPR*-tree, named as DO-TPR*-tree, which improves the performance of the original TPR*-tree significantly. In our proposed method, thesearch algorithm will enforce firing up MBR adjustment on N, if the condition, based on density optimalfor the area of N’s MBR, is satisfied at a query time. So, some of queries can be prevented from beingmisled as to an empty space of N. The algorithm of the method is also proven to be correct in this paper.Several experiments are carried out for performance evaluation. The results show that in the environmentwith less update rates (due to disconnected) or high query rates, this method is faster than the originalmethod.This paper is organized as follows. Section 2 briefly reviews the TPR*-treeas related work, and thenintroduces the research motivation. Section 3 proposes the method in detail. In the section 4, the results ofperformance evaluation for justifying the effectiveness of our approach are shown. Finally, section 5summarizes and concludes this paper.2 RELATED WORK AND RESEARCH MOTIVATION2.1 TPR-treeThe TPR-tree [7], which has been devised based on the R*-tree [6], predicts the future-time positions ofmoving objects by storing the current position and velocity of each object at a specific time point.According to [8], a moving object Ois represents a minimum bounding rectangle (MBR)OR that denotesits extent at reference time 0, and a velocity bounding rectangle (VBR) OV={OV1-,OV1+,OV2-,OV2+} whereOVi-(OVi+) describes the velocity of the lower (upper) boundary of ORalong the i-th dimension (1 ≤ i ≤ 2).(a) MBRs & VBRs at time 0 (b) MBRs at time 1(a) MBRs & VBRs at time 02 NGUYEN TIEN PHUONG, DANG VAN DUCquery processing times [9]. The research aims at improving the query processing times, so this method willbe compared with the TPR*-tree in section 4.In the TPR*-tree, the MBR adjustment is a solution to better performance, but its execution is only firedup while having update operations. That is, the TPR*-tree cannot adjust the MBR of a node N, if noindexed object in N changes its location or velocity. The size of the empty space in node N enlargescontinuously for a long time, if N is a node without updates. Therefore, if query processes frequentlysearches into a sub-tree with rare updates, their response times will get longer.The goal of this paper is to introduce the density optimal method for TPR*-tree, named as DO-TPR*-tree, which improves the performance of the original TPR*-tree significantly. In our proposed method, thesearch algorithm will enforce firing up MBR adjustment on N, if the condition, based on density optimalfor the area of N’s MBR, is satisfied at a query time. So, some of queries can be prevented from beingmisled as to an empty space of N. The algorithm of the method is also proven to be correct in this paper.Several experiments are carried out for performance evaluation. The results show that in the environmentwith less update rates (due to disconnected) or high query rates, this method is faster than the originalmethod.This paper is organized as follows. Section 2 briefly reviews the TPR*-treeas related work, and thenintroduces the research motivation. Section 3 proposes the method in detail. In the section 4, the results ofperformance evaluation for justifying the effectiveness of our approach are shown. Finally, section 5summarizes and concludes this paper.2 RELATED WORK AND RESEARCH MOTIVATION2.1 TPR-treeThe TPR-tree [7], which has been devised based on the R*-tree [6], predicts the future-time positions ofmoving objects by storing the current position and velocity of each object at a specific time point.According to [8], a moving object Ois represents a minimum bounding rectangle (MBR)OR that denotesits extent at reference time 0, and a velocity bounding rectangle (VBR) OV={OV1-,OV1+,OV2-,OV2+} whereOVi-(OVi+) describes the velocity of the lower (upper) boundary of ORalong the i-th dimension (1 ≤ i ≤ 2).(a) MBRs & VBRs at time 0 (b) MBRs at time 1(b) MBRs at time 1Figure 1: Entry representations in a TPR-treeFigure 1a shows the MBRs and VBRs of 4 objects a, b, c, d. The arrows (numbers) denotethe directions (values) of their velocities, where a negative value implies that the velocity is towardsthe negative direction of an axis. The VBR of a is aV = {1, 1, 1, 1} (the first two numbers are forDO-TPR*-TREE: A DENSITY OPTIMAL METHOD FOR TPR*-TREE 45the x-dimension), while those of b, c, d are bV = { − 2, −2, −2, −2}, cV = { − 2, 0, 0, 2}, anddV = { − 1, −1, 1, 1} respectively. A non-leaf entry is also represented with a MBR and a VBR.Specifically, the MBR (VBR) tightly bounds the MBRs (VBRs) of the entries in its child node. InFigure 1, the objects are clustered into two leaf nodes N1, N2, whose VBRs are N1V = {−2, 1, −2, 1}and N2V = { − 2, 0, −1, 2} (their directions are indicated using white arrows).Figure 1b shows the MBRs at timestamp 1 (notice that each edge moves according to its velocity).The MBR of a non-leaf entry always encloses those of the objects in its sub-tree, but it is notnecessarily tight. For example, N1(N2) at timestamp 1 is much larger than the tightest boundingrectangle for a, b (c, d). A predictive window query is answered in the same way as in the R*-tree,except that it is compared with the (dynamically computed) MBRs at the query time. For example,the query qR at timestamp 1 in Fig. 1b visits both N1 and N2 (although it does not intersect themat time 0). When an object is inserted or removed, the TPR-tree tightens the MBR of its parentnode.2.2. TPR*-treeThe data structure and the query processing algorithm of the TPR*-tree [8] are similar to those ofthe TPR-tree. A difference between them is the insertion algorithm. That is, the TPR-tree usesthe original insertion algorithm of the R*-tree without modification, while the TPR*-tree makes amodification in order to reflect the mobility of objects.In the insertion algorithm, the TPR-tree assesses the overall changes of the area and perimeterof MBRs, and the overlapping regions among MBRs that are caused by this object insertion. Bychoosing the tree-path where such changes remain smallest, the TPR-tree brings the least spacepossible. This approach can be very efficient for indexing static objects as in the R*-tree, but itcannot be a good solution to moving objects. Because the TPR-tree does not consider the timeparameter, it estimates the MBR changes only found at the insertion time without considering thetime-dependent sizes of the BRs. To resolve these omissions, the TPR*-tree revised the insertionalgorithm to reflect the characteristic of time-varying BRs, which result from the mobility of objects.In the insertion algorithm, the TPR*-tree considers how much the BR will sweep the index spacefrom the insertion time to a specific future-time and chooses the insertion paths that the sweepingregion remains smallest. The sweeping region of a BR from time t1 to t2 (t1 an index space area that is swept by the BR expanding during the time interval (t2 − t1). Fig. 2shows an example of a sweeping region of an object o in the TPR*-tree. At the initial time 0, wehave the BR of O is OR(0). Until time 1, the BR of O is OR(1). Sweeping region of o from time 0to 1 is the gray-filled polygon below.With this strategy, the TPR*-tree may consume more CPU time for inserts than the TPR-tree.However, it greatly improves the overall query performance (up to five times [8]) for the future-timequeries because it compacts the MBRs.2.3. Research MotivationIn the TPR*-tree, the VBR stores the maximum and minimum velocity of moving objects in theMBR. So the MBR enlarges at a fast and continuous rate. It leads to a large empty space and causesoverlaps among nodes’ MBRs as time goes on (see Fig. 1b above). It may reduce the performance ofquery processing because of increasing number of node accesses that require for query processing (qRin Fig. 1b above has unnecessary node access to N1 and N2). To resolve this problem, the TPR*-tree46 NGUYEN TIEN PHUONG, DANG VAN DUC4 NGUYEN TIEN PHUONG, DANG VAN DUCFigure 2: Sweeping region of moving object o (from time 0 to time 1)With this strategy, the TPR*-tree may consume more CPU time for inserts than the TPR-tree. However,it greatly improves the overall query performance (up to five times [8]) for the future-time queries becauseit compacts the MBRs.2.3 Research MotivationIn the TPR*-tree, the VBR stores the maximum and minimum velocity of moving objects in the MBR. Sothe MBR enlarges at a fast and continuous rate. It leads to a large empty space and causes overlaps amongnodes’ MBRs as time goes on (see fig. 1b above). It may reduce the performance of query processingbecause of increasing number of node accesses that require for query processing (qR in fig. 1b above hasunnecessary node access to N1 and N2). To resolve this problem, the TPR*-tree executes MBR adjustmenton a node whenever object’s velocity or position have explicitly changed.(a) Time 0 (b) Time 1Figure 3: MBR R at the initial time 0 and its expansion R1 at time 1Fig. 3 illustrates the benefit of the MBR adjustment. In Fig. 3a, a MBR is created or updated to capturethe objects of O1 and O2 at time 0 and its MBR is denoted by rectangle R. Fig. 3b depicts the positions ofFigure 2: Sweeping region of moving object o (from time 0 to time 1)executes MBR adjustment on a node whenever object’s velocity or posi代写10.15625、MBR代做、代写R编程设计、代做R设计tion have explicitly changed.4 NGUYEN TIEN PHUONG, DANG VAN DUCFigure 2: Sweeping region of moving object o (from time 0 to time 1)With this strategy, the TPR*-tree may consume more CPU time for inserts than the TPR-tree. However,it greatly improves the overall query performance (up to five times [8]) for the future-time queries becauseit compacts the MBRs.2.3 Research MotivationIn the TPR*-tree, the VBR stores the maximum and minimum velocity of moving objects in the MBR. Sothe MBR enlarges at a fast and continuous rate. It leads to a large empty space and causes overlaps amongnodes’ MBRs as time goes on (see fig. 1b above). It may reduce the performance of query processingbecause of increasing number of node accesses that require for query processing (qR in fig. 1b above hasunnecessary node access to N1 and N2). To resolve this problem, the TPR*-tree executes MBR adjustmenton a node whenever object’s velocity or position have explicitly changed.(a) Time 0 (b) Time 1Figure 3: MBR R at the initial time 0 and its expansion R1 at time 1Fig. 3 illustrates the benefit of the MBR adjustment. In Fig. 3a, a MBR is created or updated to capturethe objects of O1 and O2 at time 0 and its MBR is denoted by rectangle R. Fig. 3b depicts the positions of(a) Time 04 NGUYEN TIEN PHUONG, DANG VAN DUCFigure 2: Sweeping region of moving object o (from time 0 to time 1)With this strategy, the TPR*-tree may consume more CPU time for inserts than the TPR-tree. However,it greatly improves the overall query performance (up to five times [8]) for the future-time queries becauseit compacts the MBRs.2.3 Research MotivationIn the TPR*-tree, the VBR stores the maximum and minimum velocity of moving objects in the MBR. Sothe MBR enlarges at a fast and continuous rate. It leads to a large empty space and causes overlaps amongnodes’ MBRs as time goes on (see fig. 1b above). It may reduce the performance of query processingbecause of increasing number of node accesses that require for query processing (qR in fig. 1b above hasunnecessary node access to N1 and N2). To resolve this problem, the TPR*-tree executes MBR adjustmenton a node whenever object’s velocity or position have explicitly changed.(a) Time 0 (b) Time 1Figure 3: MBR R at the initial time 0 and its expansion R1 at time 1Fig. 3 illustrates the benefit of the MBR adjustment. In Fig. 3a, a MBR is created or updated to capturethe objects of O1 and O2 at time 0 and its MBR is denoted by rectangle R. Fig. 3b depicts the positions of(b) Time 1Figure 3: MBR R at the initial time 0 and its expansion R1 at time 1Fig. 3 illustrates the benefit of the MBR adjustment. In Fig. 3a, a MBR is created or updated tocapture the objects of O1 and O2 at time 0 and its MBR is denoted by rectangle R. Fig. 3b depictsthe positions of those objects after the time interval of 1. Objects O1 and O2 moved closely to eachother. If a MBR adjustment arises at time 1 because of updating a node, a smaller MBR will beavailable (R0in Fig. 3b). In contrast, the predicted MBR will become a larger rectangle (R1 of Fig.3b). Therefore, the empty space of R1 − R0can be eliminated. In other words, some unnecessarynode access to the area of R1 − R0can be eliminated in the near future.The MBR adjustment is a solution to better performance, but its execution is only fired up whilehaving update operations. That is, the TPR*-tree cannot adjust the MBR of a node N, if no indexedobject in N changes its location or velocity (due to disconnected). Otherwise, the size of empty spacein node N enlarges continuously for a long time, if N is a node without updates. Therefore, if queryprocesses frequently searches into a sub-tree with rare updates, their response times will get longer.To overcome such a problem, a new method with a new tree based on TPR*-tree is proposed, namedas DO-TPR*-tree, enabling the query process to do the MBR adjustment in an efficient manner.DO-TPR*-TREE: A DENSITY OPTIMAL METHOD FOR TPR*-TREE 473. THE PROPOSED METHODIn this section, a new method for improving the query performance in the TPR*-tree is proposed.At first, the technique is presented in section 3.1. Then section 3.2 shows the detailed algorithm.3.1. Method DescriptionIn this section, the technique for the proposed method is described. Denote P is a query process, Nis a leaf node that Preached and Tujand Tuj+1 are the jth and the (j + 1)th update times when theMBR adjustments occur on N, respectively. Assuming that there are kuser queries accessing N in[Tuj, Tuj+1 ] and P, is the ith query process, happens to arrives at N during the period from TujtoTuj+1 . Denote the user query having released P by Qj,i, that is, Qj,i is the ith user query accessingN. Let Tqj,i be the access time of Qj,i to N resulting in an arrival sequence as below.Tuj Because the MBR of Nenlarges continuously during [Tuj, Tuj+1 ], the user queries at Tqj,i (1 ≤i ≤ k) will view the growing MBR of Nand thus the possibility of their misleading to Nincreasesduring that interval. Note that if there is any query having an overlap between its target query regionand the empty space of N, then the query will uselessly access Nbecause of misleading.With the observation above, it is now back to the situation when the query process of Qj,i arrivesat N. If this process is able to do its MBR adjustment on Nat time Tqj,i , then some of the queriesQj,x(i¡x ≤ k) can be prevented from being misled as to an empty space of N during [Tqj,i , Tuj+1 ].In proposed method, the search algorithm will enforce firing up MBR adjustment on N, if thecondition, based on density optimal for the area of N0s MBR, is satisfied at time Tqj,i . Two definitionsare introduced to be used in the following search algorithm.Definition 1 (Node Density). Given N is a node of TPR*-tree. Node Density of N is thenumber of entries per unit of the area of N’s MBR. Node Density of Nat time T, denotedDN (T), is the number of entries per unit of the area of N’s MBR at time T.DN (T) = Num EN (T)ABRN (T)(1)where, Num EN (T) is the number of the entries inside N at time T. If N is a leaf node,Num EN (T)is the number of all moving objects inside N. ABRN (T) is the area of N’s MBRat time T.Definition 2 (Node Density Optimal). Node Density of N at query time Tq is called optimalif its ratio and Node Density of Nat the last update time Tu is smaller than a given number λ.DN (Tq)DN (Tu)where, DN (Tq) is Node Density of N at query time Tq, DN (Tu) is Node Density of N atthe last update time Tu, λ is a given number, depending on the specific application. Inthe Vehicle Management System, λ should be h − 1, h is the tree height, according to ourevaluation.48 NGUYEN TIEN PHUONG, DANG VAN DUCIn the search algorithm of our proposed method, Node Density Optimal condition (2) of N ischecked while user queries are being at time Tqj,i . If not, MBR adjustments arise on N. So, allqueries Qj,x(i space of N during [Tqj,i , Tuj+1 ]. From that, the number of useless node access to N can be reduced.Thus, it improves the query performance of the TPR*-tree. When checking formula (2) the MBRadjustment is called Density Optimal Adjustment (DOA). The tree in density method is based onTPR*-tree, so it is called DO-TPR*-tree. Details about this DOA and the search algorithm for thequery process are presented in the next section.3.2. AlgorithmAlgorithms for node insertion and deletion are identical with the previous ones in [8]. According to[8], the insertion algorithm first identifies the leaf N that will accommodate ewith the choose pathalgorithm in line 3. If N is full, a set of entries, selected by pick worst, is removed from N andre-inserted in line 7.6 NGUYEN TIEN PHUONG, DANG VAN DUCDN (T) =(1)Where, Num_EN(T) is the number of the entries inside N at time T. If N is a leaf node, Num_EN(T)is the number of all moving objects inside N ABRN(T) is the area of N’s MBR at time TDEFINITION 3.2 (Node Density Optimal): Node Density of N at query time Tq is called optimal if itsratio and Node Density of N at the last update time Tu is smaller than a given number λ.Where, is Node Density of N at query time Tq is Node Density of N at the last update time Tu λ is a given number, depending on the specific application. In the Vehicle ManagementSystem, λ should be h-1, h is the tree height, according to our evaluation.In the search algorithm of our proposed method, Node Density Optimal condition (2) of N is checkedwhile user queries are being at time. If not, MBR adjustments arise on N. So, all queries Qj,x(ithat occur after time will be prevented from being misled as to an empty space of N during [,]. From that, the number of useless node access to N can be reduced. Thus, it improves the queryperformance of the TPR*-tree. When checking formula (2) the MBR adjustment is called Density OptimalAdjustment (DOA). The tree in density method is based on TPR*-tree, so it is called DO-TPR*-tree.Details about this DOA and the search algorithm for the query process are presented in the next section.3.2 AlgorithmAlgorithms for node insertion and deletion are identical with the previous ones in [8]. According to [8], theinsertion algorithm first identifies the leaf N that will accommodate e with the choose path algorithm inline 3. If N is full, a set of entries, selected by pick worst, is removed from N and re-inserted in line 7.Figure 4: Insert algorithmAlgorithm Insert (e)Input: e is the entry to be insertedOutput: Inserted e into Node N1. re-insertedi= false for all levels 1≤ i ≤ h−1 (h is the tree height)2. Initialize an empty re-insertion list Lreinsert3. Invoke Choose Path to find the leaf node N to insert e4. Invoke Node Insert (N, e)5. For each entry e in the Lreinsert6. Invoke Choose Path to find the leaf node N to insert e7. Invoke Node Insert (N, e)8. End forAlgorithm End.Figure 4: Insert algorithmA future-time query from a user is expressed in the form of (QBR, QT ). Here, QBR denotesthe query target region (includes MBR and VBR) in the 2-dimensional query space, and QT is thetarget query time interval of that query (includes start time and end time). The future-time queryis answered by predicting the moving objects that will pass QBR during the interval of QT . Theproposed search algorithm is given in Fig. 4, where it returns a set of object ids satisfying a query of(QBR, QT ).The algorithm searches down for the leaf level from the root node. During the downward search,the search process finds its search paths by computing the BRs from each entry e in the internal nodes.In the meantime, the process will cache the encountered BR data as in line 11. When arriving at aleaf node in line 5, this algorithm selects a group of object id’s satisfying the given query condition,and return them in line 21.Theorem 1 (Algorithm DOA Search is correct). Algorithm DOA Search returns the completeset of intersecting valid objects.Proof. Every node of the tree is traversed. This can be seen in line 3 (every leaf node) andin line 9 (every non-leaf node) (i).DO-TPR*-TREE: A DENSITY OPTIMAL METHOD FOR TPR*-TREE 49DO-TPR*-TREE: A DENSITY OPTIMAL METHOD FOR TPR*-TREE 7A future-time query from a user is expressed in the form of (QBR, QT). Here, QBR denotes the querytarget region (includes MBR and VBR) in the 2-dimensional query space, and QT is the target query timeinterval of that query (includes start time and end time). The future-time query is answered by predictingthe moving objects that will pass QBR during the interval of QT. The proposed search algorithm is given inFig. 4, where it returns a set of object ids satisfying a query of (QBR, QT).Figure 5: Proposed Search algorithm for the query processThe algorithm searches down for the leaf level from the root node. During the downward search, thesearch process finds its search paths by computing the BRs from each entry e in the internal nodes. In themeantime, the process will cache the encountered BR data as in line 11. When arriving at a leaf node inline 5, this algorithm selects a group of object id’s satisfying the given query condition, and return them inline 21.Algorithm DOA_Search(QBR, QT, rootNode)Input: (QBR, QT) = future-time query answered.rootNode= address to the root of a sub-tree being searched.Output:SBR= objects’ ids satisfying (QBR, QT).1. IF rootNode is a leaf node THEN2. SBR←; // initialization3. FOR EACH moving object O in rootNode4. IF OIN (QBR, QT) THEN //O is expected computed to be positioned d in QBR within intervalQT5. SBR= SBR O.id;6. END IF7. END FOR8. ELSE // rootNode is a non-leaf node9. FOR EACH index entry e in rootNode10. IF OVERLAP(e.MBR,QBR,QT) THEN // if there is an overlap between the MBR of e and QBRwithin QT11. Cache(e); // cache the content of e into the memory buffer12. nodeDensity = Cal_NodeDensity(e.childNode); // calculate the Node Density of thechild node pointed to by e13. λ = h-1; // h is the tree height14. IF (nodeDensity>= λ) THEN // an DOA execution is needed on childNode15. Adjust (e.MBR, e.VBR); // adjust the MBR and VBR data of e16. END IF17. childSBR←DOA_Search(QBR, QT, childNode);18. SBR← SBRchildSBR;19. END IF20. END FOR21. RETURN SBR22. END IFAlgorithm End.Figure 5: Proposed Search algorithm for the query processFor every leaf node traversed, all of its objects which locate in query region at query timeinterval are inserted into the result set of the corresponding query. This can be seen fromline 4 to 5 (ii).For every non-leaf node traversed, all of its entries which intersect at least one of therange queries arerecursive searched to find the satisfy leaf nodeand inserted into the resultset of the corresponding query (iii).The algorithm terminates when all the nodes in the tree are traversed (iv).From (i), (ii), (iii) and (iv) we have proved that DOA Search algorithm is correct.We next estimate the performance in our method according to the range query size andcompare it with the original TPR*-tree.4. EXPERIMENTIn this section, the query processing performance between this proposed method and the originalTPR*-tree is compared. From the experiment comparisons, the performance advantages of the proposedmethod over the TPR*-tree are shown.4.1. Experiment dataThe experimental datasets is generated by using an algorithm same as GSTD (Generating SpatioTemporalDatasets) [10], a well-known data generator used in many previous researches on perfor-50 NGUYEN TIEN PHUONG, DANG VAN DUCmance evaluations of the index schemes for moving objects [11, 12]. With this algorithm, four datasetsinclude [1000, 10000, 50000, 100,000] moving objects are generated with a random velocity each inthe range of [-50, 50] and maximum velocity changes in each update to 5. Those objects are simulatedto move around within the normalized 2-dimensional query space of the size 0 by 10,000. In thatquery space, an object is represented as a point and its initial position is uniform distribution.Data file was created as a text file containing the records of the object. The objects were randomlygenerated at time points t0 (including identification, minimum bounding rectangle, velocity, referencetime of object). At time t1, t2, t3,... random number of objects are generated with velocity changes.Detail of the record is described as a s转自：http://www.3daixie.com/contents/11/3444.html