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

High order

P1_P2

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

Window-pair
partitions. Ordered
by (min pivot index,
max pivot index)

P0_P1

P0_P2

(( P 1 ,-1), (id 2 ,elem 2 ))
(( P 1 ,-1), (id 4 ,elem 4 ))
(( P 1 ,-1), (id 6 ,elem 6 ))

P0_P1

P1

P2

Base partitions.
Ordered by pivot
index

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

P1

P0

P0

Low order

(c) Order of
partitions
with 3 pivots

(b) Order of partitions
with 2 pivots

(a) General order of
partitions

Fig. 6. Group formation in a base round.

After generating the groups in a reduce node, the MapReduce
framework calls the reduce function Reduce_base once for each group. This
function is presented in Algorithm 5. The function receives as input the
key-value pair ( k 2 , v 2 List ). k 2 is the intermediate key of one of the records
of the group being processed and v 2 List is the list of values of all the
records of the group. If the size of the list is small enough to be processed
in a single node, the algorithm calls a single-node Similarity Join routine,
i.e., InMemorySimJoin , to get the links in the current partition (lines 1 to 2).
Otherwise all the records of the group are stored in an intermediate directory
for further partitioning. If the current group is a base partition, then the

Algorithm 5: Reduce_base ()
Input: ( k 2 , v 2 List ). k 2 = ( kPart, kWin ), v 2 List = list( id, elem, part )
Output: SJ matches or intermediate data. Intermediate data = list( k 3 , v 3).
k 3 = id , v 3 = ( id, elem [ , part ])
1 : if sizeInBytes ( v 2 List ) memT then
2 : InMemorySimJoin ( v 2 List, outDir, eps )
3 : else
4 : if kWin = í 1 then
5 : for each element e of v 2 List do
6 : output ( e.id, ( e.id, e.elem )) to outDir /intermedi-
ate/B_ ۦ roundNum ̴ۧۦ kPart ۧ
7 : end for
8 : else
9 : for each element e of v 2 List do
10 : output ( e.id, ( e.id, e.elem, e.part )) to outDir /inter-
mediate/W_ ۦ roundNum ۧ _0_ ۦ kPart ۧ _ ۦ kWin ۧ
11 : end for
12 : end if
13 : end if