=Paper=
{{Paper
|id=Vol-174/paper-2
|storemode=property
|title=Update-efficient Indexing of Moving Objects in Road Networks
|pdfUrl=https://ceur-ws.org/Vol-174/paper2.pdf
|volume=Vol-174
|dblpUrl=https://dblp.org/rec/conf/stdbm/ChenMGX06
}}
==Update-efficient Indexing of Moving Objects in Road Networks==
https://ceur-ws.org/Vol-174/paper2.pdf
Update-efficient Indexing of Moving Objects in Road
Networks
Jidong Chen Xiaofeng Meng Yanyan Guo Zhen Xiao
School of Information, Renmin University of China
{chenjd, xfmeng, guoyy, xiaozhen}@ruc.edu.cn
Abstract dexes to improve the update performance is an impor-
tant challenge.
Recent advances in wireless sensor networks Current work on reducing the index updates of mov-
and positioning technologies have boosted ing objects mainly contains three kinds of approaches.
new applications that manage moving objects. First, most efforts [4, 9, 10, 15] focus on the update
In such applications, a dynamic index is often optimization of the existing multi-dimensional index
built to expedite evaluation of spatial queries. structures especially the adaptation and extension of
However, development of efficient indexes is a the R-tree [6]. To avoid the multiple paths search op-
challenge due to frequent object movement. In eration in the R-tree during the top-down update, re-
this paper, we propose a new update-efficient cent work proposes the bottom-up approach [9, 10] and
index method for moving objects in road net- memo-based [15] structure to reduce the updates of
works. We introduce a dynamic data struc- the R-tree. Another method [4] exploits the change-
ture, called adaptive unit, to group neighbor- tolerant property of the index structure to reduce the
ing objects with similar movement patterns. number of updates that cross the MBR boundaries of
To reduce updates, an adaptive unit captures R-tree.
the movement bounds of the objects based However, the indexes based on MBRs exhibit high
on a prediction method, which considers the concurrency overheads during node splitting, and each
road-network constraints and stochastic traf- individual update is still costly. Therefore, some index
fic behavior. A spatial index (e.g., R-tree) for methods based on a low-dimensional index structure
the road network is then built over the adap- (e.g. B + -tree) are proposed [7, 16], which construct
tive unit structures. Simulation experiments, the second category of index methods. They combine
carried on two different datasets, show that an the dimension reduction and linearization technique
adaptive-unit based index is efficient for both with a single B + -tree to efficiently update the index
updating and querying performance. structure.
The third kind of approaches use a prediction
Keywords Spatial-Temporal Databases, Moving method with a time-parameterized function to reduce
Objects, Index Structure, Road Networks the index updates [12, 13, 14]. They describe a mov-
ing object’s location by a linear function and the index
1 Introduction is updated only when the parameters of the function
Recent advances in wireless sensor networks and po- change, for example, when the moving object changes
sitioning technologies have enabled a variety of new its speed or direction. The MBRs of the index vary
applications such as traffic management, fleet manage- with the time as a function of the enclosed objects.
ment, and location-based services that manage contin- However, the linear prediction is hard to reflect the
uously changing positions of moving objects [11, 12]. movement in many real application and therefore leads
In such applications, a dynamic index is often built to to low prediction accuracy and frequent updates.
expedite evaluation of spatial queries. However, exist- Though these index structures solve the problem
ing dynamic index structures (e.g. B-tree and R-tree) of index updates to some extent, they are designed
suffer from poor performance due to the large over- to index objects performing free movement in a two-
head of keeping the index updated with the frequently dimensional space. We focus on the index update
changing position data. Development of efficient in- problem in real life environments, where the objects
move within constrained networks, such as vehicles on
Proceedings of the third Workshop on STDBM roads. In such setting, the spatial property of objects’
Seoul, Korea, September 11, 2006 movement is captured by the network. Therefore, the
9
spatial location of moving objects can be indexed by 2 Related Work and Underlying Model
means of the road-network index structure. For ex-
2.1 Related Work
ample, moving objects can be accessed by each road
segment indexed by the R-tree. Since the road net- There are lots of efforts at reducing the need for index
work seldom change and objects just move from one updates of moving objects. In summary, they can be
part to the other part of the network, the R-tree in classified into three categories.
this case remains fixed. Existing index work that han- First, most work focuses on the update optimiza-
dles network-constrained moving objects [1, 5, 11] is tion of existing multi-dimensional index structures es-
based on this feature. They separate spatial and tem- pecially the adaptation and extension of the R-tree [6].
poral components of the moving objects’ trajectories The top-down update of R-tree is costly since it needs
and index the spatial aspect by the network with a several paths for searching the right data item con-
R-tree. However, they are mostly concerned with the sidering the MBR overlaps. In order to reduce the
historical movement and therefore they do not consider overhead, Kwon et al. [9] develop the Lazy Update R-
the problem of index updates. tree, which is updated only when an object moves out
In this paper, we address the problem of efficient of the corresponding MBR. With adding a secondary
indexing of moving objects in road networks to sup- index on the R-tree, it can perform the update oper-
port heavy loads of updates. We exploit the con- ation in the bottom-up way. Recently, by exploiting
straints of the network and the stochastic behavior of the change-tolerant property of the index structure,
the real traffic to achieve both high update and query Cheng et al. [4] present the CTR-tree to maximize
efficiency. We introduce a dynamic data structure, the opportunity for applying lazy updates and reduce
called adaptive unit (AU for short) to group neigh- the number of updates that cross MBR boundaries.
boring objects with similar movement patterns in the [10] extends the main idea of [9] and generalizes the
network. A spatial index (e.g., R-tree) for the road bottom-up update approach. However, they are not
network is then built over the adaptive units to form suitable to the case where consecutive changes of ob-
the index scheme for moving objects in road networks. jects are large. Xiong and Aref [15] present the RUM-
The index scheme optimizes the update performance tree that processes R-tree updates in a memo-based
for the following reasons: (1) An AU functions as approach, which eliminates the need to delete the old
a one-dimensional MBR in the TPR-tree [13], while data item during an index update. Therefore, its up-
it minimizes expanding and overlaps by considering date performance is stable with respect to the changes
more movement features. (2) The AU captures the between consecutive updates. In our index structure,
movement bounds of the objects based on a predic- however, the R-tree remains fixed since it indexes the
tion method, which considers the road-network con- road network and only the adaptive units are updated.
straints and stochastic traffic behavior. (3) Since the The second type of methods are based on the dimen-
movement of objects is reduced to occur in one spatial sion reduction technique [11] and a low-dimensional in-
dimension and attached to the network, the update of dex [7, 16] (e.g. B + -tree). The B x -tree [7, 16] combine
the index scheme is only restricted to the update of the the linearization technique with a single B + -tree to ef-
AUs. We have carried out extensive experiments based ficiently update the index structure. They uses space
on two datasets. The results show that an adaptive- filling curves and a pre-defined time interval to parti-
unit based index not only improves the efficiency of tion the representation of the locations of the moving
each individual update but also reduces the number of objects. This makes the B + -tree capable to index the
updates and is efficient for both updating and querying two-dimensional spatial locations of moving objects.
performance. Therefore, the cost of individual update of index is
The main contributions of this paper are: reduced. However, the B x -tree imposes discrete rep-
resentation and may not keep the precise values of lo-
• The introduction of Adaptive Units that optimize cation and time during the partitioning. For our set-
for frequent index updates of moving objects in ting, the two-dimensional spatial locations of moving
road networks. objects can be reduced to the 1.5 dimensions [8] by the
• An experimental evaluation and validation of the road network where objects move.
efficient update as well as query performance of The techniques in third category use a prediction
the proposed index structure. method represented as the time-parameterized func-
tion to reduce the index updates [12, 13, 14]. They
The rest of the paper is organized as follows. Sec- store the parameters of the function, e.g. the veloc-
tion 2 surveys related work and introduces underlying ity and the starting position of an object, instead of
model. Section 3 describes the structure and algo- the real positions. In this way, they update the in-
rithms of adaptive units for efficient updates. Sec- dex structure only when the parameters change (for
tion 4 contains algorithm analysis and experimental example, the speed or the direction of a moving ob-
evaluation. We conclude and propose the future work ject changes). The Time-Parameterized R-tree (TPR-
in Section 5. tree) [13] and its variants (e.g. TPR*-tree) [12, 14] are
10
the examples of this type of index structures. They ing patterns. Specifically, for objects in the same net-
all use a linear prediction model, which relates ob- work edge, we use a distance threshold and a speed
jects’ positions as a linear function of time.However, threshold to cluster the adjacent objects with the same
the linear prediction is hard to reflect the movement direction and similar speed. In comparison, the AU
in many real application especially in traffic networks has no obvious enlargement because objects in the AU
where vehicles change their velocities frequently. The move in a cluster.
frequent changes of the object’s velocity will incur re- We now formally introduce the AU. An AU is a
peated updates of the index structure. Our technique 8-tuple:
also fall into this category and apply an accurate pre-
diction method we proposed in [3] by considering more AU = (auID, objSet, upperBound, lowerBound,
transportation features. edgeID, enterTime, exitTime, auInitLen)
Several methods have been proposed for index-
ing moving objects in spatially constrained networks. where auID is the identifier of the AU, objSet is a list
Pfoser et al. [11] propose to convert the 3-dimensional that stores objects belonging to the AU, upperBound
problem into two sub-problems of lower dimensions and lowerBound are upper and lower bounds of pre-
through certain transformation of the networks and dicted future trajectory of the AU. The trajectory
the trajectories. Another approach, known as the bounds will be explained in details in Section 3.3. We
FNR-tree [5], separates spatial and temporal compo- assume the functions of trajectory bounds as follows:
nents of the trajectories and indexes the time intervals
that each moving object spends on a given network upperBound : D(t) = αu + βu · t
link. The MON-tree approach [1] further improves lowerBound : D(t) = αl + βl · t
the performance of the FNR-tree by representing each
edge by multiple line segments (i.e. polylines) instead edgeID denotes the network edge that the AU belongs
of just one line segment. However, they all focus on to, enterTime and exitTime record the time when the
the historical movement and cannot support frequent AU enters and leaves the edge and auInitLen repre-
index updates. To the best of our knowledge, there is sents the initial length of the AU.
no current index method to support efficient updates In the road network, multiple AUs are associated
of moving objects in road networks. with a network edge. Since AUs in the same edge are
likely to be accessed together during query process-
2.2 Underlying Model
ing, we store AUs by clustering on their edgeID. That
We use the GCA model we proposed in [3] to model the is, the AUs in the same edge are stored in the same
network and moving objects. A road network is mod- disk pages. To access AUs more efficiently, we create
eled as a graph of cellular automata (GCA), where an in-memory, compact summary structure called the
the nodes of the graph represent road intersections direct access table for each edge. A direct access ta-
and the edges represent road segments with no inter- ble stores the summary information of each AU on an
sections. Each edge consists of a cellular automaton edge (i.e. number of objects, trajectory bounds) and
(CA), which is represented, in a discrete mode, as a pointers to AU disk pages. Each AU corresponds to
finite sequence of cells. an entry in the direct access table, which has the fol-
In the GCA, a moving object is represented as a lowing structure (auID, upperBound, lowerBound,
symbol attached to the cell and it can move several auPtr, objNum), where auPtr points to a list of AUs
cells ahead at each time unit. Intuitively, the velocity in disk storage and objNum is the number of objects
is the number of cells an object can traverse during included in the AU. In order to minimize I/O cost, we
a time unit. The motion of an object is represented use the direct access table to filter AUs and only access
as some (time, location) information. Generally, such the disk pages when necessary.
information is treated as a trajectory. 3.2 The Index Scheme
3 The Adaptive Unit We build a spatial index (e.g., R-tree) for the road net-
work over the adaptive units to form the index scheme
3.1 Structure and Storage
for the network-constrained moving objects. The AU
Conceptually, an adaptive unit is similar to a one- index scheme is a two-level index structure. At the
dimensional MBR in the TPR-tree, that expands with top level, it consists of a 2D R-tree that indexes spa-
time according to the predicted movement of the ob- tial information of the road network. On the bottom
jects it contains. However, in the TPR-tree, it is possi- level, its leaves contain the edges representing road
ble that an MBR may contain objects moving in oppo- segments included in the corresponding MBR of the
site directions, or objects moving at different speeds. R-tree and point to the lists of adaptive units. The
As a result, the MBR may expand rapidly, which may top level R-tree remains fixed during the lifetime of
create large overlaps with other MBRs. The AU avoids the index scheme (unless there are changes in the net-
this problem by grouping objects having similar mov- work). The index scheme is developed with the R-tree
11
road road
d d
upper bound
leaf node fastest
R-Tree movement
auID upperBd d2
lowerBd
Direct Access d1
slowest movement lower bound
Table
objSet AU objSet objSet
objSet ... objSet objSet Adaptive Units cars t AU tq t
objSet ... objSet objSet
(a) Simulated trajectories (b) Trajectory bounds
Figure 1: Structure of the AU index scheme
Figure 2: The simulation-based prediction
in this paper, but any existing spatial index can also trajectories of objects by setting Pd (i) to values that
be used without changes. model different traffic conditions. In this setting, Pd (i)
Figure 1 shows the structure of the AU index is treated as a random variable to reflect the stochas-
scheme, which also includes the direct access table. tic, dynamic nature of traffic system. By giving Pd (i)
The R-tree and adaptive units are stored in the disk. two values (e.g. 0 and 0.1 in our experiments), we can
However, the direct access table is in the main memory derive two future trajectories, which describe, respec-
since it only keeps the summary information of adap- tively, the fastest and slowest movements of objects.
tive units. In the index scheme, each leaf node of the Finally, we translate the two regression lines, until all
R-tree can be associated with its direct access table by estimated future positions fall within to obtain the pre-
its edgeID and the direct access table can connect to dicted trajectory bounds. The SP method is shown in
corresponding adaptive units by auPtr in its entries. Figure 2. Through the SP method, we obtain two pre-
Therefore, we only need to update the direct access dicted future trajectory bounds of objects. We apply
table when AUs change, which greatly enhances the this technique to the AU - a set of moving objects that
performance of the index scheme. have similar movement and are treated as one object.
3.3 Optimizing for Updates The future trajectory bounds are predicted as soon
as AU is created. The trajectory bounds will not be
An important feature of the AU is that it groups ob- changed along the edge that the AU moves on until
jects having similar moving patterns. The AU is capa- the objects in the AU move to another edge in the net-
ble of dynamically adapting itself to cover the move- work. It is evident that the range of predicted bounds
ment of the objects it contains. By tightly bounding of AU will become wider with the time, which leads to
enclosed moving objects for some time in the future, lower accuracy of future trajectory prediction. How-
the AU alleviates the update problem of MBR rapid ever, if we issue another prediction when the predicted
expanding and overlaps in the TPR-tree like methods. bounds are not accurate any more, the costs of sim-
For reducing the updates further, the AU captures ulation and regression are high. Considering that the
the movement bounds of the objects based on a predic- movement of objects along one network edge is sta-
tion method we proposed in [3], which considers the ble, we can assume the same trends of the trajectory
road-network constraints and stochastic traffic behav- bounds and adjust only the initial locations when the
ior. Since objects in an AU have similar movement, we prediction is not accurate. Specifically, when the pre-
then predict the movement of the AU, as if it were a dicted position exceeds its actual position above the
single moving object. In the following, we describe the predefined accuracy, the AU treats its actual locations
application and adaptation of the prediction method (the locations of the boundary objects) at that time
to the AU. as the initial locations of the two trajectory bounds
We use GCAs not only to model road networks, and follow the same movement vector (e.g. slope of
but also to simulate the movements of moving objects the bounds) as the previous bounds to provide more
by the transitions of the GCA. Based on the GCA, accurate predicted trajectory bounds. In this way, the
the Simulation-based Prediction (SP) method to an- predicted trajectory bounds can be effectively revised
ticipate future trajectories of moving objects is pro- with few costs. Figure 2(b) shows the adaptation of
posed. The SP method treats the objects’ simulated the trajectory bounds. tq is the time slice when actual
results as their predicted positions. Then, by the lin- locations of boundary objects in the AU exceeds the
ear regression, a compact and simple linear function predicted bounds of the AU above precision threshold
that reflects future movement of a moving object can and the d1 ,d2 are the actual locations of the first object
be obtained. To refine the accuracy, based on differ- and last object respectively in the AU. The trajectory
ent assumptions on the traffic conditions we simulate bounds are revised according to the actual locations
two future trajectories to obtain its predicted move- and the original bounds’ slopes. Therefore, without
ment function. Specifically, we extend the CA model executing more prediction, the prediction accuracy of
used in traffic flow simulation for predicting the future the objects’ future trajectories can be kept high.
12
Since the R-Tree indexes the road network, it re- the AU that the object belongs to unless its position
mains fixed, and the update of the AU index scheme exceeds the bounds of the AU. In that case, we execute
restricts to the update of adaptive units. Specifically, the same updates as those when it moves to another
an AU is usually created at the start of one edge and edge or only revise the predicted trajectory bounds of
dropped at the end of the edge. Since the AU is a the AU. Factually, we find, from the experiment eval-
one-dimensional structure, it performs update opera- uation, that the chances that objects move beyond the
tions much more efficiently than the two-dimensional trajectory bounds of its AU on an edge are very slim.
indexes. We will describe these operations in details. The algorithm 1 shows the update algorithm of AUs.
3.4 Update Operations
Algorithm 1: Update(objID, position, velocity, edgeID)
The update of an AU can be of the following form:
input : objID is the object identifier, position and
creating an AU, dropping an AU, adding objects to an velocity are its position and velocity,
AU and removing objects from an AU. edgeID is the edge identifier where the
Creating an AU object lies
Find AU where objID is included before update;
To create an AU, we first compose the objSet – a list of if AU.edgeID 6= edgeID or (position <
objects traveling in the same direction with similar ve- AU.lowerBound or position > AU.upperBound)
locities, and in close-by locations. We then predict the then
future trajectories of the AU by simulation and com- // The object moves to a new edge or
pute its trajectory bounds. In fact, we treat the AU exceeds bounds of its original AU
as one moving object (the object closest to the center Find the nearest AU AU1 for objID on edgeID;
of the AU) and predict its future trajectory bounds by if GetNum(AU1 .objSet) < M AXOBJN U M and
predicting this object. The prediction starts when the ObjectFitAU(objID, position, velocity, AU1 )
AU is created and ends at the end the edge. Finally, then
InsertObject(objID, AU1 .auID, AU1 .edgeID);
we write the created AU to the disk page and insert
else AU2 ← CreateAU(objID,edgeID);
the AU entry to its summary structure. if GetNum(AU.objSet) > 1 then
Dropping an AU DeleteObject(objID, AU.auID, AU.edgeID);
else DropAU(AU.edgeID, AU.auID);
When objects in an AU move out of the edge, they end
may change direction independently. So we need to
drop this AU and create new AUs in adjacent edges to
regroup the objects. When the front of an AU touches In summary, updating the AU-based index is easier
the end of the edge, some objects in the AU may start than updating the TPR-tree. It never invoke any com-
moving out of the edge. However, the AU cannot be plex node splitting and merging. Moreover, thanks to
dropped because a query may occur at that time. Only the similar movement features of objects in an AU and
after the last object in the AU enters another edge and the accurate prediction of the SP method, the objects
joins another AU, can the AU be dropped. Dropping are seldom removed or added from their AU on an
an AU is simple. Through its entry in direct access edge, which reduces the number of index updates.
table, we find the AU and delete it. 3.5 Query Algorithm
Adding and removing objects from an AU Query processing in the AU index scheme is straight-
When an object leaves an AU, we remove this object forward. Given a query, we use the top level R-tree
from the AU and find another AU in the neighborhood to get the edges involved and then scan the direct
to check if the object can fit that AU. If it can, the access tables of the edges. With the upperBound
object will be inserted into that AU, otherwise, a new and the lowerBound in the direct access table, we
AU is created for this object. Specifically, when adding can easily find AU entries that intersect the query,
an object into an AU, we first find the direct access and then visit the disk pages to get more informa-
table of the edge that the object lies and, by its AU tion about these AUs. For space limitation, we just
entry in the table, access the AU disk storage. Finally, take window range query for example. Given a range
we insert into the objects list of the AU and update with (X1 , Y1 , X2 , Y2 ), we first perform a spatial range
the AU entry in the direct access table. Removing an search in the top level R-Tree to locate the edges (e.g.
object from an AU has the similar process. e1 , e2 , e3 , . . .). For each selected edge ei , we trans-
Therefore, when updating an object in the AU index form the original search (X1 , Y1 , X2 , Y2 ) to a 1D search
scheme, we first determine whether the object is leav- range (S1 , S2 ) (S1 ≤ S2 ), where S1 and S2 are the rel-
ing the edge and entering another one. If it is moving ative distances from the start vertex along the edge ei .
to another edge, we delete it from the old AU (if it is In the case of multiple intersecting edges, we can di-
the last object in the old AU, the AU is also dropped) vide the query range into several sub-ranges by edges
and insert it into the nearest AU or create a new AU and apply the transformation method to each edge.
in the edge it is entering. Otherwise, we do not update The method is also applicable to the various modes
13
that the query and edges intersect. Here, we only il-
lustrate the case when the query window range only Table 1: Parameters and their settings
Parameters Settings
intersects one edge and compute its relative distances Page size 4K
S1 and S2 . It can be easily extended to other cases. Node capacity 100
Suppose Xstart , Ystart , Xend , Yend are the start vertex Numbers of queries 200
coordinates and the end vertex coordinates of the edge Numbers of mo(cars) 10K, ... , 50K, ... , 100K
Numbers of updates 100K, ... , 500K, ... , 1M
ei . According to Thales Theorem about similar trian- Dataset Generator CA Simulator, Network-based Generator
gles, we obtain S1 and S2 as follows:
p We implemented both the AU index scheme and
r = (Xstart − Xend )2 + (Ystart − Yend )2 the TPR-tree in Java and carried out experiments on
X1 − Xstart a Pentium 4, 2.4 GHz PC with 512MB RAM running
S1 = r
Xend − Xstart Windows XP. To improve the performance of the index
Y1 − Ystart structure, we employed a LRU buffer of the same size
S2 = r as the one used in the TPR-tree [13]. We summarize
Yend − Ystart
workload parameters in Table 1, where values in bold
The transformed query (S1 , S2 ) is then executed in are default values.
each of the AUs in the direct access table of the cor-
4.2 Update Cost
responding edge ei . By the trajectory bounds of the
AU, we can determine whether the transformed query We compare the cost of index update for the AU index
intersects the AU, thus filtering the unnecessary AUs and the TPR-tree in terms of the average individual
quickly. Finally, we access the selected AUs in disk update cost, update frequency and total update cost.
storage and return the objects satisfying the query Individual Update Cost
window. In summary, the query processing is efficient
due to the grouping of similar objects in AUs and the We study the individual update performance of the in-
dimensionality reduction of the query. dex while varying the number of moving objects and
updates. Figure 3 shows the average individual update
4 Performance Analysis cost when increasing the data size from 10K to 100K.
We evaluate the AU index scheme (denoted as “AU Figure 4 shows how the performance varies over time.
index”) by comparing it with the TPR-tree and the Clearly, updating the TPR-tree tends to be costly,
AU index scheme when the direct access table is not and the problem is exacerbated when the data size in-
used (denoted as “AU index without DT”). We mea- creases. In each case of different data size and different
sure their their update performance with the individ- number of updates, the AU index has much lower up-
ual update, update frequency and total update costs date cost than the TPR-tree. The main reason can
and their query performance. be explained as follows. Each update of the TPR-tree
involves the search of an old entry and a new entry, as
4.1 Datasets
well as the modification of the index structure (node
We use two datasets for our experiments. The first splitting, merging, and the propagating of changes up-
is generated by the CA simulator, and the second by wards). The cost increases with larger data size due
the Brinkhoff’s Network-based Generator [2]. We use to more overlaps among MBRs. The changes of index
the CA traffic simulator to generate a given number of structure with the increase of data updates also affect
objects in a uniform network of size 10000×10000 con- the performance of the TPR-tree. However, the AU
sisting of 500 edges. Each object has its route and is index has better performance because its update only
initially placed at a random position on its route. The restricts to the AU’s update and as a one-dimensional
initial velocities of the objects follow a uniform random access structure, the AU has few overlaps and incurs
distribution in the range [0, 30]. The location and ve- no cost associated with node splitting and the propa-
locity of every object is updated at each time-stamp. gation of MBR updates.
The Brinkhoff’s Network-based Generator is used as a The direct access table of the AU index has a signif-
popular benchmark in many related work. The gen- icant contribution in improving update performance.
erator takes a map of a real road network as input This is because the search of the specific AU is accel-
(our experiment is based on the map of Oldenburg erated by the in-memory structure.
including 7035 edges). The positions of the objects
are given in two dimensional X-Y coordinates. We Update Frequency
transform them to the form of (edgeid, pos), where Frequent updates of moving objects (a.k.a. data up-
edgeid denotes the edge identifier and pos denotes dates) may lead to frequent updates of index. When
the object relative position on the edge. The generator an object’s position exceeds the MBR or AU, the index
places a given number of objects at random positions needs to be updated to delete the object from the old
on the road network, and updates their locations at MBR or AU and insert it to another one. In this ex-
each time-stamp. periment, we measure the index update rate, which is
14
11 11 4
AU-index AU-index 14 AU-index AU-index
10 AU-index without DT 10 AU-index without DT AU-index without DT 3.5 AU-index without DT
Rate of index updates (%)
Rate of index updates (%)
TPR-tree TPR-tree 12 TPR-tree TPR-tree
9 9 3
Update I/Os
Update I/Os
8 8 10 2.5
7 7 8 2
6 6 6 1.5
5 5 1
4
4 4 0.5
2
3 3 0
10K 30K 50K 70K 90K 10K 30K 50K 70K 90K 100K 300K 500K 700K 900K 100K 300K 500K 700K 900K
Number of moving objects Number of moving objects Number of data updates Number of data updates
(a) Brinkhoff (b) CA (a) Brinkhoff (b) CA
Figure 3: Individual Update Cost with Different Datasize Figure 6: Index Update Frequency over Time
100000 25000
14 AU-index 14 AU-index AU-index AU-index
AU-index without DT AU-index without DT 90000 AU-index without DT AU-index without DT
12 TPR-tree 12 TPR-tree TPR-tree TPR-tree
Total index update I/Os
Total index update I/Os
80000 20000
70000
Update I/Os
Update I/Os
10 10
60000 15000
8 8
50000
6 6 40000 10000
30000
4 4
20000 5000
2 2 10000
100K 300K 500K 700K 900K 100K 300K 500K 700K 900K 0 0
10K 30K 50K 70K 90K 10K 30K 50K 70K 90K
Number of data updates Number of data updates
Number of moving objects Number of moving objects
(a) Brinkhoff (b) CA
(a) Brinkhoff (b) CA
Figure 4: Individual Update Cost over Time Figure 7: Total Update Cost with Different Datasize
the ratio between number of index updates and num-
For each data size, the update costs of the two in-
ber of data updates, for every 100K data updates and
dexes in the Brinkhoff’s dataset are both higher than
different data size. Figure 5 and 6 show that the up-
those in the CA dataset due to the higher complex-
date rate of the TPR-tree is nearly 4 to 5 times more
ity of road network and skewed spatial distribution of
than that of the AU index. The index update rate
objects in the Brinkhoff’s dataset.
depends on the prediction method. In the AU index,
the future positions of the object are predicted more 4.3 Query Cost
accurately, so the object is likely to remain in its AU,
We study the window range query performance of the
which leads to fewer index updates.
TPR-tree and the AU index with different update set-
Total Update Costs tings. We increase the number of updates from 100K
The total update costs depend on the update fre- to 1M to examine how query performance is affected.
quency and the average individual update cost, and We issued 200 range queries for every 100K updates
it can reflect the index update performance more ac- in a 1M dataset. Figure 9 shows that the cost of the
curately. From both Figure 7 and 8, we can see that TPR-tree increases much faster as the number of up-
although the AU index has to deal with the creation dates increases. The cost of the AU index is consider-
and dropping of AUs, the TPR-tree incurs much higher ably lower and is less sensitive to the number of up-
update costs than the AU index and its performance dates. This is because the adaptive units in the AU
deteriorates dramatically as data size increases. This index have much less overlaps than the MBRs in the
is mainly due to the inaccuracy of the linear prediction TPR-tree, and the overlaps to a large extent determine
model and the complex reconstruction of the TPR-tree the range query cost. Besides, as objects move apart,
(e.g. splitting and merging). the amount of dead space in the TPR-tree increases,
30000
4 140000 AU-index AU-index
14 AU-index AU-index AU-index without DT AU-index without DT
AU-index without DT 3.5 AU-index without DT TPR-tree 25000 TPR-tree
Rate of index updates (%)
Rate of index updates (%)
120000
Total index update I/Os
Total index update I/Os
12 TPR-tree TPR-tree
3
100000 20000
10 2.5
80000
8 2 15000
60000
6 1.5 10000
1
40000
4
5000
0.5 20000
2
0 0 0
10K 30K 50K 70K 90K 10K 30K 50K 70K 90K 100K 300K 500K 700K 900K 100K 300K 500K 700K 900K
Number of moving objects Number of moving objects Number of data updates Number of data updates
(a) Brinkhoff (b) CA (a) Brinkhoff (b) CA
Figure 5: Index Update Frequency with Different Datasize Figure 8: Total Update Cost over Time
15
which makes false hits more likely. Also, updates lead Program for New Century Excellent Talents in Uni-
to the expanding and overlaps of MBRs, which further versity (NCET); Program for Creative PhD Thesis in
deteriorate the performance of the TPR-tree. For the University. The authors would like to thank Jianliang
AU index, the increase of the updates hardly affect the Xu and Haibo Hu from Hong Kong Baptist Univer-
total number of AUs, and the chances of overlaps of sity and Stéphane Grumbach from CNRS, LIAMA in
different AUs are very slim. China for many helpful advice and assistance.
We also study the query performance while varying References
the number of moving objects and query window size.
For the space limitation, we do not report the exper- [1] V. T. Almeida, R. H. Güting. Indexing the Trajec-
imental results. Also, in each case, the AU index has tories of Moving Objects in Networks (Extended
Abstract). In SSDBM, 2004, 115-118.
lower query cost than the TPR-tree and scales well.
[2] T. Brinkhof. A framework for generating network-
1200
AU-index
100
AU-index
based moving objects. In GeoInformatica, 6(2),
1000
AU-index without DT
TPR-tree
90 AU-index without DT
TPR-tree
2002, 153-180.
Range query I/Os
Range query I/Os
80
800
70
[3] J. Chen, X. Meng, Y. Guo, S. Grumbach, H.
600
60
Sun. Modeling and Predicting Future Trajectories
400
50
of Moving Objects in a Constrained Network. In
200 40
MDM, 2006, 156 (MLASN workshop).
0
100K 300K 500K 700K 900K
30
100K 300K 500K 700K 900K [4] R. Cheng, Y. Xia, S. Prabhakar, R. Shah. Change
Number of data updates Number of data updates
Tolerant Indexing for Constantly Evolving Data.
(a) Brinkhoff (b) CA In ICDE, 2005, 391-402.
[5] E. Frentzos. Indexing objects moving on Fixed net-
Figure 9: Effect of Updates on Query Performance works. In SSTD, 2003, 289-305.
5 Conclusions and Future Work [6] A. Guttman. R-trees: A Dynamic Index Structure
for Spatial Searching. In SIGMOD, 1984, 47-57.
Indexing objects moving in a constrained network es-
pecially the road network is a topic of great practical [7] C. S. Jensen, D. Lin, B. C. Ooi. Query and Up-
importance. We focus on the index update issue for date Efficient B+-Tree Based Indexing of Moving
the current positions of network-constrained moving Objects. In VLDB, 2004, 768-779.
objects. We introduce a new access structure, adap- [8] G. Kollios, D. Gunopulos, V. J. Tsotras. On index-
tive unit that exploits as much as possible the charac- ing mobile objects. In PODS, 1999, 261-272.
teristics of the movements of objects. The updates of
the structure are minimized by an accurate prediction [9] D. Kwon, S. J. Lee, S. Lee. Indexing the current
method which produces two trajectory bounds based positions of moving objects using the lazy update
R-tree. In MDM, 2002, 113-120.
on different assumptions on the traffic conditions. The
efficiency of the structure also results from the possi- [10] M. L. Lee, W. Hsu, C. S. Jensen, B. Cui, K. L.
ble reduction of dimensionality of the trajectory data Teo. Supporting Frequent Updates in R-Trees: A
to be indexed. Our experimental results performed Bottom-Up Approach. In VLDB, 2003, 608-619.
on two datasets show that the efficiency of the index [11] D. Pfoser, C. S. Jensen. Indexing of network con-
structure is one order of magnitude higher than the strained moving objects. In ACM-GIS, 2003, 25-32.
TPR-tree.
In the future, we will compare the update perfor- [12] S. Saltenis, C. S. Jensen. Indexing of Moving Ob-
jects for Location-Based Service. In ICDE, 2002,
mance with the work of the R-tree-based updating op- 463-472.
timization such as RUM-tree [15] and CTR-tree [4].
On the other hand, since the adaptive units contain [13] S. Saltenis, C. S. Jensen, S. T. Leutenegger, M.
the predicted future trajectories of moving objects, A. Lopez. Indexing the Positions of Continuously
Moving Objects. In SIGMOD, 2000, 331-342.
the predictive query algorithms can be developed nat-
urally based on the adaptive unit-based index. Fur- [14] Y. Tao, D. Papadias, J. Sun. The TPR*-Tree: An
thermore, we will extend the query algorithms to sup- Optimized Spatiotemporal Access Method for Pre-
port the KNN query and continuous query for moving dictive Queries. In VLDB, 2003, 790-801.
objects in the road network. [15] X. Xiong, W. G. Aref. R-trees with Update
Memos. In ICDE, 2006, 22.
Acknowledgments
This research was partially supported by the grants [16] M. L. Yiu, Y. Tao, N. Mamoulis. The B dual−T ree :
Indexing Moving Objects by Space-Filling Curves
from the Natural Science Foundation of China under in the Dual Space. To appear in Very Large Data
grant number 60573091, 60273018; the Key Project of Base Journal, 2006.
Ministry of Education of China under Grant No.03044;
16