Global Positioning System Reference
In-Depth Information
illustrates how the region (base partition) is partitioned. In this case, the
result of the Similarity Join operation (pairs of restaurants and theatres) on
the dataset
T
is the union of the pairs in
P0
and
P1
, and the pairs in
P0_P1
where one element belongs to window
A
and the other one to window
B
.
We refer to this last type of pair as
window links
. Figure 3 represents the
repartitioning of the window-pair partition
P
0_
P
1 of Fig. 2. In this case,
the set of window links in
P
0_
P
1 is the union of the window links in
Q
0,
Q
1,
Q
0_
Q
1{1} and
Q
0_
Q
1{2}. Note that other window-pair combinations,
e.g., {
E
,
C
}, {
D
,
F
}, {
E
,
D
}, and {
C
,
F
}, do not form window-pair partitions
because the links that can be identifi ed in these combinations are identifi ed
processing other partitions. Specifi cally, the links in {
E
,
C
} and {
D
,
F
} are
T
AB
P
0
P
1
εε
AB
P0
P1
P0_P1
Window-pair
Partition
Base Partitions
Fig. 2.
Partitioning a base partition.
A
B
A
B
Q1
Q
1
D
E
ε
ε
ED
C
C
F
F
Q
0
Q0_Q1{1}
Q0_Q1{2}
Q0
P0_P1
Window-pair Partitions
Base Partitions
Fig. 3.
Partitioning a window-pair partition.
Search WWH ::
Custom Search