Du är här

Optimal algorithms for complete linkage clustering in d dimensions

Författare:
Publiceringsår: 2002
Språk: Engelska
Sidor: 139-149
Publikation/Tidskrift/Serie: Theoretical Computer Science
Volym: 286
Nummer: 1
Dokumenttyp: Konferensbidrag
Förlag: ELSEVIER SCIENCE BV

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • multidimensional
  • optimal algorithms
  • complete linkage clustering
  • approximation algorithms
  • hierarchical clustering

Övriga

Published
Yes
  • ISSN: 0304-3975

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

 

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen