# ProHD: Projection-Based Hausdorff Distance Approximation

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

## Key facts

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

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

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Refined Complexity of PCA with Outliers](https://mlsanity.com/paper/1905.04124/) (2019)
- [Relative Hausdorff Distance for Network Analysis](https://mlsanity.com/paper/1906.04936/) (2019)
- [On the Budgeted Hausdorff Distance Problem](https://mlsanity.com/paper/2306.02151/) (2023)
- [Approximate Hausdorff Distance for Multi-Vector Databases](https://mlsanity.com/paper/2503.06833/) (2025)

## Abstract (arXiv)

The Hausdorff distance (HD) is a robust measure of set dissimilarity, but computing it exactly on large, high-dimensional datasets is prohibitively expensive. We propose ProHD, a projection-guided approximation algorithm that dramatically accelerates HD computation while maintaining high accuracy. ProHD identifies a small subset of candidate "extreme" points by projecting the data onto a few informative directions (such as the centroid axis and top principal components) and computing the HD on this subset. This approach guarantees an underestimate of the true HD with a bounded additive error and typically achieves results within a few percent of the exact value. In extensive experiments on image, physics, and synthetic datasets (up to two million points in D=256), ProHD runs 10--100× faster than exact algorithms while attaining 5--20× lower error than random sampling-based approximations. Our method enables practical HD calculations in scenarios like large vector databases and streaming data, where quick and reliable set distance estimation is needed.