Recent advances in wireless sensor networks and positioning technologies have boosted new applications that manage moving objects. In such applications, a dynamic index is often built to expedite evaluation of spatial queries. However, development of e±cient indexes is a challenge due to frequent object movement. In this paper, we propose a new update-e±cient index method for moving objects in road networks. We introduce a dynamic data structure, called adaptive unit, to group neighboring objects with similar movement patterns. To reduce updates, an adaptive unit captures the movement bounds of the objects based on a prediction method, which considers the road-network constraints and stochastic traf¯c behavior. A spatial index (e.g., R-tree) for the road network is then built over the adaptive unit structures. Simulation experiments, carried on two di®erent datasets, show that an adaptive-unit based index is e±cient for both updating and querying performance.
Recent advances in wireless sensor networks and
positioning technologies have enabled a variety of new
applications such as tra±c management, °eet
management, and location-based services that manage
continuously changing positions of moving objects [
Current work on reducing the index updates of
moving objects mainly contains three kinds of approaches.
First, most e®orts [
However, the indexes based on MBRs exhibit high
concurrency overheads during node splitting, and each
individual update is still costly. Therefore, some index
methods based on a low-dimensional index structure
(e.g. B+-tree) are proposed [
The third kind of approaches use a prediction
method with a time-parameterized function to reduce
the index updates [
Though these index structures solve the problem
of index updates to some extent, they are designed
to index objects performing free movement in a
twodimensional space. We focus on the index update
problem in real life environments, where the objects
move within constrained networks, such as vehicles on
roads. In such setting, the spatial property of objects'
movement is captured by the network. Therefore, the
spatial location of moving objects can be indexed by
means of the road-network index structure. For
example, moving objects can be accessed by each road
segment indexed by the R-tree. Since the road
network seldom change and objects just move from one
part to the other part of the network, the R-tree in
this case remains ¯xed. Existing index work that
handles network-constrained moving objects [
In this paper, we address the problem of e±cient
indexing of moving objects in road networks to
support heavy loads of updates. We exploit the
constraints of the network and the stochastic behavior of
the real tra±c to achieve both high update and query
e±ciency. We introduce a dynamic data structure,
called adaptive unit (AU for short) to group
neighboring objects with similar movement patterns in the
network. A spatial index (e.g., R-tree) for the road
network is then built over the adaptive units to form
the index scheme for moving objects in road networks.
The index scheme optimizes the update performance
for the following reasons: (1) An AU functions as
a one-dimensional MBR in the TPR-tree [
The main contributions of this paper are: ² The introduction of Adaptive Units that optimize for frequent index updates of moving objects in road networks. ² An experimental evaluation and validation of the e±cient update as well as query performance of the proposed index structure.
The rest of the paper is organized as follows. Section 2 surveys related work and introduces underlying model. Section 3 describes the structure and algorithms of adaptive units for e±cient updates. Section 4 contains algorithm analysis and experimental evaluation. We conclude and propose the future work in Section 5. 2.1
There are lots of e®orts at reducing the need for index updates of moving objects. In summary, they can be classi¯ed into three categories.
First, most work focuses on the update
optimization of existing multi-dimensional index structures
especially the adaptation and extension of the R-tree [
The second type of methods are based on the
dimension reduction technique [
The techniques in third category use a prediction
method represented as the time-parameterized
function to reduce the index updates [
Several methods have been proposed for
indexing moving objects in spatially constrained networks.
Pfoser et al. [
We use the GCA model we proposed in [
In the GCA, a moving object is represented as a symbol attached to the cell and it can move several cells ahead at each time unit. Intuitively, the velocity is the number of cells an object can traverse during a time unit. The motion of an object is represented as some (time, location) information. Generally, such information is treated as a trajectory. 3 3.1
Conceptually, an adaptive unit is similar to a onedimensional MBR in the TPR-tree, that expands with time according to the predicted movement of the objects it contains. However, in the TPR-tree, it is possible that an MBR may contain objects moving in opposite directions, or objects moving at di®erent speeds. As a result, the MBR may expand rapidly, which may create large overlaps with other MBRs. The AU avoids this problem by grouping objects having similar moving patterns. Speci¯cally, for objects in the same network edge, we use a distance threshold and a speed threshold to cluster the adjacent objects with the same direction and similar speed. In comparison, the AU has no obvious enlargement because objects in the AU move in a cluster.
We now formally introduce the AU. An AU is a 8-tuple: AU = (auID; objSet; upperBound; lowerBound; edgeID; enterTime; exitTime; auInitLen) where auID is the identi¯er of the AU, objSet is a list that stores objects belonging to the AU, upperBound and lowerBound are upper and lower bounds of predicted future trajectory of the AU. The trajectory bounds will be explained in details in Section 3.3. We assume the functions of trajectory bounds as follows: upperBound : lowerBound :
D(t) = ®u + ¯u ¢ t
D(t) = ®l + ¯l ¢ t edgeID denotes the network edge that the AU belongs to, enterTime and exitTime record the time when the AU enters and leaves the edge and auInitLen represents the initial length of the AU.
In the road network, multiple AUs are associated with a network edge. Since AUs in the same edge are likely to be accessed together during query processing, we store AUs by clustering on their edgeID. That is, the AUs in the same edge are stored in the same disk pages. To access AUs more e±ciently, we create an in-memory, compact summary structure called the direct access table for each edge. A direct access table stores the summary information of each AU on an edge (i.e. number of objects, trajectory bounds) and pointers to AU disk pages. Each AU corresponds to an entry in the direct access table, which has the following structure (auID, upperBound, lowerBound, auPtr, objNum), where auPtr points to a list of AUs in disk storage and objNum is the number of objects included in the AU. In order to minimize I/O cost, we use the direct access table to ¯lter AUs and only access the disk pages when necessary. 3.2
We build a spatial index (e.g., R-tree) for the road network over the adaptive units to form the index scheme for the network-constrained moving objects. The AU index scheme is a two-level index structure. At the top level, it consists of a 2D R-tree that indexes spatial information of the road network. On the bottom level, its leaves contain the edges representing road segments included in the corresponding MBR of the R-tree and point to the lists of adaptive units. The top level R-tree remains ¯xed during the lifetime of the index scheme (unless there are changes in the network). The index scheme is developed with the R-tree leaf node auID upperBdlowerBd
R-Tree Direct Access
Table objSet AU objSet ... objSet ...
objSet objSet objSet objSet Adaptive Units objSet objSet in this paper, but any existing spatial index can also be used without changes.
Figure 1 shows the structure of the AU index scheme, which also includes the direct access table. The R-tree and adaptive units are stored in the disk. However, the direct access table is in the main memory since it only keeps the summary information of adaptive units. In the index scheme, each leaf node of the R-tree can be associated with its direct access table by its edgeID and the direct access table can connect to corresponding adaptive units by auPtr in its entries. Therefore, we only need to update the direct access table when AUs change, which greatly enhances the performance of the index scheme. 3.3
An important feature of the AU is that it groups objects having similar moving patterns. The AU is capable of dynamically adapting itself to cover the movement of the objects it contains. By tightly bounding enclosed moving objects for some time in the future, the AU alleviates the update problem of MBR rapid expanding and overlaps in the TPR-tree like methods.
For reducing the updates further, the AU captures
the movement bounds of the objects based on a
prediction method we proposed in [
We use GCAs not only to model road networks, but also to simulate the movements of moving objects by the transitions of the GCA. Based on the GCA, the Simulation-based Prediction (SP) method to anticipate future trajectories of moving objects is proposed. The SP method treats the objects' simulated results as their predicted positions. Then, by the linear regression, a compact and simple linear function that re°ects future movement of a moving object can be obtained. To re¯ne the accuracy, based on di®erent assumptions on the tra±c conditions we simulate two future trajectories to obtain its predicted movement function. Speci¯cally, we extend the CA model used in tra±c °ow simulation for predicting the future road trajectories of objects by setting Pd(i) to values that model di®erent tra±c conditions. In this setting, Pd(i) is treated as a random variable to re°ect the stochastic, dynamic nature of tra±c system. By giving Pd(i) two values (e.g. 0 and 0.1 in our experiments), we can derive two future trajectories, which describe, respectively, the fastest and slowest movements of objects. Finally, we translate the two regression lines, until all estimated future positions fall within to obtain the predicted trajectory bounds. The SP method is shown in Figure 2. Through the SP method, we obtain two predicted future trajectory bounds of objects. We apply this technique to the AU - a set of moving objects that have similar movement and are treated as one object.
The future trajectory bounds are predicted as soon as AU is created. The trajectory bounds will not be changed along the edge that the AU moves on until the objects in the AU move to another edge in the network. It is evident that the range of predicted bounds of AU will become wider with the time, which leads to lower accuracy of future trajectory prediction. However, if we issue another prediction when the predicted bounds are not accurate any more, the costs of simulation and regression are high. Considering that the movement of objects along one network edge is stable, we can assume the same trends of the trajectory bounds and adjust only the initial locations when the prediction is not accurate. Speci¯cally, when the predicted position exceeds its actual position above the prede¯ned accuracy, the AU treats its actual locations (the locations of the boundary objects) at that time as the initial locations of the two trajectory bounds and follow the same movement vector (e.g. slope of the bounds) as the previous bounds to provide more accurate predicted trajectory bounds. In this way, the predicted trajectory bounds can be e®ectively revised with few costs. Figure 2(b) shows the adaptation of the trajectory bounds. tq is the time slice when actual locations of boundary objects in the AU exceeds the predicted bounds of the AU above precision threshold and the d1,d2 are the actual locations of the ¯rst object and last object respectively in the AU. The trajectory bounds are revised according to the actual locations and the original bounds' slopes. Therefore, without executing more prediction, the prediction accuracy of the objects' future trajectories can be kept high.
Since the R-Tree indexes the road network, it remains ¯xed, and the update of the AU index scheme restricts to the update of adaptive units. Speci¯cally, an AU is usually created at the start of one edge and dropped at the end of the edge. Since the AU is a one-dimensional structure, it performs update operations much more e±ciently than the two-dimensional indexes. We will describe these operations in details. 3.4
The update of an AU can be of the following form: creating an AU, dropping an AU, adding objects to an AU and removing objects from an AU.
To create an AU, we ¯rst compose the objSet { a list of objects traveling in the same direction with similar velocities, and in close-by locations. We then predict the future trajectories of the AU by simulation and compute its trajectory bounds. In fact, we treat the AU as one moving object (the object closest to the center of the AU) and predict its future trajectory bounds by predicting this object. The prediction starts when the AU is created and ends at the end the edge. Finally, we write the created AU to the disk page and insert the AU entry to its summary structure.
When objects in an AU move out of the edge, they 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 the end of the edge, some objects in the AU may start moving out of the edge. However, the AU cannot be dropped because a query may occur at that time. Only after the last object in the AU enters another edge and joins another AU, can the AU be dropped. Dropping an AU is simple. Through its entry in direct access table, we ¯nd the AU and delete it.
When an object leaves an AU, we remove this object from the AU and ¯nd another AU in the neighborhood to check if the object can ¯t that AU. If it can, the object will be inserted into that AU, otherwise, a new AU is created for this object. Speci¯cally, when adding an object into an AU, we ¯rst ¯nd the direct access table of the edge that the object lies and, by its AU entry in the table, access the AU disk storage. Finally, we insert into the objects list of the AU and update the AU entry in the direct access table. Removing an object from an AU has the similar process.
Therefore, when updating an object in the AU index scheme, we ¯rst determine whether the object is leaving the edge and entering another one. If it is moving to another edge, we delete it from the old AU (if it is the last object in the old AU, the AU is also dropped) and insert it into the nearest AU or create a new AU in the edge it is entering. Otherwise, we do not update the AU that the object belongs to unless its position exceeds the bounds of the AU. In that case, we execute the same updates as those when it moves to another edge or only revise the predicted trajectory bounds of the AU. Factually, we ¯nd, from the experiment evaluation, that the chances that objects move beyond the trajectory bounds of its AU on an edge are very slim. The algorithm 1 shows the update algorithm of AUs.
Algorithm 1: Update(objID; position; velocity; edgeID) input : objID is the object identi¯er, position and velocity are its position and velocity, edgeID is the edge identi¯er where the object lies Find AU where objID is included before update; if AU:edgeID 6= edgeID or (position < AU:lowerBound or position > AU:upperBound) then // The object moves to a new edge or
exceeds bounds of its original AU Find the nearest AU AU1 for objID on edgeID; if GetNum(AU1:objSet) < M AXOBJN U M and ObjectFitAU(objID; position; velocity; AU1) then
InsertObject(objID; AU1:auID; AU1:edgeID); else AU2 Ã CreateAU(objID,edgeID); if GetNum(AU:objSet) > 1 then
DeleteObject(objID; AU:auID; AU:edgeID); else DropAU(AU:edgeID; AU:auID); end
In summary, updating the AU-based index is easier than updating the TPR-tree. It never invoke any complex node splitting and merging. Moreover, thanks to the similar movement features of objects in an AU and the accurate prediction of the SP method, the objects are seldom removed or added from their AU on an edge, which reduces the number of index updates. 3.5
Query processing in the AU index scheme is straightforward. Given a query, we use the top level R-tree to get the edges involved and then scan the direct access tables of the edges. With the upperBound and the lowerBound in the direct access table, we can easily ¯nd AU entries that intersect the query, and then visit the disk pages to get more information about these AUs. For space limitation, we just take window range query for example. Given a range with (X1; Y1; X2; Y2), we ¯rst perform a spatial range search in the top level R-Tree to locate the edges (e.g. e1; e2; e3; : : :). For each selected edge ei, we transform the original search (X1; Y1; X2; Y2) to a 1D search range (S1; S2) (S1 · S2), where S1 and S2 are the relative distances from the start vertex along the edge ei. In the case of multiple intersecting edges, we can divide the query range into several sub-ranges by edges and apply the transformation method to each edge. The method is also applicable to the various modes that the query and edges intersect. Here, we only illustrate the case when the query window range only intersects one edge and compute its relative distances S1 and S2. It can be easily extended to other cases. Suppose Xstart; Ystart; Xend; Yend are the start vertex coordinates and the end vertex coordinates of the edge ei. According to Thales Theorem about similar triangles, we obtain S1 and S2 as follows: r =
p(Xstart ¡ Xend)2 + (Ystart ¡ Yend)2 S1 S2 = =
Xend ¡ Xstart
Yend ¡ Ystart
The transformed query (S1; S2) is then executed in each of the AUs in the direct access table of the corresponding edge ei. By the trajectory bounds of the AU, we can determine whether the transformed query intersects the AU, thus ¯ltering the unnecessary AUs quickly. Finally, we access the selected AUs in disk storage and return the objects satisfying the query window. In summary, the query processing is e±cient due to the grouping of similar objects in AUs and the dimensionality reduction of the query. 4
We evaluate the AU index scheme (denoted as \AU index") by comparing it with the TPR-tree and the AU index scheme when the direct access table is not used (denoted as \AU index without DT"). We measure their their update performance with the individual update, update frequency and total update costs and their query performance. 4.1
We use two datasets for our experiments. The ¯rst
is generated by the CA simulator, and the second by
the Brinkho®'s Network-based Generator [
We study the individual update performance of the index while varying the number of moving objects and updates. Figure 3 shows the average individual update cost when increasing the data size from 10K to 100K. Figure 4 shows how the performance varies over time. Clearly, updating the TPR-tree tends to be costly, and the problem is exacerbated when the data size increases. In each case of di®erent data size and di®erent number of updates, the AU index has much lower update cost than the TPR-tree. The main reason can be explained as follows. Each update of the TPR-tree involves the search of an old entry and a new entry, as well as the modi¯cation of the index structure (node splitting, merging, and the propagating of changes upwards). The cost increases with larger data size due to more overlaps among MBRs. The changes of index structure with the increase of data updates also a®ect the performance of the TPR-tree. However, the AU index has better performance because its update only restricts to the AU's update and as a one-dimensional access structure, the AU has few overlaps and incurs no cost associated with node splitting and the propagation of MBR updates.
The direct access table of the AU index has a significant contribution in improving update performance. This is because the search of the speci¯c AU is accelerated by the in-memory structure.
Frequent updates of moving objects (a.k.a. data updates) may lead to frequent updates of index. When an object's position exceeds the MBR or AU, the index needs to be updated to delete the object from the old MBR or AU and insert it to another one. In this experiment, we measure the index update rate, which is 14 ()s% 12 tade 10 xuep 8 ifnd 6 o tae 4 R 2 10K 14 AU-index wAithUo-uintdDeTx 12 TPR-tree /sO 10 tIea 8 pdU 6 4 2 100K 300K 500K 700K 900K
Number of data updates (a) Brinkho® 14 AU-index wAithUo-uintdDeTx 12 TPR-tree /sO 10 tIea 8 pdU 6 4 2 100K 300K 500K 700K 900K
Number of data updates (b) CA
The total update costs depend on the update frequency and the average individual update cost, and it can re°ect the index update performance more accurately. From both Figure 7 and 8, we can see that although the AU index has to deal with the creation and dropping of AUs, the TPR-tree incurs much higher update costs than the AU index and its performance deteriorates dramatically as data size increases. This is mainly due to the inaccuracy of the linear prediction model and the complex reconstruction of the TPR-tree (e.g. splitting and merging). R 2 100K 300K 500K 700K 900K
Number of data updates (a) Brinkho® 90K 30K 50K 70K
Number of moving objects (a) Brinkho® 90K 30K 50K 70K
Number of moving objects (b) CA 90K We study the window range query performance of the TPR-tree and the AU index with di®erent update settings. We increase the number of updates from 100K to 1M to examine how query performance is a®ected. We issued 200 range queries for every 100K updates in a 1M dataset. Figure 9 shows that the cost of the TPR-tree increases much faster as the number of updates increases. The cost of the AU index is considerably lower and is less sensitive to the number of updates. This is because the adaptive units in the AU index have much less overlaps than the MBRs in the TPR-tree, and the overlaps to a large extent determine the range query cost. Besides, as objects move apart, the amount of dead space in the TPR-tree increases, Program for New Century Excellent Talents in University (NCET); Program for Creative PhD Thesis in University. The authors would like to thank Jianliang Xu and Haibo Hu from Hong Kong Baptist University and St¶ephane Grumbach from CNRS, LIAMA in China for many helpful advice and assistance.
AU-index AU-index without DT
TPR-tree which makes false hits more likely. Also, updates lead to the expanding and overlaps of MBRs, which further deteriorate the performance of the TPR-tree. For the AU index, the increase of the updates hardly a®ect the total number of AUs, and the chances of overlaps of di®erent AUs are very slim.
We also study the query performance while varying the number of moving objects and query window size. For the space limitation, we do not report the experimental results. Also, in each case, the AU index has lower query cost than the TPR-tree and scales well. 1200 AU-index 1000 AU-index wiTthPoRu-ttrDeTe /IsO 800 y rueq 600 e ang 400 R 200 1000K 300K 500K 700K 900K
Number of data updates (a) Brinkho® 100 90 /sO 80 I rye 70 eqgu 60 anR 50 40 31000K
Indexing objects moving in a constrained network especially the road network is a topic of great practical importance. We focus on the index update issue for the current positions of network-constrained moving objects. We introduce a new access structure, adaptive unit that exploits as much as possible the characteristics of the movements of objects. The updates of the structure are minimized by an accurate prediction method which produces two trajectory bounds based on di®erent assumptions on the tra±c conditions. The e±ciency of the structure also results from the possible reduction of dimensionality of the trajectory data to be indexed. Our experimental results performed on two datasets show that the e±ciency of the index structure is one order of magnitude higher than the TPR-tree.
In the future, we will compare the update
performance with the work of the R-tree-based updating
optimization such as RUM-tree [
This research was partially supported by the grants from the Natural Science Foundation of China under grant number 60573091, 60273018; the Key Project of Ministry of Education of China under Grant No.03044;