Algorithm 1

BUILD algorithm. The first initial medoid is found by the loop in lines 5–9. The rest of the medoids require two nested loops (those in lines 10–26 and 13–25). The first loop runs through all points not yet found as medoids. The second loop does the same but takes into account the distance of each point to its closest medoid (\(d_{nearest}\)) to easily calculate the contribution of such point to the global distance, TD. \(d_{nearest}\) must be updated in the inner loop (lines 23–24). Our implementation executes the inner loop (lines 13-25) in parallel by groups of points, dividing the points into as many groups as simultaneous threads.