arXiv:2511.18207cs.IRcs.LG2025-11

用投影快速估算点集距离,又快又准。

ProHD: Projection-Based Hausdorff Distance Approximation

  • 通过投影关键方向筛选候选点,大幅降低计算量。
  • 在百万级高维数据上提速10到100倍,误差比随机采样低5到20倍。
  • 适合向量数据库、流式数据等需快速距离估计的场景。

Hausdorff距离(HD)是衡量集合差异的鲁棒指标,但在大规模高维数据上精确计算代价高昂。我们提出ProHD,一种基于投影引导的近似算法,显著加速HD计算并保持高精度。ProHD通过将数据投影到少数关键方向(如质心轴和前几个主成分),识别出少量“极端”候选点,并在该子集上计算HD。该方法保证对真实HD的下界估计,且加性误差有界,通常结果仅比精确值低几个百分点。在图像、物理及合成数据集(最多达两百万个点,维度D=256)上的大量实验表明,ProHD比精确算法快10至100倍,同时误差比基于随机采样的近似方法低5至20倍。本方法使在大型向量数据库和流式数据等场景中实现高效可靠的集合距离估计成为可能。

原文摘要 · Abstract (English)

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 \textbf{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$\times$ faster than exact algorithms while attaining 5--20$\times$ 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.

距离度量高维数据加速计算投影方法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。