2021/04/14 by Craig S. Greenberg, Greenberg, Craig S., Sebastian Macaluso +15
Computer Science · #Advanced Clustering Algorithms Research #Algorithms and Data Compression #Data Analysis #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics and Probability (physics.data-an)
paper · pdf · doi:10.48550/arxiv.2104.07061
openalex publication_date 2021/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hierarchical clustering is a critical task in numerous domains. Many approaches are based on heuristics and the properties of the resulting clusterings are studied post hoc. However, in several applications, there is a natural cost function that can be used to characterize the quality of the clustering. In those cases, hierarchical clustering can be seen as a combinatorial optimization problem. To that end, we introduce a new approach based on A* search. We overcome the prohibitively large search space by combining A* with a novel trellis data structure. This combination results in an exact algorithm that scales beyond previous state of the art, from a search space with 1012 trees to 1015 trees, and an approximate algorithm that improves over baselines, even in enormous search spaces that contain more than 101000 trees. We empirically demonstrate that our method achieves substantially higher quality results than baselines for a particle physics use case and other clustering benchmarks. We describe how our method provides significantly improved theoretical bounds on the time and space complexity of A* for clustering.