# Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences

arXiv: https://arxiv.org/abs/2411.13922 · HTML: https://mlsanity.com/paper/2411.13922/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 21 Nov 2024.

## Builds on (most cited first, 8 of 8)

- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Data Stream Clustering: A Review](https://mlsanity.com/paper/2007.10781/) (2020)
- [Almost Cost-Free Communication in Federated Best Arm Identification](https://mlsanity.com/paper/2208.09215/) (2022)
- [MaxGap Bandit: Adaptive Algorithms for Approximate Ranking](https://mlsanity.com/paper/1906.00547/) (2019)
- [Sequential Controlled Sensing for Composite Multihypothesis Testing](https://mlsanity.com/paper/1910.12697/) (2019)
- [K-medoids Clustering of Data Sequences with Composite Distributions](https://mlsanity.com/paper/1807.11620/) (2018)
- [Hierarchical Clustering Given Confidence Intervals of Metric Distances](https://mlsanity.com/paper/1610.04274/) (2016)
- [Linear-Complexity Exponentially-Consistent Tests for Universal Outlying Sequence Detection](https://mlsanity.com/paper/1701.06084/) (2017)

## Built on by (most cited first, 2 of 2)

- [Online Clustering of Data Sequences with Bandit Information](https://mlsanity.com/paper/2501.11421/) (2025)
- [Efficient Clustering in Stochastic Bandits](https://mlsanity.com/paper/2601.09162/) (2026)

## Abstract (arXiv)

In this paper, we consider nonparametric clustering of M independent and identically distributed (i.i.d.) data sequences generated from em unknown distributions. The distributions of the M data sequences belong to K underlying distribution clusters. Existing results on exponentially consistent nonparametric clustering algorithms, like single linkage-based (SLINK) clustering and k-medoids distribution clustering, assume that the maximum intra-cluster distance (dL) is smaller than the minimum inter-cluster distance (dH). First, in the fixed sample size (FSS) setting, we show that exponential consistency can be achieved for SLINK clustering under a less strict assumption, dI < dH, where dI is the maximum distance between any two sub-clusters of a cluster that partition the cluster. Note that dI < dL in general. Thus, our results show that SLINK is exponentially consistent for a larger class of problems than previously known. In our simulations, we also identify examples where k-medoids clustering is unable to find the true clusters, but SLINK is exponentially consistent. Then, we propose a sequential clustering algorithm, named SLINK-SEQ, based on SLINK and prove that it is also exponentially consistent. Simulation results show that the SLINK-SEQ algorithm requires fewer expected number of samples than the FSS SLINK algorithm for the same probability of error.