Suppose a clustering job takes too long because it processes every point sequentially. Parallelism offers a possible speedup: split work into independent pieces and run them at the same time. The first question is not how many workers to launch, but whether each worker can do useful work without waiting for the others. section 13.0 section 13.1
Parallel computing usually means using multiple CPUs on one machine, often through threads. Distributed computing uses CPUs on multiple machines that communicate over a network. A single machine limits the available processors but allows communication through shared memory; distributing work can handle datasets too large for one machine, at the cost of network communication. The same computational design may run in either setting, depending on input size and resources. section 13.1.1
To assess an algorithm, inspect its steps separately rather than treating the whole job as indivisible:
- Skip work too small to benefit. Fully random k-means centroid initialization depends on the number of clusters, not the dataset, so it is not worth parallelizing in that form. section 13.1.2
- Find independent work. During k-means re-centering, each cluster’s center of mass needs only that cluster’s points. One worker can process each cluster. section 13.1.2
- Check how results come back together. Splitting work is insufficient if one process must collect and combine every worker’s output; that process can become the bottleneck. section 13.2.2
For re-centering n points of dimension d across k clusters, the sequential calculation uses n×d sums and k×d divisions. With an even cluster split, each of k workers performs about d×n/k additions and d divisions. A k-fold speedup is an ideal case: it assumes balanced work and workers finishing together at the original processing speed. It is not a guarantee for uneven clusters or other algorithm steps. section 13.1.2
Counting coins without a final counting bottleneck
Divide a large collection of coins into piles and have workers catalog each pile. That speeds up the first pass, but handing every list to one person leaves a large combining job. MapReduce separates the work again: mappers extract coin occurrences from their portions of the input, and reducers receive groups of like entries and count them. The example shows why a parallel design must account for both local computation and aggregation. section 13.2.1 section 13.2.2
Figure 13.6A Comparing the classical approach to parallel computing to MapReduce. We assume that in both cases, data is already broken down into chunks and can be passed by location, that is, by providing something like a file handle without the need for the orchestrator to read the data. In the basic parallel approach, using processes (either running on threads or on different machines), the orchestrator needs to spin up the threads and make sense of their results. It can either combine these results itself, or spawn more processes to combine them (as shown in the figure), but it will be the bottleneck either way.
Compare where intermediate output goes in basic parallel processing: the orchestrator still has to handle workers’ results, making aggregation a potential bottleneck. section 13.2.2
Use parallelism when work can be partitioned and its results combined without erasing the gain. For large-scale clustering, MapReduce provides a distributed model applicable to k-means, canopy clustering, and DBSCAN. The same partitioning question also arises in nearest-neighbor search: searching shards in parallel may help meet a response-time limit, but an approximate approach requires an acceptable accuracy trade-off. section 13.5 section 11.3.1
