 | The ACM Journal of Experimental Algorithmics |
Volume 5, Article 1, 2000
Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs
by
http://www.jea.acm.org/2000/EppsteinDynamic/
Abstract:
We develop data structures for dynamic closest pair problems with
arbitrary distance functions, that do not necessarily come from any
geometric structure on the objects. Based on a technique previously
used by the author for Euclidean closest pairs, we show how to insert
and delete objects from an n-object set, maintaining the closest pair,
in O(n log2n) time per update and
O(n) space. With quadratic space,
we can instead use a quadtree-like structure to achieve an optimal
time bound, O(n) per update. We apply these data structures
to hierarchical clustering, greedy matching, and TSP heuristics,
and discuss other potential applications in machine learning,
Gröbner bases, and local improvement algorithms for partition
and placement problems. Experiments show our new methods to be
faster in practice than previously used heuristics.
- Keywords:
TSP, matching, conga line data structure, quadtree, nearest-neighbor heuristic,
agglomerative clustering, hierarchical clustering, Gröbner bases
- CR Categories:
F.2.2} Analysis of Algorithms (Nonnumeric Algorithms)
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the article;
this is a small Unix tar file, which includes the source code, a Makefile,
and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
December 21, 1999
|
May 25, 2000
|
May 30, 2000
|
June 1, 2000
|
Last updated and validated June 1, 2000, by editor@jea.acm.org