Advanced

Optimal algorithms for complete linkage clustering in d dimensions

Krznaric, Drago and Levcopoulos, Christos LU (2002) In Theoretical Computer Science 286(1). p.139-149
Abstract
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
multidimensional, optimal algorithms, complete linkage clustering, approximation algorithms, hierarchical clustering
in
Theoretical Computer Science
volume
286
issue
1
pages
139 - 149
publisher
Elsevier
external identifiers
  • wos:000178256800007
  • scopus:0037031797
ISSN
0304-3975
DOI
10.1016/S0304-3975(01)00239-0
language
English
LU publication?
yes
id
47372190-3528-4826-8ed6-19bbd305920c (old id 327803)
date added to LUP
2007-11-28 09:03:35
date last changed
2017-03-05 04:07:41
@inproceedings{47372190-3528-4826-8ed6-19bbd305920c,
  abstract     = {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.},
  author       = {Krznaric, Drago and Levcopoulos, Christos},
  booktitle    = {Theoretical Computer Science},
  issn         = {0304-3975},
  keyword      = {multidimensional,optimal algorithms,complete linkage clustering,approximation algorithms,hierarchical clustering},
  language     = {eng},
  number       = {1},
  pages        = {139--149},
  publisher    = {Elsevier},
  title        = {Optimal algorithms for complete linkage clustering in d dimensions},
  url          = {http://dx.doi.org/10.1016/S0304-3975(01)00239-0},
  volume       = {286},
  year         = {2002},
}