Similarity Join for Big Geographic Data - Geographical Information Systems: Trends and Technologies - page 37

intermediate key-value pair of the form (( p , − 1, − 1), ( id , elem , − 1, prevPart ))
for the base partition with pivot p that elem belongs to (line 2) and one
key-value pair of the form (( p , i , prevPart ), ( id , elem , p , prevPart )) for each
window-pair partition (corresponding to pivots p and i ) that elem belongs
to (lines 3 to 9). Figure 7 shows an example of the intermediate key-value
pairs generated by Map_windowPair .
The MapReduce framework partitions the intermediate data using
the Partition_windowPair function presented in Algorithm 7. Partition_
windowPair receives an intermediate key, i.e., k 2 = ( part, win, prevPart ), as
input and generates the corresponding partition number. The generation of
the partition number is similar to the process in Partition_base . The difference
is that Partition_windowPair distinguishes between the two window-pair
partitions of any pair of pivots. The correct identifi cation of the specifi c
window-pair a record belongs to is obtained using the information of the
previous partition of the record (lines 6 to 10).

Q 1
(id 2 , (id 2 ,elem 2 ,P 1 ))

(id 1 , (id 1 ,elem 1 , P 0 ))
(id 3 , (id 3 ,elem 3 , P 0 ))

(id 4 , (id 4 ,elem 4 ,P 1 ))
(id 5 , (id 5 ,elem 5 ,P 1 ))

(id 6 , (id 6 ,elem 6 , P 1 ))

Q 0

P0_P1

(( Q 1 , Q 0 , P 1 ),
(id 4 ,elem 4 , Q 1 , P 1 ))
(( Q 0 , Q 1 , P 0 ),
(id 3 ,elem 3 , Q 0 , P 0 ))
Q0_Q1{1}

Q1

(( Q 1 ,-1,-1), (id 2 ,elem 2 ,-1, P 1 ))

(( Q 1 ,-1,-1),
(id 1 ,elem 1 ,-1, P 0 ))
(( Q 0 ,-1,-1),
(id 3 ,elem 3 ,-1, P 0 ))

(( Q 1 ,-1,-1), (id 4 ,elem 4 ,-1, P 1 ))

(( Q 1 , Q 0 , P 0 ),
(id 1 ,elem 1 , Q 1 , P 0 ))
(( Q 0 , Q 1 , P 1 ),
(id 5 ,elem 5 , Q 0 , P 1 ))
Q0_Q1{2}
Window-pair Partitions

(( Q 0 ,-1,-1), (id 5 ,elem 5 ,-1, P 1 ))

(( Q 0 ,-1,-1),
(id 6 ,elem 6 ,-1, P 1 ))

Q0

Base Partitions

Fig. 7. Example of the Map function for a window-pair round.