A large clustering dataset may be too slow to process sequentially, but distributing the work creates another problem: who combines the results? If every worker sends its output to one coordinating process, that process can become the bottleneck. MapReduce separates the work into mapping independent data shards and reducing their intermediate results. section 13.0 section 13.2.2
Design a MapReduce job around what each step needs:
- Shard the input so mappers can process their assigned pieces independently. section 13.2.2
- Have mappers produce intermediate results for the appropriate reducers. Reducers read those results; they need not pass through the leader node. section 13.2.2
- Keep shared state small. Immutability and pure functions help express independent work, while the infrastructure handles necessary synchronization. section 13.2.3
A leader still assigns shards, plans routing, manages workers, and handles errors. It does not read and compute the input itself. A failed machine can therefore be replaced without restarting the entire computation. The model is less suitable when a problem cannot be expressed without substantial shared state. section 13.2.2 section 13.2.3
Iterative k-means
Give every mapper a shard of points and the current centroids. Each mapper assigns its points to centroids; reducers group the assignments by centroid and compute new centers of mass. Repeat until the centroids stop changing or the iteration limit is reached. Initialization needs separate thought: canopy clustering can supply initial centroids, whereas random samples drawn independently from shards may not be uniform across the whole dataset. section 13.3
Listing 13.2 MapReduce k-means
function MRkmeans(points, numShards, numClusters, maxIter, T1, T2) #1
shards ← randomShard(points, numShards) #2
centroids ← MRcanopyCentroids(points, numClusters, T1, T2) #3
mappers ← initMappers(numShards, classifyPoints, shards) #4
reducers ← initReducers(numClusters, centerOfMass) #5
for i in {0, .., maxIter-1} do #6
newCentroids ← mapReduce(centroids, mappers, reducers) #7
if centroids == newCentroids then #8
break
else
centroids ← newCentroids #9
return combine(mappers, centroids) #10
The pseudocode shows sharding, canopy-based initialization, repeated map–reduce updates, and the stopping test in one workflow. section 13.3
Partitioning must preserve the information an algorithm needs. DBSCAN is harder to distribute than k-means because splitting neighboring points across shards can hide core points. Its distributed design extends grid cells by ε so border points retain their ε-neighborhoods, runs DBSCAN on the resulting shards, then merges clusters across adjacent cells. That overlap adds work, but avoids treating the shards as unrelated datasets. section 13.4
Figure 13.12 Sharding data for MapReduce DBSCAN (MR-DBSCAN). After dividing the domain into equally sized cells, for each shard we need to include all points in one cell, plus all the points within a distance equal to ϵ from its borders. In practice, instead of the cells, we take a rectangle obtained by stretching the cell further in all directions, and each of the sides will measure like the corresponding cell’s side plus 2ϵ. This way, core points close to the cells’ borders will have their ϵ-neighborhood contained in either shard.
The diagram shows why DBSCAN shards include an ε-wide margin beyond each grid cell. section 13.4
