Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.06833 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909532490301440 |
|---|---|
| author | Zhao, Dongfang |
| author_facet | Zhao, Dongfang |
| contents | The Hausdorff distance is a fundamental measure for comparing sets of vectors, widely used in database theory and geometric algorithms. However, its exact computation is computationally expensive, often making it impractical for large-scale applications such as multi-vector databases. In this paper, we introduce an approximation framework that efficiently estimates the Hausdorff distance while maintaining rigorous error bounds. Our approach leverages approximate nearest-neighbor (ANN) search to construct a surrogate function that preserves essential geometric properties while significantly reducing computational complexity. We provide a formal analysis of approximation accuracy, deriving both worst-case and expected error bounds. Additionally, we establish theoretical guarantees on the stability of our method under transformations, including translation, rotation, and scaling, and quantify the impact of non-uniform scaling on approximation quality. This work provides a principled foundation for integrating Hausdorff distance approximations into large-scale data retrieval and similarity search applications, ensuring both computational efficiency and theoretical correctness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_06833 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximate Hausdorff Distance for Multi-Vector Databases Zhao, Dongfang Databases Computational Geometry The Hausdorff distance is a fundamental measure for comparing sets of vectors, widely used in database theory and geometric algorithms. However, its exact computation is computationally expensive, often making it impractical for large-scale applications such as multi-vector databases. In this paper, we introduce an approximation framework that efficiently estimates the Hausdorff distance while maintaining rigorous error bounds. Our approach leverages approximate nearest-neighbor (ANN) search to construct a surrogate function that preserves essential geometric properties while significantly reducing computational complexity. We provide a formal analysis of approximation accuracy, deriving both worst-case and expected error bounds. Additionally, we establish theoretical guarantees on the stability of our method under transformations, including translation, rotation, and scaling, and quantify the impact of non-uniform scaling on approximation quality. This work provides a principled foundation for integrating Hausdorff distance approximations into large-scale data retrieval and similarity search applications, ensuring both computational efficiency and theoretical correctness. |
| title | Approximate Hausdorff Distance for Multi-Vector Databases |
| topic | Databases Computational Geometry |
| url | https://arxiv.org/abs/2503.06833 |