# Adaptive Hierarchical Clustering Using Ordinal Queries

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2017.

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

- [Optimal Sample Complexity of Contrastive Learning](https://mlsanity.com/paper/2312.00379/) (2023)
- [Interactive Machine Learning: A State of the Art Review](https://mlsanity.com/paper/2207.06196/) (2022)
- [How to Design Robust Algorithms using Noisy Comparison Oracle](https://mlsanity.com/paper/2105.05782/) (2021)
- [Hierarchical Clustering: New Bounds and Objective](https://mlsanity.com/paper/2111.06863/) (2021)
- [Tree Learning: Optimal Algorithms and Sample Complexity](https://mlsanity.com/paper/2302.04492/) (2023)
- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [A Revenue Function for Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/2211.16459/) (2022)
- [Metric k-clustering using only Weak Comparison Oracles](https://mlsanity.com/paper/2601.19333/) (2026)
- [Optimal VC Dimension of Contrastive Learning with Margin](https://mlsanity.com/paper/2609.38834/) (2026)

## Abstract (arXiv)

In many applications of clustering (for example, ontologies or clusterings of animal or plant species), hierarchical clusterings are more descriptive than a flat clustering. A hierarchical clustering over n elements is represented by a rooted binary tree with n leaves, each corresponding to one element. The subtrees rooted at interior nodes capture the clusters. In this paper, we study active learning of a hierarchical clustering using only ordinal queries. An ordinal query consists of a set of three elements, and the response to a query reveals the two elements (among the three elements in the query) which are "closer" to each other than to the third one. We say that elements x and x' are closer to each other than x" if there exists a cluster containing x and x', but not x". When all the query responses are correct, there is a deterministic algorithm that learns the underlying hierarchical clustering using at most n log2 n adaptive ordinal queries. We generalize this algorithm to be robust in a model in which each query response is correct independently with probability p > frac12, and adversarially incorrect with probability 1 - p. We show that in the presence of noise, our algorithm outputs the correct hierarchical clustering with probability at least 1 - δ, using O(n log n + n log(1/δ)) adaptive ordinal queries. For our results, adaptivity is crucial: we prove that even in the absence of noise, every non-adaptive algorithm requires Omega(n3) ordinal queries in the worst case.