Published on Tue Oct 08 2019

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

Leonid Boytsov, Eric Nyberg

A graph-based search algorithm can directly work with non-metric and/or non-symmetric distances. This paves a way to a new line of research of designing index-specific distance functions.

0
0
0
Abstract

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.