Optimal algorithms for complete linkage clustering in d dimensions
Author
Summary, in English
It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. Furthermore, for every other fixed L-t-metric, it is shown that it can be approximated within an arbitrarily small constant factor in O(nlogn) time and linear space.
Department/s
- Computer Science
Publishing year
2002
Language
English
Pages
139-149
Publication/Series
Theoretical Computer Science
Volume
286
Issue
1
Document type
Conference paper
Publisher
Elsevier
Topic
- Computer Science
Keywords
- multidimensional
- optimal algorithms
- complete linkage clustering
- approximation algorithms
- hierarchical clustering
Status
Published
ISBN/ISSN/Other
- ISSN: 0304-3975