Advanced Algorithms and Data Structures

13 Parallel clustering: MapReduce and canopy clustering

This chapter covers

• Understanding parallel and distributed computing
• Canopy clustering
• Parallelizing k-means by leveraging canopy clustering
• Using the MapReduce computational model
• Using MapReduce to write a distributed version of k-means
• Leveraging MapReduce canopy clustering
• Working with MR-DBSCAN

In the previous chapter we introduced clustering and described three different approaches to data partitioning: k-means, DBSCAN, and OPTICS.

All these algorithms use a single-thread approach, where all the operations are executed sequentially in the same thread.¹ This is the point where we should question our design: Is it really necessary to run these algorithms sequentially?

During the ...