Information Technology Reference
In-Depth Information
5.5 Resampling
Resampling plays a crucial role in maintaining the diversity among particles. Resam-
pling relies on drawing particles from their corresponding weight distribution. To do
so, Lines 1-5 of algorithm R
ESAMPLE
compute a distribution containing prefix sums
of particle weights:
C
i
is the sum of weights
w
1
,w
2
,...,w
i
. In each iteration of the loop
in Lines 6-9, new particle positions are drawn by sampling from
C
.
Algorithm
R
ESAMPLE
Input
: Particle positions and weights (
x
,
s
,
w
)
Output
: Particle positions and weights after resampling (
x
,
s
,
w
)
1
C
0
= 0
2
N
p
= dim
x
3
for
i
= 1
to
N
p
do
C
i
=
C
i−
1
+
w
(
i
)
4
5
end
6
for
i
= 1
to
N
p
do
7
SAMPLE PARTICLE INDEX
k
FROM
C
(
x
(
i
)
, s
(
i
)
, w
(
i
)
) = (
x
(
k
)
,s
(
k
)
,
1
/N
p
)
8
9
end
10
return
(
x
,
s
,
w
)
5.6 Calculating the Probability Distribution
After
T
time steps, the probability distribution
P
(
X
T
,S
T
|
o
1:
T
,
q
1:
T
) is estimated on
Lines 30-31 by summing the weights of particles in each state.
6
Evaluation
In this section, we evaluate the performance of the RVPF algorithm by comparing it to
the RVSE and AP-RVSE algorithms. We conducted multiple experiments focusing on
three important factors:
execution time
,
memory usage
, and state-estimation
accuracy
.
All our experiments were carried out under Fedora Linux 17 on a computer with 4GB
of RAM and a quad-core Intel
R
Core
TM
i5-2500 CPU running at 3.3GHz. For these
experiments, we adapted the existing implementation of AP-RVSE and created new im-
plementations of RVSE and RVPF, reusing relevant parts from the code for AP-RVSE.
All three programs are written in C.
The
micro-benchmark
is a multi-threaded application developed for the purpose of
experimental evaluation of the AP-RVSE algorithm [1]. It consists of five threads con-
currently accessing 100 objects. Each thread can perform four possible operations on
any of the objects: LOCK, UNLOCK, PROT, and UNPROT. Threads choose which of
these operations to execute according to the HMM in Figure 4. The DFA in Figure 3 is
used to check for proper access to the protected fields of each object.
To offer a fair comparison, all three algorithms were evaluated on the same set of
micro-benchmark-generated traces (event sequences), which contain gaps of varying fre-
quency (measured as the percentage of trace elements that are gap symbols) and length.
