Global Positioning System Reference
In-Depth Information
Algorithm 2:
Map_base
()
Input: (
k
1
, v
1).
k
1 =
id, v
1 = (
id, elem
)
Output: list(
k
2
, v
2).
k
2 = (
part,win
),
v
2 = (
id, elem, part
)
1
:
p ĸ GetClosestPivotIndx
(
elem, pivots
)
2
: output ((
p,í
1)
,
(
id, elem,í
1))
3
: for
i
= 0
ĺ numPiv í
1 do
4
: if
i p
then
5
: if (
dist
(
elem, pivots
[
i
])
ídist
(
elem, pivots
[
p
]))
/
2
eps
then
6
: output ((
p, i
)
,
(
id, elem, p
))
7
: end if
8
: end if
9
: end for
p
and
i
) that
elem
belongs to (lines 3 to 9). Figure 5 shows an example of the
intermediate key-value pairs generated by
Map_base
. Region
T
contains all
the key-value pairs of the job input data. Different subsets of this region are
processed by different
map
tasks on possibly different nodes.
The overall result of the
map
phase is independent of the number or
distribution of the
map
tasks. In this example, they will always generate the
key-value pairs shown in partitions
P
0,
P
1 and
P
0_
P
1. Each input record
generates an intermediate key-value pair corresponding to its associated
base partition (
P
0 or
P
1). Additionally, each record in the windows
between the two base partitions, e.g.,
id
5 and
id
6, generates a key-value
pair corresponding to the window-pair partition
P
0_
P
1.
T
(id
2
, (id
2
,elem
2
))
(id
1
, (id
1
,elem
1
))
P
0
P
1
(id
3
, (id
3
,elem
3
))
(id
4
, (id
4
,elem
4
))
(id
6
, (id
6
,elem
6
))
(id
5
, (id
5
,elem
5
))
εε
((
P
1
,-1), (id
2
,elem
2
))
((
P
0
,-1), (id
1
,elem
1
))
((
P
0
,
P
1
),
(id
5
,elem
5
,
P
0
))
((
P
0
,-1), (id
3
,elem
3
))
((P
1
,-1), (id
4
,elem
4
))
((P
1
,-1), (id
6
,elem
6
))
((P
1
,P
0
),
(id
6
,elem
6
,P
1
))
((
P
0
,-1), (id
5
,elem
5
))
P0
P1
P0_P1
Base Partitions
Window-pair Partition
Fig. 5.
Example of the Map function for a base round.
Search WWH ::
Custom Search