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

Algorithm 7: Partition_windowPair ()
Input: k 2 ,W 1 ,W 2 . k 2 = ( part,win, prevPart ), W 1 and W 2 are the last two
components of the job input directory name job_inDir
Output: k 2's partition number
1: if win = − 1 then // base partition
2: partition ← ( part × C 4) mod NUMPARTITIONS
3: else // window-pair partition
4: minVal ← min ( part,win )
5: maxVal ← max ( part,win )
6: if ( part > win ∧ prevPart = W 1) ∨ ( part < win ∧ prev Part = W 2) then
7: partition ← ( minVal ×C 5+ maxVal ×C 6) mod NUMPARTITIONS
8: else // ( part > win ∧ prevPart = W 2) ∨ ( part < win ∧ prevPart = W 1)
9: partition ← ( minVal ×C 7+ maxVal ×C 8) mod NUMPARTITIONS
10: end if
11: end if

∨ ( part < win ∧ prevPart = W 2) then

In the scenario of Fig. 7, Partition_windowPair will generate the
same partition number, i.e. ( Q 0 × C 4) mod NUMPARTITIONS , for all the
intermediate keys that correspond to partition Q 0. Similarly, the function
will generate the same partition number, i.e. ( Q 0 × C 7 + Q 1 × C 8) mod
NUMPARTITIONS , for all the intermediate keys that correspond to partition
Q 0_ Q 1{1}. The partition number of the records in Q 0_ Q 1{1} is generated in
line 9 while the partition number of the records in Q 0_ Q 1{2} is generated in
line 7. We use the numbers 1 and 2 at the end of the window-pair partitions'
names to differentiate between them. We reference this number as the
window-pair sequence .
After generating the partition numbers of intermediate records, the
records are sent to their corresponding reduce nodes. In a window-pair
partition round, the records received at each reduce node are sorted and
grouped using the Compare _ windowPair function presented in Algorithm
8. This function groups all the records that belong to the same partition
establishing the order of partitions shown in Fig. 8a.
Compare_windowPair receives as input two intermediate record keys,
i.e., k 2 1 , k 2 2 , and returns 0, − 1 or +1 depending on the order of the associated
partitions. The algorithm considers all the possible combinations of the
intermediate keys. All the cases are processed as in Compare_base with the
exception of the case where both keys belong to window-pair partitions. In
this case, Compare_windowPair orders them based on the tuple (minimum
pivot index, maximum pivot index, window-pair sequence) using
lexicographical order (lines 11 to 55).
Several sub-cases are considered. When the keys do not belong to
the windows between the same pair of pivots, they are ordered based on
(minimum pivot index, maximum pivot index) (lines 14 to 20). Otherwise,