Massive parallelization of projection-based depths

2025/06/09 by Leonardo Leone, Leone, Leonardo, Pavlo Mozharovskyi +3
Computer Science · Engineering · #Advanced Measurement and Metrology Techniques #Advanced Numerical Analysis Techniques #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Optical measurement and interference techniques #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2506.08262

openalex publication_date 2025/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This article introduces a novel methodology for the massive parallelization of projection-based depths, addressing the computational challenges of data depth in high-dimensional spaces. We propose an algorithmic framework based on Refined Random Search (RRS) and demonstrate significant speedup (up to 7,000 times faster) on GPUs. Empirical results on synthetic data show improved precision and reduced runtime, making the method suitable for large-scale applications. The RRS algorithm (and other depth functions) are available in the Python-library data-depth (https://data-depth.github.io/) with ready-to-use tools to implement and to build upon this work.

Citations

• Approximate computation of projection depths
• Choosing among notions of multivariate depth statistics
• Depth for curve data and applications
• Exact computation of the halfspace depth
• A Fast Algorithm for the Minimum Covariance Determinant Estimator
• A NEW MEASURE OF RANK CORRELATION

Related

• BANG: Billion-Scale Approximate Nearest Neighbor Search using a Single GPU
• Approximate computation of projection depths
• Mathematical Computation on High-dimensional Data via Array Programming and Parallel Acceleration
• JUNO: Optimizing High-Dimensional Approximate Nearest Neighbour Search with Sparsity-Aware Algorithm and Ray-Tracing Core Mapping
• Billion-scale similarity search with GPUs