Database Reference
In-Depth Information
2. The second part (lines 7 to 10) copies and deletes the remaining user profiles
(from position
i
to
N
)fromthe
U-Net
to the candidates (2
a
) list because
their scores need to be recomputed using Formula 7 and with respect to the
best user profile in
candidates
(computed in part 1). Then, the best user
profile is inserted in position
i
. In the on-going example of Figure 1, the user
profiles
v
3
,v
4
,v
5
are copied and removed from the
U-Net
to the candidates
list and user profile
v
7
is added in the
U-Net
at position 3 (2
a
and 2
b
).
3. Finally, in the last part (lines 11 to 15), the algorithm iteratively computes,
for each empty position
i
in the
U-Net
(positions emptied in part 2), the
scores of the user profiles in the candidates list using Formula 7 and taking
into account the set of users in the
U-Net
at positions 1
, ..., i−
1 (lines 12 and
13 and step 3
a
in the figure). Then, the most useful candidate is moved to
the
U-Net
at that position (line 15 and step 3
b
in the figure). The algorithm
repeats these steps until all the positions in
U-Net
are filled out (line 11).
Recall that gossip protocols converge quickly [3]. As a consequence the
U-
Net
will also converge quickly and, in general, tends to stabilize. Therefore, the
algorithm will stop at step 1
b
more and more frequently.
Algorithm 1.
Useful
U-Net
Input
:
u
profile,
U-Net
u
(array[1..N]),
RandomView
u
Output
:
U-Net
u
is updated with respect to the
RandomView
candidates
:
unsorted list of user profiles
;
1
candidates ← RandomView
u
− U-Net
u
;
best ←∅
;
i ←
0;
2
repeat
3
i
++;
4
for
each
c
j
∈
candidates
do
score
(
c
j
)
←
usefulness
(
c
j
,
u
,
U-Net
u
[1
..i −
1])
5
best
←
arg max
c∈candidates
(
score
(
c
));
until
i=N
or
score
(
best
)
> score
(
U-Net
[
i
]);
6
if
score
(
best
)
> score
(
U-Net
[
i
])
then
7
after← U-Net
u
[
i..N
];
U-Net
u
[
i
]
← best
;
i
++;
8
candidates
←
candidates
−
best
;
9
candidates ← after ∪ candidates
;
U-Net
u
← U-Net
u
− after
;
10
while
i<N
and
candidates
=
∅
do
11
for
each
c
j
∈ candidates
do
12
score
(
c
j
)
←
usefulness
(
c
j
,u,U-Net
u
[1
..i −
1]);
13
best
←
arg max
c∈candidates
(
score
(
c
));
U-Net
u
[
i
]
←
best
;
14
candidates ← candidates
− best
;
i
++;
15
4 Experimental Evaluation
In this section, we provide an experimental evaluation to validate our approach
and compare it to other state-of-the-art solutions. We conducted a set of experi-
ments using three datasets which correspond to
MovieLens
,
Flickr
and
LastFM
.
In Section 4.1, we introduce the experimental setup of our evaluation. Then, in
Section 4.2, we present and discuss the experimental results.
Search WWH ::
Custom Search