Hierarchical clustering in general metric spaces using approximate nearest neighbors

13/04/2021

Hierarchical clustering in general metric spaces using approximate nearest neighbors

Benjamin Moseley, Sergei Vassilvtiskii, Yuyan Wang

Keywords:

Abstract Paper Similar Papers

Abstract: Hierarchical clustering is a widely used data analysis method, but suffers from scalability issues, requiring quadratic time in general metric spaces. In this work, we demonstrate how approximate nearest neighbor (ANN) queries can be used to improve the running time of the popular single-linkage and average-linkage methods. Our proposed algorithms are the first subquadratic time algorithms for non-Euclidean metrics. We complement our theoretical analysis with an empirical evaluation showcasing our methods’ efficiency and accuracy.

0

0

0

0

Share

This is an embedded video. Talk and the respective paper are published at AISTATS 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet

Similar Papers

18/07/2021

Hierarchical Clustering of Data Streams: Scalable Algorithms and Approximation Guarantees

Anand Rajagopalan, Fabio Vitale, Danny Vainstein and
Gui Citovsky, Cecilia Procopiuc, Claudio Gentile

Keywords Paper

Algorithms, Clustering, Theory, Spaces of Functions and Kernels, Algorithms, Density Estimation; Deep Learning, Adversarial Networks; Deep Learning, Generative Models; Theory, Frequent

0

0

0

0

5:09

14/09/2020

An efficient K-means clustering algorithm for tall data

Marco Capó, Aritz Pérez, Jose A. Lozan

Keywords Paper

0

0

0

0

14:46

02/02/2021

Fast Multi-view Discrete Clustering with Anchor Graphs

Qianyao Qiang, Bin Zhang, Fei Wang, Feiping Nie

Keywords Paper

0

0

0

0

14:21

12/07/2020

A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

Anastasiia Koloskova, Nicolas Loizou, Sadra Boreiri and
Martin Jaggi, Sebastian Stich

Keywords Paper

Optimization - Large Scale, Parallel and Distributed

0

0

0

0

13:46

06/12/2021

Dynamic Trace Estimation

Prathamesh Dharangutte, Christopher Musco

Keywords Paper

theory, deep learning, optimization, machine learning, graph learning

0

0

0

0

14:13

03/05/2021

Fast Geometric Projections for Local Robustness Certification

Aymeric Fromherz, Klas Leino, Matt Fredrikson and
Bryan Parno, Corina Pasareanu

Keywords Paper

verification, robustness, safety

0

1

0

0

11:54

26/04/2020

An Inductive Bias for Distances: Neural Nets that Respect the Triangle Inequality

Silviu Pitis, Harris Chan, Kiarash Jamali, Jimmy Ba

Keywords Paper

metric learning, deep metric learning, neural network architectures, triangle inequality, graph distances

0

0

0

0

5:17

12/07/2020

Regularized Optimal Transport is Ground Cost Adversarial

François-Pierre Paty, Marco Cuturi

Keywords Paper

General Machine Learning Techniques

1

0

1

1

13:26

13/04/2021

Federated learning with compression: Unified analysis and sharp guarantees

Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, Mehrdad Mahdavi

Keywords Paper

0

0

0

0

3:03

12/07/2020

Nearly Linear Row Sampling Algorithm for Quantile Regression

Yi Li, Ruosong Wang, Lin Yang, Hanrui Zhang

Keywords Paper

Optimization - Large Scale, Parallel and Distributed

0

0

0

0

15:01

06/12/2020

BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits

Mo Tiwari, Martin Zhang, James J Mayclin and
Sebastian Thrun, Chris Piech, Ilan Shomorony

Keywords Paper

0

0

0

0

3:16

02/02/2021

Automated Clustering of High-dimensional Data with a Feature Weighted Mean Shift Algorithm

Saptarshi Chakraborty, Debolina Paul, Swagatam Das

Keywords Paper

0

0

0

0

20:09

18/07/2021

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

Shyam Narayanan, Sandeep Silwal, Piotr Indyk, Or Zamir

Keywords Paper

Algorithms, Dimensionality Reduction

0

0

0

0

5:00

02/02/2021

Metrics and Continuity in Reinforcement Learning

Charline Le Lan, Marc G. Bellemare, Pablo Samuel Castro

Keywords Paper

0

0

0

0

20:24

03/05/2021

New Bounds For Distributed Mean Estimation and Variance Reduction

Peter Davies, Vijaykrishna Gurunathan, Niusha Moshrefi and
Saleh Ashkboos, Dan Alistarh

Keywords Paper

distributed machine learning, variance reduction, mean estimation, lattices

0

0

0

0

4:51

14/09/2020

Online Binary Incomplete Multi-view Clustering

Longqi Yang, Liangliang Zhang, Yuhua Tang

Keywords Paper

0

0

0

0

3:04

26/08/2020

Neighborhood Growth Determines Geometric Priors for Relational Representation Learning

Melanie Weber

Keywords Paper

0

0

0

0

16:21

06/12/2020

Collegial Ensembles

Etai Littwin, Ben Myara, Sima Sabah and
Joshua Susskind, Shuangfei Zhai, Oren Golan

Keywords Paper

0

0

0

0

3:17

13/04/2021

Cluster trellis: Data structures & algorithms for exact inference in hierarchical clustering

Sebastian Macaluso, Craig Greenberg, Nicholas Monath and
Ji Ah Lee, Patrick Flaherty, Kyle Cranmer, Andrew McGregor, Andrew McCallum

Keywords Paper

0

0

0

0

3:02

02/02/2021

Almost Linear Time Density Level Set Estimation via DBSCAN

Hossein Esfandiari, Vahab Mirrokni, Peilin Zhong

Keywords Paper

0

0

0

0

19:50

12/07/2020

Coresets for Clustering in Graphs of Bounded Treewidth

Daniel Baker, Vladimir Braverman, Lingxiao Huang and
Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu

Keywords Paper

Unsupervised and Semi-Supervised Learning

0

0

0

0

14:49

30/11/2020

Progressive Batching for Efficient Non-linear Least Squares

Huu Le, Christopher Zach, Edward Rosten, Oliver J. Woodford

Keywords Paper

0

0

0

0

8:23

06/12/2021

Local Hyper-Flow Diffusion

Kimon Fountoulakis, Pan Li, Shenghao Yang

Keywords Paper

optimization, graph learning, clustering

0

0

0

0

14:24

18/07/2021

Low-Rank Sinkhorn Factorization

Meyer Scetbon, Marco Cuturi, Gabriel Peyré

Keywords Paper

Algorithms, Optimal Transport

0

1

1

1

5:22

06/12/2020

Ratio Trace Formulation of Wasserstein Discriminant Analysis

Hexuan Liu, Yunfeng Cai, You-Lin Chen, Ping Li

Keywords Paper

0

0

0

0

3:18

06/12/2021

Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs

Bogdan-Adrian Manghiuc, He Sun

Keywords Paper

graph learning, clustering

0

0

0

0

14:05

02/02/2021

Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints

Brian Brubach, Darshan Chakrabarti, John P. Dickerson and
Aravind Srinivasan, Leonidas Tsepenekas

Keywords Paper

0

0

0

0

17:56

18/07/2021

SigGPDE: Scaling Sparse Gaussian Processes on Sequential Data

Maud Lemercier, Cristopher Salvi, Thomas Cass and
Edwin V Bonilla, Theo Damoulas, Terry Lyons

Keywords Paper

Probabilistic Methods, Gaussian Processes and Bayesian non-parametrics

0

0

0

0

4:42

18/07/2021

Solving high-dimensional parabolic PDEs using the tensor train format

Lorenz Richter, Leon Sallandt, Nikolas Nüsken

Keywords Paper

Probabilistic Methods, Monte Carlo Methods

0

0

0

0

16:30

18/07/2021

Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time

Laxman Dhulipala, David Eisenstat, Jakub Łącki and
Vahab Mirrokni, Jessica Shi

Keywords Paper

Algorithms, Clustering

0

0

0

0

5:25

18/07/2021

Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More

Johannes Klicpera, Marten Lienen, Stephan Günnemann

Keywords Paper

Algorithms, Optimal Transport

0

0

0

1

5:21

06/12/2021

Parallel and Efficient Hierarchical k-Median Clustering

Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard and
Christian Sohler, Ola Svensson

Keywords Paper

self-supervised learning, clustering

0

0

0

0

14:39

18/07/2021

Optimal Complexity in Decentralized Training

Yucheng Lu, Christopher De Sa

Keywords Paper

Optimization, Distributed and Parallel Optimization

0

0

0

1

19:59

05/01/2021

Fast Pose Graph Optimization via Krylov-Schur and Cholesky Factorization

Gabriel Moreira, Manuel Marques, Joao Paulo Costeira

Keywords Paper

0

0

0

0

5:01

14/06/2020

Spatial Pyramid Based Graph Reasoning for Semantic Segmentation

Xia Li, Yibo Yang, Qijie Zhao and
Tiancheng Shen, Zhouchen Lin, Hong Liu

Keywords Paper

semantic segmentation, graph convolution, spatial pyramid, scene parsing

0

0

0

0

1:01

12/07/2020

Fast Differentiable Sorting and Ranking

Mathieu Blondel, Olivier Teboul, Quentin Berthet, Josip Djolonga

Keywords Paper

Sequential, Network, and Time-Series Modeling

0

0

0

0

14:26

18/07/2021

A Novel Sequential Coreset Method for Gradient Descent Algorithms

Jiawei Huang, Ruomin Huang, wenjie liu and
Nikolaos Freris, Hu Ding

Keywords Paper

Optimization

0

0

0

0

5:15

18/07/2021

In-Database Regression in Input Sparsity Time

Rajesh Jayaram, Alireza Samadian, David Woodruff, Peng Ye

Keywords Paper

Algorithms, Dimensionality Reduction

0

0

0

0

5:08

06/12/2021

Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems

Zixiu Wang, Yiwen Guo, Hu Ding

Keywords Paper

optimization, machine learning, adversarial robustness and security, clustering

0

0

0

0

8:38

06/12/2020

Learning outside the Black-Box: The pursuit of interpretable models

Jonathan Crabbe, Yao Zhang, William Zame, Mihaela van der Schaar

Keywords Paper

0

0

0

0

3:16