Database Reference
In-Depth Information
StateK=Join(StructureK)
Input: StructureK
n
1: return n;
Map(StateK, StateV, StructureV)
Input: StateK
n
, StateV
R
(
n
), StructureV
adj
(
n
)
2:
for
link in
adj
(
n
)
do
3: output( link.endnode, (d ×
R
(
n
))/|
adj
(
n
)|);
4:
end for
5: output(
n
, (1-d)/N);
Reduce(IK, [IV])
Input: Key
n
, Set [
values
]
6: output(
n
, sum([
values
]));
float=Distance(StateK, PrevStateV, CurrStateV)
Input: StateK
n
, PrevStateV
R1
(
n
), CurrStateV
R2
(
n
)
7: return abs(
R1
(
n
) -
R2
(
n
));
Main
8: Job job = new Job();
9: job.setJoin(Join);
10: job.setMap(Map);
11: job.setReduce(Reduce);
12: job.setDistance(Distance);
13: job.set(“mapred.iterjob.state.path”, “hdfs://…/initRankings”);
14: job.set(“mapred.iterjob.structure.path”, “hdfs://…/adjacencylists”);
15: job.setFloat(“mapred.iterjob.disthresh”, 0.01);
16: job.submit();
FIGURE 3.4
PageRank implementation in iMapReduce.
of nodes in the graph. In the reduce function (Line 6), for each node, it updates its
PageRank score by combining the partial PageRank scores from its incoming neigh-
bors and its own retained score. For the distance measurement, the distance function
calculates the Manhattan distance (Line 7). Additionally, users should specify the
location of the initial state data (Line 13), as well as the location of the structure
data (Line 14). iMapReduce supports automatically structure data partition for a
few input data formats (including weighted and unweighted graphs). Users can first
format their input data file in our supported formats. By using the distance-based ter-
mination check method, the iterative computation will terminate when the distance
is smaller than 0.01 (Line 15).
3.5 PERFORMANCE
iMapReduce has much better performance than Hadoop on iterative computations.
Some experiments have been conducted. Four iterative algorithms, Single Source
Shortest Path (SSSP), PageRank, K-means, and MPI, are considered for comparing
iMapReduce with Hadoop. The description of the detailed experiment environment
and the data sets can be found in [21].
Search WWH ::
Custom Search