Database Reference
In-Depth Information
s
6
10:28
s
5
10:25
S
s
4
10:22
R
s
1
9:50
s
3
10:17
r
8
10:29
s
2
10:09
r
7
10:24
r
6
10:21
r
1
10:01
r
2
10:10
r
5
10:20
r
4
10:18
r
3
10:15
Fig. 12.5
In this example from [
26
], object
R
follows object
S
from
10:01
to
10:20
and moves
together afterwards. Even though
R
follows
S
,
s
2
is not in the front region of
r
2
this example,
r
2
is heading downwards at 10:10, and
s
2
is apparently not in the front
region of
r
2
. The definition of front region and the constraint on being in the front
region for k consecutive timestamps are too strict to make the method applicable on
real data.
Li et al. [
26
] propose a more relaxed definition of following pattern. Given
thresholds
d
max
and
l
max
, a location pair (
r
i
,
s
j
) is said to be a
following pair
if
l
max
. By considering a following pair as a
matching, the problem can be mapped to local sequence alignment (LSA) problem.
Smith-Waterman algorithm [
33
] can be applied to find the longest following interval
(best local alignment).
However, experimental results show LSA is sensitive to the parameter
d
max
.To
address the problem, Li et al. [
26
] further propose the concept of local distance
minimizer. The intuition is that if object
R
is following
S
at timestamp
i
, then there
must exit a
strictly positive integer
(
i
) such that
r
i
is spatially close to
s
i
−
(
i
)
.In
fact, the distance between
r
i
and
S
should be minimized
locally
at such
(
i
). Based
on the intuition,
f
(
i
) is defined as whether
r
i
is following
s
i
at timestamp
i
:
r
i
−
s
j
<d
max
and 0
<i
−
j
≤
⎧
⎨
1,
if
(
i
)
>
0 and
r
i
−
s
i
−
(
i
)
<d
max
f
(
i
)
=
0,
if
(
i
)
≤
0 and
r
i
−
s
i
−
(
i
)
<d
max
⎩
d
max
Then the following interval [
s
,
t
] should make
s
f
(
i
) maximized. The problem
can be transformed to the well-known Maximum Sum Segment problem and all the
following intervals can be found in linear time.
×
,
if
r
i
−
s
i
−
(
i
)
≥
