# Partitioned K-nearest neighbor local depth for scalable comparison-based learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Aug 2021.

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

- [Empirical complexity of comparator-based nearest neighbor descent](https://mlsanity.com/paper/2202.00517/) (2022)
- [Generalized partitioned local depth](https://mlsanity.com/paper/2303.10167/) (2023)
- [Online Partitioned Local Depth for semi-supervised applications](https://mlsanity.com/paper/2512.15436/) (2025)

## Abstract (arXiv)

A triplet comparison oracle on a set S takes an object x ∈ S and for any pair y, z subset S setminus x declares which of y and z is more similar to x. Partitioned Local Depth (PaLD) supplies a principled non-parametric partitioning of S under such triplet comparisons but needs O(n2 logn) oracle calls and O(n3) post-processing steps. We introduce Partitioned Nearest Neighbors Local Depth (PaNNLD), a computationally tractable variant of PaLD leveraging the K-nearest neighbors digraph on S. PaNNLD needs only O(n K logn) oracle calls, by replacing an oracle call by a coin flip when neither y nor z is adjacent to x in the undirected version of the K-nearest neighbors digraph. By averaging over randomizations, PaNNLD subsequently requires (at best) only O(n K2) post-processing steps. Concentration of measure shows that the probability of randomization-induced error δ in PaNNLD is no more than 2 e-δ2 K2.