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