# Accurate and Fast Retrieval for Complex Non-metric Data via Neighborhood Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2019.

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

- [Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization](https://mlsanity.com/paper/2210.12579/) (2022)
- [Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders](https://mlsanity.com/paper/2405.03651/) (2024)

## Abstract (arXiv)

We demonstrate that a graph-based search algorithm-relying on the construction of an approximate neighborhood graph-can directly work with challenging non-metric and/or non-symmetric distances without resorting to metric-space mapping and/or distance symmetrization, which, in turn, lead to substantial performance degradation. Although the straightforward metrization and symmetrization is usually ineffective, we find that constructing an index using a modified, e.g., symmetrized, distance can improve performance. This observation paves a way to a new line of research of designing index-specific graph-construction distance functions.