Journal of Computer Science and Cybernetics, V.31, N.1 (2015), 43–53
DOI: 10.15625/1813-9663/31/1/4630
DO-TPR*-TREE: A DENSITY OPTIMAL METHOD FOR
TPR*-TREE
NGUYEN TIEN PHUONG1
, DANG VAN DUC2
Institute of Information Technology, 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 the cost of object updates and have an
efficient 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 accesses
for purging old entries during an update process. Therefore, the cost of an update operation in the
RUM-tree is reduced to the cost of only an insert operation [3]. Whereas, the FD-tree, a tree index
that is aware of the hardware features of the flash disk (or SSD), has been proposed to optimize the
update 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 to
propose 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 provide
a best performance in terms of the query processing times [9]. The research aims at improving the
query processing times, so this method will be compared with the TPR*-tree in section 4.
c 2015 Vietnam Academy of Science & Technology
44 NGUYEN TIEN PHUONG, DANG VAN DUC
In the TPR*-tree, the MBR adjustment is a solution to better performance, but its execution is
only fired up while having update operations. That is, the TPR*-tree cannot adjust the MBR of a
node N, if no indexed object in N changes its location or velocity. The size of the empty space in
node N enlarges continuously for a long time, if N is a node without updates. Therefore, if query
processes 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 proposed
method, the search algorithm will enforce firing up MBR adjustment on N, if the condition, based
on density optimal for the area of N’s MBR, is satisfied at a query time. So, some of queries can
be prevented from being misled 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 environment with less update rates (due to disconnected) or high query
rates, this method is faster than the original method.
This paper is organized as follows. Section 2 briefly reviews the TPR*-treeas related work, and
then introduces the research motivation. Section 3 proposes the method in detail. In the section
4, 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 MOTIVATION
2.1. TPR-tree
The TPR-tree [7], which has been devised based on the R*-tree [6], predicts the future-time positions
of 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)OR
that 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 OR
along the i-th dimension (1 ≤ i ≤ 2).
2 NGUYEN TIEN PHUONG, DANG VAN DUC
query processing times [9]. The research aims at improving the query processing times, so this method will
be 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 fired
up while having update operations. That is, the TPR*-tree cannot adjust the MBR of a node N, if no
indexed object in N changes its location or velocity. The size of the empty space in node N enlarges
continuously for a long time, if N is a node without updates. Therefore, if query processes 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 DO-TPR*-
tree, which improves the performance of the original TPR*-tree significantly. In our proposed method, the
search algorithm will enforce firing up MBR adjustment on N, if the condition, based on density optimal
for the area of N’s MBR, is satisfied at a query time. So, some of queries can be prevented from being
misled 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 environment
with less update rates (due to disconnected) or high query rates, this method is faster than the original
method.
This paper is organized as follows. Section 2 briefly reviews the TPR*-treeas related work, and then
introduces the research motivation. Section 3 proposes the method in detail. In the section 4, 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 MOTIVATION
2.1 TPR-tree
The TPR-tree [7], which has been devised based on the R*-tree [6], predicts the future-time positions of
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)OR that denotes
its extent at reference time 0, and a velocity bounding rectangle (VBR) OV={OV1-,OV1+,OV2-
,OV2+} where
OVi-(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 0
2 NGUYEN TIEN PHUONG, DANG VAN DUC
query processing times [9]. The research aims at improving the query processing times, so this method will
be 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 fired
up while having update operations. That is, the TPR*-tree cannot adjust the MBR of a node N, if no
indexed object in N changes its location or velocity. The size of the empty space in node N enlarges
continuously for a long time, if N is a node without updates. Therefore, if query processes 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 DO-TPR*-
tree, which improves the performance of the original TPR*-tree significantly. In our proposed method, the
search algorithm will enforce firing up MBR adjustment on N, if the condition, based on density optimal
for the area of N’s MBR, is satisfied at a query time. So, some of queries can be prevented from being
misled 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 environment
with less update rates (due to disconnected) or high query rates, this method is faster than the original
method.
This paper is organized as follows. Section 2 briefly reviews the TPR*-treeas related work, and then
introduces the research motivation. Section 3 proposes the method in detail. In the section 4, 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 MOTIVATION
2.1 TPR-tree
The TPR-tree [7], which has been devised based on the R*-tree [6], predicts the future-time positions of
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)OR that denotes
its extent at reference time 0, and a velocity bounding rectangle (VBR) OV={OV1-,OV1+,OV2-
,OV2+} where
OVi-(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 1
Figure 1: Entry representations in a TPR-tree
Figure 1a shows the MBRs and VBRs of 4 objects a, b, c, d. The arrows (numbers) denote
the directions (values) of their velocities, where a negative value implies that the velocity is towards
the negative direction of an axis. The VBR of a is aV = {1, 1, 1, 1} (the first two numbers are for
DO-TPR*-TREE: A DENSITY OPTIMAL METHOD FOR TPR*-TREE 45
the x-dimension), while those of b, c, d are bV = { − 2, −2, −2, −2}, cV = { − 2, 0, 0, 2}, and
dV = { − 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. In
Figure 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 not
necessarily tight. For example, N1(N2) at timestamp 1 is much larger than the tightest bounding
rectangle 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 them
at time 0). When an object is inserted or removed, the TPR-tree tightens the MBR of its parent
node.
2.2. TPR*-tree
The data structure and the query processing algorithm of the TPR*-tree [8] are similar to those of
the TPR-tree. A difference between them is the insertion algorithm. That is, the TPR-tree uses
the original insertion algorithm of the R*-tree without modification, while the TPR*-tree makes a
modification in order to reflect the mobility of objects.
In the insertion algorithm, the TPR-tree assesses the overall changes of the area and perimeter
of MBRs, and the overlapping regions among MBRs that are caused by this object insertion. By
choosing the tree-path where such changes remain smallest, the TPR-tree brings the least space
possible. This approach can be very efficient for indexing static objects as in the R*-tree, but it
cannot be a good solution to moving objects. Because the TPR-tree does not consider the time
parameter, it estimates the MBR changes only found at the insertion time without considering the
time-dependent sizes of the BRs. To resolve these omissions, the TPR*-tree revised the insertion
algorithm 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 space
from the insertion time to a specific future-time and chooses the insertion paths that the sweeping
region remains smallest. The sweeping region of a BR from time t1 to t2 (t1 < t2) is defined to be
an index space area that is swept by the BR expanding during the time interval (t2 − t1). Fig. 2
shows an example of a sweeping region of an object o in the TPR*-tree. At the initial time 0, we
have the BR of O is OR(0). Until time 1, the BR of O is OR(1). Sweeping region of o from time 0
to 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-time
queries because it compacts the MBRs.
2.3. Research Motivation
In the TPR*-tree, the VBR stores the maximum and minimum velocity of moving objects in the
MBR. So the MBR enlarges at a fast and continuous rate. It leads to a large empty space and causes
overlaps among nodes’ MBRs as time goes on (see Fig. 1b above). It may reduce the performance of
query processing because of increasing number of node accesses that require for query processing (qR
in Fig. 1b above has unnecessary node access to N1 and N2). To resolve this problem, the TPR*-tree
46 NGUYEN TIEN PHUONG, DANG VAN DUC
4 NGUYEN TIEN PHUONG, DANG VAN DUC
Figure 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 because
it compacts the MBRs.
2.3 Research Motivation
In the TPR*-tree, the VBR stores the maximum and minimum velocity of moving objects in the MBR. So
the MBR enlarges at a fast and continuous rate. It leads to a large empty space and causes overlaps among
nodes’ MBRs as time goes on (see fig. 1b above). It may reduce the performance of query processing
because of increasing number of node accesses that require for query processing (qR in fig. 1b above has
unnecessary node access to N1 and N2). To resolve this problem, the TPR*-tree executes MBR adjustment
on a node whenever object’s velocity or position have explicitly changed.
(a) Time 0 (b) Time 1
Figure 3: MBR R at the initial time 0 and its expansion R1 at time 1
Fig. 3 illustrates the benefit of the MBR adjustment. In Fig. 3a, a MBR is created or updated to capture
the objects of O1 and O2 at time 0 and its MBR is denoted by rectangle R. Fig. 3b depicts the positions of
Figure 2: Sweeping region of moving object o (from time 0 to time 1)
executes MBR adjustment on a node whenever object’s velocity or position have explicitly changed.
4 NGUYEN TIEN PHUONG, DANG VAN DUC
Figure 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 because
it compacts the MBRs.
2.3 Research Motivation
In the TPR*-tree, the VBR stores the maximum and minimum velocity of moving objects in the MBR. So
the MBR enlarges at a fast and continuous rate. It leads to a large empty space and causes overlaps among
nodes’ MBRs as time goes on (see fig. 1b above). It may reduce the performance of query processing
because of increasing number of node accesses that require for query processing (qR in fig. 1b above has
unnecessary node access to N1 and N2). To resolve this problem, the TPR*-tree executes MBR adjustment
on a node whenever object’s velocity or position have explicitly changed.
(a) Time 0 (b) Time 1
Figure 3: MBR R at the initial time 0 and its expansion R1 at time 1
Fig. 3 illustrates the benefit of the MBR adjustment. In Fig. 3a, a MBR is created or updated to capture
the objects of O1 and O2 at time 0 and its MBR is denoted by rectangle R. Fig. 3b depicts the positions of
(a) Time 0
4 NGUYEN TIEN PHUONG, DANG VAN DUC
Figure 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 because
it compacts the MBRs.
2.3 Research Motivation
In the TPR*-tree, the VBR stores the maximum and minimum velocity of moving objects in the MBR. So
the MBR enlarges at a fast and continuous rate. It leads to a large empty space and causes overlaps among
nodes’ MBRs as time goes on (see fig. 1b above). It may reduce the performance of query processing
because of increasing number of node accesses that require for query processing (qR in fig. 1b above has
unnecessary node access to N1 and N2). To resolve this problem, the TPR*-tree executes MBR adjustment
on a node whenever object’s velocity or position have explicitly changed.
(a) Time 0 (b) Time 1
Figure 3: MBR R at the initial time 0 and its expansion R1 at time 1
Fig. 3 illustrates the benefit of the MBR adjustment. In Fig. 3a, a MBR is created or updated to capture
the objects of O1 and O2 at time 0 and its MBR is denoted by rectangle R. Fig. 3b depicts the positions of
(b) Time 1
Figure 3: MBR R at the initial time 0 and its expansion R1 at time 1
Fig. 3 illustrates the benefit of the MBR adjustment. In Fig. 3a, a MBR is created or updated to
capture the objects of O1 and O2 at time 0 and its MBR is denoted by rectangle R. Fig. 3b depicts
the positions of those objects after the time interval of 1. Objects O1 and O2 moved closely to each
other. If a MBR adjustment arises at time 1 because of updating a node, a smaller MBR will be
available (R0
in Fig. 3b). In contrast, the predicted MBR will become a larger rectangle (R1 of Fig.
3b). Therefore, the empty space of R1 − R0
can be eliminated. In other words, some unnecessary
node access to the area of R1 − R0
can be eliminated in the near future.
The MBR adjustment is a solution to better performance, but its execution is only fired up while
having update operations. That is, the TPR*-tree cannot adjust the MBR of a node N, if no indexed
object in N changes its location or velocity (due to disconnected). Otherwise, the size of empty space
in node N enlarges continuously for a long time, if N is a node without updates. Therefore, if query
processes 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, named
as 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 47
3. THE PROPOSED METHOD
In 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 Description
In this section, the technique for the proposed method is described. Denote P is a query process, N
is a leaf node that Preached and Tuj
and Tuj+1 are the jth and the (j + 1)th update times when the
MBR 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 Tuj
to
Tuj+1 . Denote the user query having released P by Qj,i, that is, Qj,i is the ith user query accessing
N. Let Tqj,i be the access time of Qj,i to N resulting in an arrival sequence as below.
Tuj < Tqj,i < Tqj,2 < . . . < Tqj,k < Tuj+1
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 Nincreases
during that interval. Note that if there is any query having an overlap between its target query region
and 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 arrives
at N. If this process is able to do its MBR adjustment on Nat time Tqj,i , then some of the queries
Qj,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 the
condition, based on density optimal for the area of N0
s MBR, is satisfied at time Tqj,i . Two definitions
are 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 the
number of entries per unit of the area of N’s MBR. Node Density of Nat time T, denoted
DN (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 MBR
at time T.
Definition 2 (Node Density Optimal). Node Density of N at query time Tq is called optimal
if its ratio and Node Density of Nat the last update time Tu is smaller than a given number λ.
DN (Tq)
DN (Tu)
< λ (2)
where, DN (Tq) is Node Density of N at query time Tq, DN (Tu) is Node Density of N at
the last update time Tu, λ is a given number, depending on the specific application. In
the Vehicle Management System, λ should be h − 1, h is the tree height, according to our
evaluation.
48 NGUYEN TIEN PHUONG, DANG VAN DUC
In the search algorithm of our proposed method, Node Density Optimal condition (2) of N is
checked while user queries are being at time Tqj,i . If not, MBR adjustments arise on N. So, all
queries Qj,x(i < x ≤ k), that occur after time will be prevented from being misled as to an empty
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 MBR
adjustment is called Density Optimal Adjustment (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. Algorithm
Algorithms 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 path
algorithm in line 3. If N is full, a set of entries, selected by pick worst, is removed from N and
re-inserted in line 7.
6 NGUYEN TIEN PHUONG, DANG VAN DUC
DN (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 T
DEFINITION 3.2 (Node Density Optimal): Node Density of N at query time Tq is called optimal if its
ratio and Node Density of N at the last update time Tu is smaller than a given number λ.
< λ (2)
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 Management
System, λ 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 checked
while user queries are being at time
. If not, MBR adjustments arise on N. So, all queries Qj,x(i