Database Reference
In-Depth Information
Many clustering techniques (discussed in Chapter
6
), such as the popular
k
-means, can be applied to the trajectory setting using a so-called
distance func-
tion
between trajectories, which measures the similarity between trajectories.
This leads to the notion of
distance-based clustering.
Clustering trajectory data
usually produces groups containing geographically close trajectories. Many dif-
ferent distance functions can be defined, ranging from the most simple ones (for
instance, clustering trajectories with the same origin and/or destination), to very
complex mathematical functions.
The space-time prism approach allows defining a distance function for tra-
jectories that accounts for uncertainty. Let us consider two trajectory samples
T
1and
T
2, such that their uncertainty is represented by two lifeline necklaces,
N
1
and
N
2
, respectively, that connect consecutive sample points of each tra-
jectory. Intuitively, the larger the intersection of the necklaces with respect to
their union, the smaller the distance between both trajectories. In other words,
the more uncertainty shared by
T
1and
T
2
,
the closer they are. On the other
hand, if
N
1
and
N
2
do not intersect, this indicates that these trajectories could
not have met, given the speed limit. Then, a clustering algorithm should not
group together these two trajectories. We can conjecture that the temporal pro-
jection of the intersection of the space-time prisms of two trajectories represents
the instants when the two trajectories
could have met.
Therefore, the longer
this period, the more similar the trajectories are. This notion is captured by
Definition
5.9
.
Definition 5.9. Let us denote
A
and
B
two necklaces corresponding to two
trajectory samples
τ
1
and
τ
2
, respectively; also, we denote
V
C
the volume of a
3-dimensional figure
C
. Then, the expression
V
A
∩
B
V
A
∪
B
d
u
(
A, B
)
=
1
−
is named the
uncertainty-based distance
between
τ
1
and
τ
2
.
It can be proved that
d
u
(
A, B
) is a distance metric, that is, it verifies
identity (
∀
i
:
d
(
i, j
)
=
0iff
i
=
j
), positive definiteness (
∀
i, j, i
=
j
:
d
(
i, j
)
>
0), symmetry (
d
(
i, j
)
=
d
(
j, i
)), and triangle inequality (
∀
i, j, k
:
d
(
i, j
)
+
d
(
j, k
)
≥
d
(
i, k
)).
The most difficult part of applying this uncertainty-aware distance function
consists in the computation of the intersection between two chains of space-time
prisms for any given two trajectories whose distance we need to calculate. To
make this computation more efficient, information related to the road network
can be preprocessed. The reader is encouraged to check the bibliographic notes
of this chapter, where references to works describing this computation are given.
