Transcript Indexing of Network Constrained Moving Objects

Indexing of Network
Constrained Moving
Objects
Dieter Pfoser
Christian S. Jensen
Chia-Yu Chang
Outline
Introduction
The Trajectory Case
Reducing Dimensionality
Performance Studies
Conclusions
2
Introduction (1/2)
Concern with the indexing of the movements of
mobile objects for post-processing (e.g. data
mining) purpose.
The movement of an object may be represented
by a trajectory, or polyline, in the three
dimensional (x, y, t) space.
time
y
x
3
Introduction (2/2)
Three movement scenarios:
1. Unconstrained movement (vessels at sea)
2. Constrained movement (pedestrians)
3. Movement in transportation networks (trains, cars)
4
The Trajectory Case
First approach: simply store the position.
→we couldn’t answer queries about the object’s
movements at time s in-between those of the
sampled positions.
→use linear interpolation
5
Indexing Trajectory
Trajectory are 3D spatial entities, and they can
be indexed using spatial methods.
The R-tree approximates the data objects by Minimum
Bounding Boxes (MBBs).
Large amounts of
“dead space”.
6
Reducing Dimensionality
Translate 2D (network) into one Dimension.
Translate 3D into two Dimensions.
e.g., cars move on roads.
Overall, we have to devise mappings for
1. the Network
2. the Trajectories
3. the Queries
7
Network Mapping (1/2)
Algorithm NetworkMapping (network)
LOCALS
range //highest coordinate
low
//lower coordinate of edge in 1D space
up
//upper coordinate of edge in 1D space
NM1
sort edges by their Hilbert value
FOR ALL edges
NM2
compute length of edge
NM3
low = range+ 1
NM4
up = range+ 1+ length
NM5
write edge(low, up)
NM6
range = up
END FOR
8
Network Mapping (2/2)
Algorithm NetworkMapping (network)
FOR ALL edges
NM2
compute length of edge
NM3
low = range+ 1
NM4
up = range+ 1+ length
NM5
write edge (low, up)
NM6
range = up
END FOR
9
Trajectory Mapping (1/2)
Algorithm TrajectoryMapping (trajectory, 2Dnetwork, 1Dnetwork)
FOR ALL segments of the trajectory
TM1
find traversed network edge in 2Dnetwork
TM2
det. traversed portion of edge in 2Dnetwork
TM3
x0, x1 = respective 1Dnetwork coordinates
TM4
write segment(x0, t0, x1, t1)
END FOR
10
Trajectory Mapping (2/2)
Algorithm TrajectoryMapping (trajectory, 2Dnetwork, 1Dnetwork)
FOR ALL segments of the trajectory
TM1
find traversed network edge in 2Dnetwork
TM2
det. traversed portion of edge in 2Dnetwork
TM3
x0, x1 = respective 1Dnetwork coordinates
TM4
write segment(x0, t0, x1, t1)
END FOR
11
Query Mapping
Algorithm QueryMapping(query, 2Dnetwork)
//2Dnetwork access using an R-tree structure
QM1 given a query window, take the spatial extent and retrieve the
portion contained in it
QM2 lift the retrieved edges by the temporal extent of the query window
12
Performance Studies (1/9)
Three synthetic networks:
1. Hilbert network, “h” , 1023
2. Raster network, “r2” , 544
3. Parallel network, “p” , 33
13
Performance Studies (2/9)
Two real networks:
1. San Jose, CA , 24123
2. Oldenburg, Germany, 7035
14
Performance Studies (3/9)
Index structure for 3D and 2D Trajectory:
R-Tree implementation in C.
Page size of each node is 1024 bytes which
results in maximum fanouts of 36 for 3D and
51 for 2D indexes.
Different types of networks.
The impact of varying number of edges.
→ r1 (144), r2 (544), r2 (2112), r4 (8320)
15
Performance Studies (4/9)
500 moving objects which positions are sampled
250 times each.
→ 125k trajectory segments each.
Sizes of 2D and 3D indexes are 2.5MB and
3.35MB.
500 quadratic query windows, each with spatial
extents of 0.25%, 0.5%, 1%, 2%, 4%, and 8%
of the quadratic 2D space.
Temporal extent of the query was kept constant
at 10%.
16
Performance Studies (5/9)
Different types of synthetic networks:
17
Performance Studies (6/9)
Networks of the same type but varying lengths and
numbers of edges:
18
Performance Studies (7/9)
Varying temporal extent for the Raster network:
19
Performance Studies (8/9)
Different types of real networks:
20
Performance Studies (9/9)
Different types of real networks:
21
Conclusion
The dimensionality of trajectories can be reduced
from three to two.
The number of 2D queries that result from the
mapping of a 3D query is critical. The larger it is,
the less likely it is that the mapping approach
outperforms querying data in the original space.
The lower complexity of a network, the more
likely the mapping approach proves to be
beneficial over indexing the data in 3D space.
22