{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,5]],"date-time":"2026-07-05T12:53:58Z","timestamp":1783256038152,"version":"3.54.6"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T00:00:00Z","timestamp":1559692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1461559, CCF-093970, CCF-18107"],"award-info":[{"award-number":["CCF-1461559, CCF-093970, CCF-18107"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N510129\/1"],"award-info":[{"award-number":["EP\/N510129\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"<jats:p>Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Motivated by the fact that most work on hierarchical clustering was based on providing algorithms, rather than optimizing a specific objective, Dasgupta framed similarity-based hierarchical clustering as a combinatorial optimization problem, where a \u201cgood\u201d hierarchical clustering is one that minimizes a particular cost function [23]. He showed that this cost function has certain desirable properties: To achieve optimal cost, disconnected components (namely, dissimilar elements) must be separated at higher levels of the hierarchy, and when the similarity between data elements is identical, all clusterings achieve the same cost.<\/jats:p>\n          <jats:p>\n            We take an axiomatic approach to defining \u201cgood\u201d objective functions for both similarity- and dissimilarity-based hierarchical clustering. We characterize a set of\n            <jats:italic>admissible<\/jats:italic>\n            objective functions having the property that when the input admits a \u201cnatural\u201d ground-truth hierarchical clustering, the ground-truth clustering has an optimal value. We show that this set includes the objective function introduced by Dasgupta.\n          <\/jats:p>\n          <jats:p>Equipped with a suitable objective function, we analyze the performance of practical algorithms, as well as develop better and faster algorithms for hierarchical clustering. We also initiate a beyond worst-case analysis of the complexity of the problem and design algorithms for this scenario.<\/jats:p>","DOI":"10.1145\/3321386","type":"journal-article","created":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T12:28:42Z","timestamp":1559824122000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":164,"title":["Hierarchical Clustering"],"prefix":"10.1145","volume":"66","author":[{"given":"Vincent","family":"Cohen-addad","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, UPMC Univ Paris 06, CNRS, LIP6, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Varun","family":"Kanade","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frederik","family":"Mallmann-trenn","sequence":"additional","affiliation":[{"name":"Massachusetts Institute for Technology, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Diderot 07, CNRS, IRIF, Paris, France;"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380808"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.36"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Pranjal Awasthi and Or Sheffet. 2012. Improved spectral-norm bounds for clustering. In Proceedings of the 15th International Workshop on Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques (APPROX\u201912) and Proceedings of the 16th International Workshop (RANDOM\u201912). 37--49.  Pranjal Awasthi and Or Sheffet. 2012. Improved spectral-norm bounds for clustering. In Proceedings of the 15th International Workshop on Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques (APPROX\u201912) and Proceedings of the 16th International Workshop (RANDOM\u201912). 37--49.","DOI":"10.1007\/978-3-642-32512-0_4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496886"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450144"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/140981575"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1813231.1813269"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374474"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","author":"Bilu Yonatan","unstructured":"Yonatan Bilu , Amit Daniely , Nati Linial , and Michael E. Saks . 2013. On the practically interesting instances of MAXCUT . In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913) . 526--537. Yonatan Bilu, Amit Daniely, Nati Linial, and Michael E. Saks. 2013. On the practically interesting instances of MAXCUT. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913). 526--537."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000193"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.22"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.48"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859898"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2004.831124"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039739"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310574"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML\u201918)","author":"Chatziafratis Vaggos","year":"2018","unstructured":"Vaggos Chatziafratis , Rad Niazadeh , and Moses Charikar . 2018 . Hierarchical clustering with structural constraints . In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918) . 773--782. Vaggos Chatziafratis, Rad Niazadeh, and Moses Charikar. 2018. Hierarchical clustering with structural constraints. In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918). 773--782."},{"key":"e_1_2_1_20_1","unstructured":"Vincent Cohen-Addad Varun Kanade and Frederik Mallmann-Trenn. 2017. Hierarchical clustering beyond the worst-case. In Advances in Neural Information Processing Systems.   Vincent Cohen-Addad Varun Kanade and Frederik Mallmann-Trenn. 2017. Hierarchical clustering beyond the worst-case. In Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175293"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796496"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897527"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.006"},{"key":"e_1_2_1_25_1","first-page":"203","article-title":"A probabilistic analysis of EM for mixtures of separated, spherical gaussians","volume":"8","author":"Dasgupta Sanjoy","year":"2007","unstructured":"Sanjoy Dasgupta and Leonard J. Schulman . 2007 . A probabilistic analysis of EM for mixtures of separated, spherical gaussians . J. Mach. Learn. Res. 8 (2007), 203 -- 226 . Sanjoy Dasgupta and Leonard J. Schulman. 2007. A probabilistic analysis of EM for mixtures of separated, spherical gaussians. J. Mach. Learn. Res. 8 (2007), 203--226.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Annual Conference on Advances in Neural Information Processing Systems. 2307--2315","author":"Eldridge Justin","year":"2016","unstructured":"Justin Eldridge , Mikhail Belkin , and Yusu Wang . 2016 . Graphons, mergeons, and so on&excl; . In Proceedings of the Annual Conference on Advances in Neural Information Processing Systems. 2307--2315 . Justin Eldridge, Mikhail Belkin, and Yusu Wang. 2016. Graphons, mergeons, and so on&excl;. In Proceedings of the Annual Conference on Advances in Neural Information Processing Systems. 2307--2315."},{"key":"e_1_2_1_27_1","unstructured":"Joseph Felsenstein and Joseph Felenstein. 2004. Inferring Phylogenies. Vol. 2. Sinauer Associates Sunderland.  Joseph Felsenstein and Joseph Felenstein. 2004. Inferring Phylogenies. Vol. 2. Sinauer Associates Sunderland."},{"key":"e_1_2_1_28_1","volume-title":"The Elements of Statistical Learning","author":"Friedman Jerome","unstructured":"Jerome Friedman , Trevor Hastie , and Robert Tibshirani . 2001. The Elements of Statistical Learning . Vol. 1 . Springer Series in Statistics, Berlin. Jerome Friedman, Trevor Hastie, and Robert Tibshirani. 2001. The Elements of Statistical Learning. Vol. 1. Springer Series in Statistics, Berlin."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_30_1","unstructured":"N. Jardine and R. Sibson. 1972. Mathematical Taxonomy. John Wiley 8 Sons.  N. Jardine and R. Sibson. 1972. Mathematical Taxonomy. John Wiley 8 Sons."},{"key":"e_1_2_1_31_1","first-page":"463","article-title":"An impossibility theorem for clustering","volume":"15","author":"Kleinberg Jon","year":"2002","unstructured":"Jon Kleinberg . 2002 . An impossibility theorem for clustering . In Advances in Neural Information Processing Systems , Vol. 15. 463 -- 470 . Jon Kleinberg. 2002. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems, Vol. 15. 463--470.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3042573.3042611"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_2_1_34_1","volume-title":"Williamson","author":"Lin Guolong","year":"2006","unstructured":"Guolong Lin , Chandrashekhar Nagarajan , Rajmohan Rajaraman , and David P . Williamson . 2006 . A general approach for incremental approximation and hierarchical clustering. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. Society for Industrial and Applied Mathematics, 1147--1156. Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David P. Williamson. 2006. A general approach for incremental approximation and hierarchical clustering. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm. Society for Industrial and Applied Mathematics, 1147--1156."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2016.2634322"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214013"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875554"},{"key":"e_1_2_1_38_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Moseley Benjamin","year":"2017","unstructured":"Benjamin Moseley and Joshua Wang . 2017 . Approximation bounds for hierarchical clustering: Average linkage, bisecting K-means, and local search . In Advances in Neural Information Processing Systems , Vol. 30 I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). 3097--3106. Benjamin Moseley and Joshua Wang. 2017. Approximation bounds for hierarchical clustering: Average linkage, bisecting K-means, and local search. In Advances in Neural Information Processing Systems, Vol. 30 I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). 3097--3106."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395117"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780549"},{"key":"e_1_2_1_41_1","unstructured":"Aurko Roy and Sebastian Pokutta. 2016. Hierarchical clustering via spreading metrics. In Advances in Neural Information Processing Systems. 2316--2324.   Aurko Roy and Sebastian Pokutta. 2016. Hierarchical clustering via spreading metrics. In Advances in Neural Information Processing Systems. 2316--2324."},{"key":"e_1_2_1_42_1","volume-title":"Sokal","author":"Sneath Peter H. A.","year":"1962","unstructured":"Peter H. A. Sneath and Robert R . Sokal . 1962 . Numerical taxonomy. Nature 193, 4818 (1962), 855--860. Peter H. A. Sneath and Robert R. Sokal. 1962. Numerical taxonomy. Nature 193, 4818 (1962), 855--860."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the ACM Knowledge Discovery and Data Mining Workshop on Text Mining (KDD\u201900)","author":"Steinbach Michael","year":"2000","unstructured":"Michael Steinbach , George Karypis , and Vipin Kumar . 2000 . A comparison of document clustering techniques . In Proceedings of the ACM Knowledge Discovery and Data Mining Workshop on Text Mining (KDD\u201900) . Michael Steinbach, George Karypis, and Vipin Kumar. 2000. A comparison of document clustering techniques. In Proceedings of the ACM Knowledge Discovery and Data Mining Workshop on Text Mining (KDD\u201900)."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. 639--646","author":"Zadeh Reza Bosagh","year":"2009","unstructured":"Reza Bosagh Zadeh and Shai Ben-David . 2009 . A uniqueness theorem for clustering . In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. 639--646 . Reza Bosagh Zadeh and Shai Ben-David. 2009. A uniqueness theorem for clustering. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. 639--646."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3321386","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3321386","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3321386","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:09Z","timestamp":1750204389000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3321386"}},"subtitle":["Objective Functions and Algorithms"],"short-title":[],"issued":{"date-parts":[[2019,6,5]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3321386"],"URL":"https:\/\/doi.org\/10.1145\/3321386","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,5]]},"assertion":[{"value":"2017-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}