# Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 57 references that are in the map.
- First posted on arXiv 6 Jun 2025.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Survey of Vector Database Management Systems](https://mlsanity.com/paper/2310.14021/) (2023)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [Hashing for Similarity Search: A Survey](https://mlsanity.com/paper/1408.2927/) (2014)
- [Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data](https://mlsanity.com/paper/1810.07355/) (2018)
- [SOAR: Improved Indexing for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2404.00774/) (2024)
- [Hierarchical Quasi-Clustering Methods for Asymmetric Networks](https://mlsanity.com/paper/1404.4655/) (2014)
- [LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2410.18926/) (2024)
- [Admissible Hierarchical Clustering Methods and Algorithms for Asymmetric Networks](https://mlsanity.com/paper/1607.06335/) (2016)
- [Metric Representations of Network Data](https://mlsanity.com/paper/1911.00164/) (2019)
- [Tao: A Learning Framework for Adaptive Nearest Neighbor Search using Static Features Only](https://mlsanity.com/paper/2110.00696/) (2021)

## Abstract (arXiv)

An ultrametric space or infinity-metric space is defined by a dissimilarity function that satisfies a strong triangle inequality in which every side of a triangle is not larger than the larger of the other two. We show that search in ultrametric spaces with a vantage point tree has worst-case complexity equal to the depth of the tree. Since datasets of interest are not ultrametric in general, we employ a projection operator that transforms an arbitrary dissimilarity function into an ultrametric space while preserving nearest neighbors. We further learn an approximation of this projection operator to efficiently compute ultrametric distances between query points and points in the dataset. We proceed to solve a more general problem in which we consider projections in q-metric spaces -- in which triangle sides raised to the power of q are smaller than the sum of the q-powers of the other two. Notice that the use of learned approximations of projected q-metric distances renders the search pipeline approximate. We show in experiments that increasing values of q result in faster search but lower recall. Overall, search in q-metric and infinity metric spaces is competitive with existing search methods.