Database Reference
In-Depth Information
Table 12.2 Summary of similarity measures [ 5 ]
Distance
Local time shifting
Noise
Metric
Computation cost
Euclidean
O ( n )
O ( n 2 )
DTW
O ( n 2 )
ERP
O ( n 2 )
LCSS
O ( n 2 )
EDR
to noises because it does not require every point in R to be matched with a point with
S .If r i is a noise point, LCSS and EDR will skip it and assign a mismatch penalty to it.
Euclidean distance and ERP are metric distances since they obey triangle inequality.
Thus, efficient indexing and retrieval can be achieved by using these two distance
measures.
The distance measures mentioned above are suitable to find similar trajectory with
similar shapes. They can be applied on trajectories, such as hurricane trajectories and
animal migration paths. To measure the similarity on human movements, it could
make more sense to look at the co-locating frequency instead of trajectory shape. The
meeting frequency [ 25 ] is defined as the number of timestamps that their locations
are with distance :
n
freq ( R , S )
=
τ ( r i , s i ),
i = 1
where τ ( r i , s i )
0 otherwise.
The similarity between two moving objects can also be measured by transitions
patterns. Li et al. [ 20 ] propose to measure the similarity of two mobile users based
on their location histories. The trajectory is first symbolized using the interesting
locations mined from user trajectory. Given two symbolized sequences seq 1
=
1if dist ( r i , s i )
and τ ( r i , s i )
=
=
t 1
−→
t 2
−→
t 1
−→
t 2
−→
...s m ( k m ),
where t denotes the transition time between locations and k is the number of times
that the user stays in a location, seq 1 and seq 2 are similar if the following constraints
are satisfied:
s 1 ( k 1 )
s 2 ( k 2 )
r 1 ( k 1 )
r 2 ( k 2 )
...r m ( k m ) and seq 2
=
1.
1
i
m , r i =
s i ;
t i
2.
1
i
m ,
|
t i
|≤
t th , where t th is a time threshold on the transition
times.
4.2
Generic Pattern
Relationships between two moving objects can be classified as attraction, avoidance
or neutral. In an attraction relationship, the presence of one individual causes the
other to approach (i.e., reduce the distance between them). As a result, the individuals
have a higher probability to be spatially close than expected based on chance. On
 
Search WWH ::




Custom Search