Online Partitioned Local Depth for semi-supervised applications

2025/12/17 by Foley, John D., Lee, Justin T.
#68W40 #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2512.15436

Abstract

We introduce an extension of the partitioned local depth (PaLD) algorithm that is adapted to online applications such as semi-supervised prediction. The new algorithm we present, online PaLD, is well-suited to situations where it is a possible to pre-compute a cohesion network from a reference dataset. After O(n³) steps to construct a queryable data structure, online PaLD can extend the cohesion network to a new data point in O(n²) time. Our approach complements previous speed up approaches based on approximation and parallelism. For illustrations, we present applications to online anomaly detection and semi-supervised classification for health-care datasets.

Citations

• Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths
• ADBench: Anomaly Detection Benchmark
• Partitioned K-nearest neighbor local depth for scalable comparison-based learning

Related

• Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths
• Semi-Supervised Deep Learning Using Improved Unsupervised Discriminant Projection
• Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation
• Online Semi-Supervised Learning on Quantized Graphs
• Adapting to Online Distribution Shifts in Deep Learning: A Black-Box Approach