Infinity Search: Approximate Vector Search With Projections On Q-metric Spaces

Abstract

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 ren

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keypariente2025infinity

Related papers

• Hilbert Exclusion: Improved Metric Search Through Finite Isometric Embeddings (2016)10.07
• Quantization Meets Projection: A Happy Marriage For Approximate K-nearest Neighbor Search (2024)0.00
• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00
• Indexing Metric Spaces For Exact Similarity Search (2020)10.85
• Practical And Asymptotically Optimal Quantization Of High-dimensional Vectors In Euclidean Space For Approximate Nearest Neighbor Search (2024)8.82
• High-dimensional Similarity Search With Quantum-assisted Variational Autoencoder (2020)8.82
• Promips: Efficient High-dimensional C-approximate Maximum Inner Product Search With A Lightweight Index (2021)8.35
• Sublinear Data Structures For Nearest Neighbor In Ultra High Dimensions (2025)0.00