A Sub-Quadratic Exact Medoid Algorithm

James Newling, François Fleuret

Abstract

Finding the medoid of a dataset—the point that minimizes the average distance to all others—is a fundamental task in data analysis, traditionally requiring $O(N^2)$ computations. We present trimed, a new exact algorithm that leverages the triangle inequality to achieve sub-quadratic expected run time, typically $O(N^{3/2})$. By aggressively pruning the search space, trimed outperforms state-of-the-art approximate methods in both speed and accuracy, particularly on spatial and low-to-medium dimensional data.

The Challenge of Centrality

In many applications, from $K$-medoids clustering to facility location, we need a robust measure of a dataset's center. While the "mean" is common, it often results in a synthetic point that doesn't exist in the original data. The medoid, however, is an actual member of the dataset. The bottleneck has always been computational: calculating the total distance (or "energy") for every point to find the minimum requires $N^2$ distance evaluations, which is prohibitive for large datasets.

The Trimed Algorithm

The core innovation of trimed is its use of the triangle inequality to avoid unnecessary calculations. The algorithm maintains a lower bound $l(i)$ on the energy of each point. As it iterates through points, it checks if a point's lower bound already exceeds the best energy found so far. If so, that point is pruned.

Geometric intuition of the triangle inequality bounds used in trimed to relate the energies of different points.

When the full energy $E(i)$ is computed for a point $x(i)$, it provides information about all other points $x(j)$. Specifically, the triangle inequality implies $|E(i) - \text{dist}(x(i), x(j))| \leq E(j)$. This allows the algorithm to sharpen the lower bounds for all remaining candidates simultaneously, leading to a rapid reduction in the search space.

Theoretical and Empirical Performance

The authors demonstrate that for "well-behaved" distributions, the number of points for which full energy must be computed scales as $O(N^{1/2})$. Since each such computation takes $O(N)$ time, the total complexity is $O(N^{3/2})$.

Scaling of trimed performance. Left: Number of computed elements vs. dataset size $N$ for various dimensions. Right: Comparison with the TOPRANK approximate algorithm and theoretical scaling laws.

As shown in the results, trimed scales significantly better than the brute-force $O(N^2)$ approach. Notably, it is often faster than TOPRANK, the previous state-of-the-art approximate algorithm. This is because the deterministic bounds from the triangle inequality are tighter in practice than the probabilistic estimates used by approximate methods.

Limitations and High Dimensions

The algorithm's efficiency depends on the "strength" of the triangle inequality. In very high-dimensional spaces (e.g., MNIST) or dense "small-world" networks, points tend to become equidistant. This weakens the lower bounds, causing the pruning rate to drop and the algorithm to approach $O(N^2)$ performance. Despite this "curse of dimensionality," trimed remains a powerful tool for spatial data and many real-world clustering tasks, where it provides orders-of-magnitude speedups.

Conclusion

By breaking the $O(N^2)$ barrier for exact medoid computation, trimed makes robust centrality measures accessible for large-scale data science. Its integration into $K$-medoids clustering (trikmeds) offers a faster, more interpretable alternative to $K$-means for a wide variety of datasets.

Summary updated

Abstract

We present a new algorithm, ‘trimed’ for obtaining the medoid of a set, that is the element of the set which minimises the mean distance to all other elements. The algorithm is shown to have, under...
BibTeX
@inproceedings{newling2017sub,
  author = {James Newling and François Fleuret},
  title = {{A Sub-Quadratic Exact Medoid Algorithm}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=BvF5vxZhtOlj},
}
Figure