Global Positioning System Reference
In-Depth Information
algorithm stores its records in a directory that will be processed in a future
base partition round (lines 4 to 7). Likewise, the records of a window-pair
partition are stored in a directory that will be processed in a future window-
pair partition round (lines 8 to 12). In the latter case, the last part of the
directory name includes the indices of the two pivots associated with the
window-pair partition. These values will be used in the algorithms of the
window-pair rounds. In the scenario represented in Fig. 5, the MapReduce
framework calls the
Reduce_base
function for each partition of Fig. 6b:
P
0,
P
1 and
P
0_
P
1.
Window-pair Partition Round
A window-pair partition round processes a window-pair partition
generated by a base round or any partition generated by a window-pair
round. Similarly to base partition rounds, window-pair partition rounds
generate result links and intermediate data. However, the links generated are
window links, i.e., links between records of different previous partitions. A
window-pair round uses the functions
Map_windowPair
,
Reduce_windowPair
,
Partition_windowPair
and
Compare_windowPair
in a similar way their
counterparts are used in a base partition round. This section explains these
functions highlighting the differences.
Map_windowPair
, the map function for the window-pair partition
rounds, is presented in Algorithm 6. In this case, the format of the input key-
value pair, i.e.,
k
1
, v
1, is:
k
1 =
id, v
1 = (
id, elem, prevPart
), and the format of the
intermediate key-value pairs, i.e.,
k
2
, v
2, is:
k
2=(
part
,
win
,
prevPart
),
v
2=(
id
,
elem
,
part
,
prevPart
). The function is similar to
Map_base
. The difference is
in the format of the intermediate records.
Map_windowPair
outputs one
Algorithm 6:
Map_windowPair
()
Input:
(
k
1
, v
1).
k
1 =
id, v
1 = (
id, elem, prevPart
)
Output:
list(
k
2
, v
2).
k
2 = (
part,win, prevPart
),
v
2 = (
id, elem, part,
prevPart
)
1
:
p ← GetClosestPivotIndex
(
elem, pivots
)
2
: output ((
p,−
1
,−
1)
,
(
id, elem,−
1
, prevPart
))
3
:
for
i
= 0
→ numPiv −
1
do
4
:
if
i ≠p
then
5
:
if
(
dist
(
elem, pivots
[
i
])
−dist
(
elem, pivots
[
p
]))
/
2
≤ eps
then
6
: output ((
p, i, prevPart
)
,
(
id, elem, p, prevPart
))
7
:
end if
8
:
end if
9
:
end for
prevPart
)
Search WWH ::
Custom Search