Article

Free access

Fast hierarchical clustering and other applications of dynamic closest pairs

Author:

David EppsteinAuthors Info & Claims

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

Pages 619 - 628

Published: 01 January 1998 Publication History

PDF eReader

References

[1]

W.W. Adams and E Loustaunau. An Introduction to Gr6bner Bases. Graduate Studes in Mathematics 3. AMS, 1994.

Google Scholar

[2]

R. Agarwala, V. Bafna, M. Farach, B. Narayanan, M. S. Paterson, and M. Thorup. On the approximability of numerical taxonomy. Proc. 7th Syrup. Discrete Algorithms, pp. 365-372. ACM and SIAM, January 1996.

Digital Library

Google Scholar

[3]

O. Aichholzer. Combinatorial & Computational Properties of the Hypercube- New Results on Covering, Slicing, Clustering and Searching on the Hypercube. Ph.D. thesis, Tech. Univ. Graz., April 1997.

Google Scholar

[4]

M. R. Anderberg. Cluster Analysis for Applications. Probability and Mathematical Statistics 19. Academic Press, New York, 1973.

Google Scholar

[5]

G. H. Ball and D. J. Hall. ISODATA, a novel method of data analysis and pattern classification. Tech. rep., Stanford Research Inst., 1965.

Google Scholar

[6]

J. L. Bentley. Experiments on traveling salesman heuristics. Proc. 1st Symp. Discrete Algorithms, pp. 91-99. ACM and SIAM, January 1990.

Digital Library

Google Scholar

[7]

B. Buchberger. Applications of Gr/Sbner bases in non-linear computational geometry. Proc. Int. Symp. Trends in Computer Algebra, pp. 52--66. Springer-Verlag, Lecture Notes in Computer Science 296, May 1987.

Digital Library

Google Scholar

[8]

X. Cheng and J. M. Wallace. Cluster analysis of the northern hemisphere wintertime 500-hPa height field: spatial patterns. J. Atmospheric Sciences 50(i 6):2674--2696, August 1993.

Google Scholar

[9]

M. Clegg, J. Edmonds, and R. impagliazzo. Using the Groebner basis algorithm to find proofs of unsatisfiability. Proc. 28th Symp. Theory of Computing, pp. 174-183. ACM, May 1996.

Digital Library

Google Scholar

[10]

F. Corpet. Multiple sequence alignment with hierarchical clustering. Nucleic Acids Research 16(22):10881-10890, 1988.

Google Scholar

[11]

S. Czapor.A heuristic selection strategy for lexicographic Gr0bner bases? Proc. Int. Syrup. Symbolic & Algebraic Computation, pp. 39-48. ACM, July 1991.

Digital Library

Google Scholar

[12]

D. Dobkin and S. Suri. Maintenance of geometric extrema. J. ACM 38:275-298, 1991.

Digital Library

Google Scholar

[13]

B. S. Duran and P. L. Odell. Cluster Analysis: A Survey. Lecture Notes in Economics and Mathematical Systems 100. Springer-Vedag, Berlin, 1974.

Google Scholar

[14]

D. Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete & Computational Geometry 13(1):111-122, January 1995.

Google Scholar

[15]

D. Eppstein and J. Erickson. Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions. Manuscript, 1997.

Google Scholar

[16]

J. Felsenstein. PHYLIP (Phylogeny Inference Package) version 3.572c. Distributed by the author, July 1995.

Google Scholar

[17]

A. Frieze, C. McDiarmid, and B. Reed. Greedy matching on the line. SIAM J. Computing 19(4):666-672, August 1990.

Digital Library

Google Scholar

[18]

A. Giovini, T. Mora, G. Niesi, L. Robbiano, and C. Traverso. 'One sugar cube, please' or selection strategies in the Buchberger algorithm. Proc. int. Symp. Symbolic & Algebraic Computation, pp. 49-54. ACM, July 1991.

Digital Library

Google Scholar

[19]

M. Golin, R. Raman, C. Schwarz, and M. Smid. Randomized data structures for the dynamic closest-pair problem. Proc. 4th Symp. Discrete Algorithms, pp. 301-310. ACM and SIAM, 1993.

Digital Library

Google Scholar

[20]

O. Gotoh. Further improvements in methods of group-togroup sequence alignment with generalized profile operations. CABIOS 10(4):379-387, 1994.

Google Scholar

[21]

J. A. Hartigan. Clustering Algorithms. John Wiley & Sons, New York, 1975.

Digital Library

Google Scholar

[22]

D. Krznaric and C. Levcopoulos. The first subquadratic algorithm for complete linkage clustering. Proc. 6th Int. Conf. Algorithms & Computation, pp. 392-401. Springer-Verlag, Lecture Notes in Computer Science 1004, December 1995.

Digital Library

Google Scholar

[23]

Y. Matias. Semi-dynamic closest-pair algorithms. Proc. 5th Canad. Conf. Computational Geometry, pp. 264-271, August 1993.

Google Scholar

[24]

M. J. Pazzani. Constructive induction of Cartesian product attributes. Manuscript, 1997.

Google Scholar

[25]

E. M. Reingold and R. E. Tarjan. On a greedy heuristic for complete matching. SIAM J. Computing 10(4):676-681, November 1981.

Google Scholar

[26]

D.H. Rosenkrantz, R. E. Steams, and P. M. Lewis, II. An analysis of several heuristics for the traveling salesman problem. SlAM J. Computing 6(3):563-581, September 1977.

Google Scholar

[27]

C. Schwarz, M. Smid, and J. Snoeyink. An optimal algorithm for the on-line closest pair problem. Proc. 8th Symp. Computational Geometry, pp. 330--336. ACM, 1992.

Digital Library

Google Scholar

[28]

M. Smid. Maintaining the minimal distance of a point set in polylogarithmic time. Discrete & Computational Geometry 7(415-431), 1992.

Google Scholar

[29]

B. Sturmfels. GriJbner Bases and Convex Polytopes. University Lecture Ser. 8. AMS, 1996.

Google Scholar

[30]

K. J. Supowit. New techniques for some dynamic closestpoint and farthest-point problems. Proc. 1st Syrup. Discrete Algorithms, pp. 84-90. ACM and SIAM, 1990.

Digital Library

Google Scholar

[31]

J. D. Thompson, D. G. Higgins, and T. J. Gibson. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice. Nucleic Acids Research 22:4673-4680, 1994.

Google Scholar

[32]

P. N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. Proc. 4th Symp. Discrete Algorithms, pp. 31 f-321. ACM and SIAM, January 1993.

Digital Library

Google Scholar

[33]

J. Zupan. Clustering of Large Data Sets. Chemometrics Research Studies Ser. Research Studies Press, Chichester, 1982.

Google Scholar

Cited By

View all

Kriegel HSchubert EZimek A(2017)The (black) art of runtime evaluationKnowledge and Information Systems10.1007/s10115-016-1004-252:2(341-378)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s10115-016-1004-2
Nagel UThiel KKötter TPiątek DBerthold M(2012)Towards discovery of subgraph bisociationsBisociative Knowledge Discovery10.5555/2363300.2363321(263-284)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2363300.2363321
Jang JBrumley DVenkataraman SChen YDanezis GShmatikov V(2011)BitShredProceedings of the 18th ACM conference on Computer and communications security10.1145/2046707.2046742(309-320)Online publication date: 17-Oct-2011
https://dl.acm.org/doi/10.1145/2046707.2046742
Show More Cited By

Index Terms

Recommendations

Fast hierarchical clustering and other applications of dynamic closest pairs

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 ...
Dynamic hierarchical algorithms for document clustering

In this paper, two clustering algorithms called dynamic hierarchical compact and dynamic hierarchical star are presented. Both methods aim to construct a cluster hierarchy, dealing with dynamic data sets. The first creates disjoint hierarchies of ...
Hierarchical Means Clustering
Abstract
In the cluster analysis literature, there are several partitioning (non-hierarchical) methods for clustering multivariate objects based on model estimation. Distinct to these methods is the use of a system of n nested statistical models and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms

January 1998

704 pages

ISBN:0898714109

Chairman:
Howard Karloff

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1998

Check for updates

Qualifiers

Article

Conference

SODA98

Sponsor:

SIGACT
SIAM

SODA98: 1998 Conference on Discrete Algorithms

January 25 - 27, 1998

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
682
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)5

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kriegel HSchubert EZimek A(2017)The (black) art of runtime evaluationKnowledge and Information Systems10.1007/s10115-016-1004-252:2(341-378)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s10115-016-1004-2
Nagel UThiel KKötter TPiątek DBerthold M(2012)Towards discovery of subgraph bisociationsBisociative Knowledge Discovery10.5555/2363300.2363321(263-284)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.5555/2363300.2363321
Jang JBrumley DVenkataraman SChen YDanezis GShmatikov V(2011)BitShredProceedings of the 18th ACM conference on Computer and communications security10.1145/2046707.2046742(309-320)Online publication date: 17-Oct-2011
https://dl.acm.org/doi/10.1145/2046707.2046742
Lee JPark C(2010)Unnecessary image pair detection for a large scale reconstructionProceedings of the 9th international conference on Entertainment computing10.5555/1881673.1881691(151-159)Online publication date: 8-Sep-2010
https://dl.acm.org/doi/10.5555/1881673.1881691
Ko ASabourin RDe Souza Britto A(2007)A new HMM-based ensemble generation method for numeral recognitionProceedings of the 7th international conference on Multiple classifier systems10.5555/1761171.1761179(52-61)Online publication date: 23-May-2007
https://dl.acm.org/doi/10.5555/1761171.1761179
Yip KCheung DNg M(2004)HARPIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2004.7416:11(1387-1397)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1109/TKDE.2004.74
Borodin AOstrovsky RRabani Y(2004)Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional SpacesMachine Language10.1023/B:MACH.0000033118.09057.8056:1-3(153-167)Online publication date: 25-Jun-2004
https://dl.acm.org/doi/10.1023/B%3AMACH.0000033118.09057.80
Dragut ANichitiu C(2004)A Monotonic On-Line Linear Algorithm for Hierarchical Agglomerative ClassificationInformation Technology and Management10.1023/B:ITEM.0000008078.09272.895:1-2(111-141)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1023/B%3AITEM.0000008078.09272.89
Nanopoulos ATheodoridis YManolopoulos Y(2001)C2PProceedings of the 27th International Conference on Very Large Data Bases10.5555/645927.672358(331-340)Online publication date: 11-Sep-2001
https://dl.acm.org/doi/10.5555/645927.672358
Langbein FMills BMarshall AMartin R(2001)Finding approximate shape regularities in reverse engineered solid models bounded by simple surfacesProceedings of the sixth ACM symposium on Solid modeling and applications10.1145/376957.376981(206-215)Online publication date: 1-May-2001
https://dl.acm.org/doi/10.1145/376957.376981
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Fast hierarchical clustering and other applications of dynamic closest pairs

Dynamic hierarchical algorithms for document clustering

Hierarchical Means Clustering