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

Algorithm 8 Part 2: Compare_windowPair ()
34 : else // ( prevPart 1 = W 2 ) ∧ ( prevPart 2 = W 1 )
35 : return -1
36 : end if
37 : end if
38 : end if
39 : if ( prevPart 1 = prevPart 2 ) then // ≠ partitions, = old partitions
40 : if prevPart 1 = win 1 then // prevPart 2 = win 1
41 : if part 1 < win 1 then // part 2 > win 2
42 : return -1
43 : else // ( part 1 > win 1 ) ∧ ( part 2 < win 2 )
44 : return + 1
45 : end if
46 : else // prevPart 1 = win 2 ∧ prevPart 2 = win 2
47 : if part 1 < win 1 then // part 2 > win 2
48 : return +1
49 : else // ( part 1 > win 1 ) ∧ ( part 2 < win 2 )
50 : return - 1
51 : end if
52 : end if
53: end if
54: return 0 // ≠ partitions, ≠ old partitions
55: end if

then

part 1 win 1 part 2

High order

Q1_Q2{2}

Q0_Q1{2} (( 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 ))

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

Q1_Q2{1}

Q0_Q2{2}

Q0_Q1{1} (( 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_Q2{1}

Q0_Q1{2}

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

Q0_Q1{1}

Q1

Base
partitions.
Ordered by
pivot index

Q2

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

Q1

Q0

Q0

Low order

(c) Order of
partitions
with 3 pivots

(a) General order
of partitions

(b) Order of partitions
with 2 pivots

Fig. 8. Group formation in a window-pair round.