  A triplet comparison oracle on a set $S$ takes an object $x \in 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(n^2 \log{n})$ oracle calls and $O(n^3)$ 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 \log{n})$ 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 K^2)$
post-processing steps. Concentration of measure shows that the probability of
randomization-induced error $\delta$ in PaNNLD is no more than $2 e^{-\delta^2
K^2}$.
