Accurate and Fast Retrieval for Complex Non-metric Data via Neighborhood Graphs
This work addresses retrieval challenges in domains with non-metric or non-symmetric distances, such as multimedia or bioinformatics, though it appears incremental as it builds on existing graph-based methods.
The paper tackles the problem of efficient retrieval for complex non-metric data by proposing a graph-based search algorithm that avoids performance degradation from metric-space mapping or distance symmetrization, achieving improved performance through index-specific distance functions.
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.