# Online Partitioned Local Depth for semi-supervised applications

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 17 references that are in the map.
- First posted on arXiv 17 Dec 2025.

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

- [ADBench: Anomaly Detection Benchmark](https://mlsanity.com/paper/2206.09426/) (2022)
- [Data-Driven Network Neuroscience: On Data Collection and Benchmark](https://mlsanity.com/paper/2211.12421/) (2022)
- [Partitioned K-nearest neighbor local depth for scalable comparison-based learning](https://mlsanity.com/paper/2108.08864/) (2021)
- [Generalized partitioned local depth](https://mlsanity.com/paper/2303.10167/) (2023)
- [Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths](https://mlsanity.com/paper/2307.16652/) (2023)

## Abstract (arXiv)

We introduce an extension of the partitioned local depth (PaLD) algorithm that is adapted to online applications such as semi-supervised prediction. PaLD is best known for unsupervised, parameter-free clustering, but its robustness is based on triples of data points, making exact analysis computationally expensive. Research is ongoing to improve the scalability of the underlying discrete algorithm and expand the breath of PaLD's applications. The new algorithm we present, online PaLD, is well-suited to situations where it is possible to pre-compute a cohesion network from a reference dataset. After O(n3) steps to construct a queryable data structure, online PaLD can extend the cohesion network to a new data point in O(n2) time. Our approach complements previous speed up approaches based on approximation and parallelism. In practical terms, online PaLD makes larger datasets accessible to exact analysis with a relatively simple implementation. We present applications to online anomaly detection and semi-supervised classification for health-care datasets as initial illustrations of online PaLD's potential to expand applications of the PaLD framework.