2021/08/19 by Jacob D. Baron, R. W. R. Darling, Baron, Jacob D. +5 · 1 citation
Computer Science · #90C35 #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2108.08864
openalex publication_date 2021/08/19 · openalex created_date 2021/08/30 · openalex updated_date 2026/07/28
A triplet comparison oracle on a set S takes an object x ∈ S and for any pair \y, z\ ⊂ S ∖ \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.