Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs

Details Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs

1999-12-22

arxiv.org/abs/cs/9912014v1

J. Experimental Algorithmics 5(1):1-23, 2000

Computer Science

Data Structures and Algorithms

20 pages, 9 figures. A preliminary version of this paper appeared at the 9th ACM-SIAM Symp. on Discrete Algorithms, San Franci

Scientific paper

10.1145/351827.351829

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 log^2 n) 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, Groebner bases, and local improvement algorithms for partition and placement problems. Experiments show our new methods to be faster in practice than previously used heuristics.

Affiliated with

Also associated with

No associations

Rating

Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-518814