The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms
Open accessAbstract
Clustering non-Euclidean data is difficult, and one of the most used algorithms besides hierarchical clustering is the popular algorithm Partitioning Around Medoids (PAM), also simply referred to as k-medoids. In Euclidean geometry the mean-as used in k-means-is a good estimator for the cluster center, but this does not hold for arbitrary dissimilarities. PAM uses the medoid instead, the object with the smallest dissimilarity to all others in the cluster. This notion of centrality can be used with any (dis-)similarity, and thus is of high relevance to many domains such as biology that require the use of Jaccard, Gower, or more complex distances. A key issue with PAM is its high run time cost. We propose modifications to the PAM algorithm to achieve an O(k)-fold speedup in the second SWAP phase of the algorithm, but will still find the same results as the original PAM algorithm. If we slightly relax the choice of swaps performed (at comparable quality), we can further accelerate the algorithm by performing up to k swaps in each iteration. With the substantially faster SWAP, we can now also explore alternative strategies for choosing the initial medoids. We also show how the CLARA and CLARANS algorithms benefit from these modifications. It can easily be combined with earlier approaches to use PAM and CLARA on big data (some of which use PAM as a subroutine, hence can immediately benefit from these improvements), where the performance with high k becomes increasingly important. In experiments on real data with k=100, we observed a 200-fold speedup compared to the original PAM SWAP algorithm, making PAM applicable to larger data sets as long as we can afford to compute a distance matrix, and in particular to higher k (at k=2, the new SWAP was only 1.5 times faster, as the speedup is expected to increase with k).
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Algorithm AS 136: A K-Means Clustering Algorithm
Hartigan, J. A., & Wong, M. A. (1979) · Applied Statistics · doi:10.2307/2346830 · Cited by 14,523
(2007) · doi:10.5555/1283383.1283494 · Cited by 7,364
Cited by
Unsupervised Learning Methods for Molecular Simulation Data
Glielmo, A., Husic, B. E., Rodriguez, A., Clementi, C., Noé, F., & Laio, A. (2021) · Chemical Reviews · doi:10.1021/acs.chemrev.0c01195 · Cited by 402
Genomic history and ecology of the geographic spread of rice
Gutaker, R. M., Groen, S. C., Bellis, E. S., Choi, J. Y., Pires, I. S., Bocinsky, R. K., Slayton, E. R., Wilkins, O., Castillo, C. C., Negrão, S., et al. (2020) · Nature Plants · doi:10.1038/s41477-020-0659-6 · Cited by 278
Latency Prediction for Delay-sensitive V2X Applications in Mobile Cloud/Edge Computing Systems
Zhang, W., Feng, M., Krunz, M., & Volos, H. (2020) · GLOBECOM 2020 - 2020 IEEE Global Communications Conference · doi:10.1109/globecom42002.2020.9348104 · Cited by 27
Metadata
- Authors
- Schubert, E., & Rousseeuw, P. J.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer International Publishing
- Published
- 2019
- Pages
- 171-187
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2897098291
- Cited by
- 230
- References
- 2
- FWCI
- 10.42
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms. https://app.cochat.ai/papers/10.1007/978-3-030-32047-8_16
- The paper
- Schubert, E., & Rousseeuw, P. J. (2019). Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-030-32047-8_16
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.