# A Triangle Inequality for Cosine Similarity

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 22 references that are in the map.
- First posted on arXiv 8 Jul 2021.

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

- [ELKI: A large open-source library for data analysis - ELKI Release 0.7.5 "Heidelberg"](https://mlsanity.com/paper/1902.03616/) (2019)
- [BETULA: Numerically Stable CF-Trees for BIRCH Clustering](https://mlsanity.com/paper/2006.12881/) (2020)

## Built on by (most cited first, 13 of 13)

- [Statistical Hypothesis Testing for Auditing Robustness in Language Models](https://mlsanity.com/paper/2506.07947/) (2025)
- [Federated Domain Generalization with Data-free On-server Matching Gradient](https://mlsanity.com/paper/2501.14653/) (2025)
- [CADIS: Handling Cluster-skewed Non-IID Data in Federated Learning with Clustered Aggregation and Knowledge DIStilled Regularization](https://mlsanity.com/paper/2302.10413/) (2023)
- [FedGrad: Mitigating Backdoor Attacks in Federated Learning Through Local Ultimate Gradients Inspection](https://mlsanity.com/paper/2305.00328/) (2023)
- [tinyCLAP: Distilling Constrastive Language-Audio Pretrained Models](https://mlsanity.com/paper/2311.14517/) (2023)
- [Dynamic Topology Optimization for Non-IID Data in Decentralized Learning](https://mlsanity.com/paper/2602.03383/) (2026)
- [Accelerating k-Means Clustering with Cover Trees](https://mlsanity.com/paper/2410.15117/) (2024)
- [Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds](https://mlsanity.com/paper/2411.12154/) (2024)
- [Design of the topology for contrastive visual-textual alignment](https://mlsanity.com/paper/2209.02127/) (2022)
- [On Projections to Linear Subspaces](https://mlsanity.com/paper/2209.12485/) (2022)
- [LGDE: Local Graph-based Dictionary Expansion](https://mlsanity.com/paper/2405.07764/) (2024)
- [Beyond L2: Generalizing Abductive Latent Explanations to Diverse Prototype-Based Architectures](https://mlsanity.com/paper/2608.16773/) (2026)
- [On the Triangle Inequality for the Jaccard Distance in Arbitrary Lattices](https://mlsanity.com/paper/2608.18194/) (2026)

## Abstract (arXiv)

Similarity search is a fundamental problem for many data analysis techniques. Many efficient search techniques rely on the triangle inequality of metrics, which allows pruning parts of the search space based on transitive bounds on distances. Recently, Cosine similarity has become a popular alternative choice to the standard Euclidean metric, in particular in the context of textual data and neural network embeddings. Unfortunately, Cosine similarity is not metric and does not satisfy the standard triangle inequality. Instead, many search techniques for Cosine rely on approximation techniques such as locality sensitive hashing. In this paper, we derive a triangle inequality for Cosine similarity that is suitable for efficient similarity search with many standard search structures (such as the VP-tree, Cover-tree, and M-tree); show that this bound is tight and discuss fast approximations for it. We hope that this spurs new research on accelerating exact similarity search for cosine similarity, and possible other similarity measures beyond the existing work for distance metrics.