Algorithm 2

FASTPAM1 algorithm. This algorithm exchanges one point at a time between the current set of medoids and the rest of the points selecting the exchange that most reduces TD. Many possible swaps are eliminated by clever use of two arrays of distances, \(d_{nearest}\) and \(d_{second}\) which hold the distances of each point to its nearest and to its second-nearest medoid; they must be updated (loop in lines 30–32). The global structure contains two nested loops (lines 9–28 and lines 12–21). Our implementation runs the inner one (lines 12–21) in parallel dividing the set of points into as many groups as simultaneous threads.