Transcript PPT

Spatio-Temporal Databases
Moving Objects
Introduction





Spatiotemporal Databases: manage spatial data
whose geometry changes over time
Geometry: position and/or extent
Global change data: climate or land cover
changes
Transportation: cars, airplanes
Animated movies/video DBs
Spatio-temporal Queries


Historical Queries: Store the past the history of
a spatio-temporal evolution.
 R-tree, MV3R-tree (PPR-tree)
“Future” Queries: Find the future positions of
moving objects.
 Indexing?
Indexing moving objects


Database stores the current location of each
object and the velocity vector.
Example: cars moving in a highway system. GPS
can provide position/velocity
Moving Objects: Queries



Range Queries
NN queries
Aggregation queries
Q
Moving Objects:Representation


Consider the 1-d case (objects moving on a line)
Storing the locations of moving objects is a challenge:
 Update the database with the new locations
 Use a function of time f(t) to store a location

f (t )  v t  u

Update overhead is reduced; update the database only
when velocity changes
Space-time

Trajectories are plotted as lines in the
time-location space (y, t); p(t) = vt+a
trajectories
o1
o2
o3
o4
(t) time
Indexing



Use R-tree to index the lines Large MBRs, extensive
overlap
Use a Quadtree approach (or a grid)
 Partition the space into cells, store for each cell the
lines that intersect it
Disk space is increased
Dual space-time

Idea: map a line to a point
y  vt  a  (v, a)
(y) location
intercept
trajectories
o1
o1
o2
o3
o4
o2
o3
(t) time
intercept
slope
Dual space-time indexing

Query must be transformed. [(y1q, y2q), (t1q, t2q)]


a + t2qv >= y1q and a+ t1q v <= y2q , for v>0
a + t1qv >= y1q and a+ t2q v <= y2q , for v<0
a
y2q
y1q
vmin
vmax
v
Dual space-time indexing

Another transformation (Hough-Y) is:
ty


1 a
1 a
  ( , )
v v
v
v
The difference is that we compute the
intercept over a horizontal line
Queries in the dual space are similar with
the previous transformation
Hough-Y space
u
1/vmin
E2
E1
1/vmax
t1q
t2q
b
Querying the dual space



Use a PAM to index the dual points, change
the search function to find the points inside
the query
Problem: Partitioning is not aligned with the
queries  many I/Os
An idea is to try to store multiple structures,
one for each set of queries with similar slope
Improving the query

In the Hough-Y, the slope of the queries is y1q
– yr (or y2q – yr)
location
y3
y2
query
y1
time
Improving the query




Compute the dual using multiple y-lines
Store an R-tree for each line
Given a query, find the line that is closer to the
query and then use the corresponding index
Thus, the query will appear as vertical as
possible  better performance
Indexing in 2-dimensions



The dual transformation can be extended to 2
dimensional points
Map the trajectories in a point in 4-d using
the transformations on x-t and y-t planes
Use the 1-d structures to answer a query
Dual for 2-D Moving Objects

Using Hough-X:





Map a moving point p with location (px, py) and
velocity (vx, vy) to the 4D point (vx, ax, vy, ay)
Query is also transformed to a linear constraint
query:
Q=[(x1q, x2q), (y1q, y2q), (t1q, t2q)]
ax + t2qvx >= x1q and ax+ t1q vx <= x2q
ay + t2qvy >= y1q and ay+ t1q vy <= y2q
x1qvy - y2qvx <= axvy – ayvx<= x2qvy - y1q vx
TP R-tree



Time-Parametrized R-tree
Store the MBRs as functions of time
The MBRs grow with time, at any time
instant in the future we can compute
the “MBR”
Motion function
y axis
y axis
10
10
1
8
-1
-2
6
4
2
1
-2 b
1 -2
-2
d
-1
8
1
6
2
-2
a
b
2
at time 0
c
a
4
c
1
1
d
at time 1
x axis
0

2
4
6
8
10
x axis
0
2
4
6
8
10
For each object, the database stores




Its minimum bounding rectangle (MBR) at the reference time 0
Its current velocity bounding rectangle (VBR)
Examples: MBR(a)={2,4,3,4}, VBR(a)={1,1,1,1};
MBR(c)={8,9,8,9}
An update is necessary only when an object’s VBR changes.
TPR – MBRs
y axis
y axis
query window
10
8
E
-1
1
1
v
u
4
-1
-1
2
v
6
2
-1
4
query window
E
8
2
u
6
10
2
x axis
0
2
4
6
8
10
(a) The boundaries at current time 0
x axis
0
2
4
6
8
10
(b) The boundaries at future time 1
Insertion and Deletion




Insertion and Deletion similar to R*-tree
The only difference is that you have to compute the
values: margin, overlap, volume over time
Trick: try to optimize the structure for the next H time
instants.
Another optimization: when you update an object, recompute the MBR at the current time
y
o1
o2
o3
o4
t update
time
An example of update and re-computation of MBR (1D)
Reference:
Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez: Indexing the
Positions of Continuously Moving Objects. SIGMOD Conference 2000: 331-342