论文标题
广义相对邻里图（GRNG）用于相似性搜索
Generalized Relative Neighborhood Graph (GRNG) for Similarity Search
论文作者
论文摘要
相似性搜索是在各种数据集上进行信息检索的基本构建块。邻居的概念通常基于二进制考虑因素，例如K最近的K邻居。但是，考虑到数据通常被组织为具有较低固有维度的流形，邻居的概念必须识别高阶关系，以捕获各个方向的邻居。接近图，例如相对邻居图（RNG），使用捕获方向概念并已成功用于许多应用程序的三元关系。但是，尽管使用广泛使用，但当前用于计算RNG的算法是近似且不可扩展的。本文提出了一种新型的图形，即用于枢轴层的广义相对邻域图（GRNG），然后指导一组示例的RNG的有效构建。它还显示了如何将其扩展到多层层次结构，该层次结构大大改善了最新方法，该方法只能构建近似RNG。
Similarity search is a fundamental building block for information retrieval on a variety of datasets. The notion of a neighbor is often based on binary considerations, such as the k nearest neighbors. However, considering that data is often organized as a manifold with low intrinsic dimension, the notion of a neighbor must recognize higher-order relationship, to capture neighbors in all directions. Proximity graphs, such as the Relative Neighbor Graphs (RNG), use trinary relationships which capture the notion of direction and have been successfully used in a number of applications. However, the current algorithms for computing the RNG, despite widespread use, are approximate and not scalable. This paper proposes a novel type of graph, the Generalized Relative Neighborhood Graph (GRNG) for use in a pivot layer that then guides the efficient and exact construction of the RNG of a set of exemplars. It also shows how to extend this to a multi-layer hierarchy which significantly improves over the state-of-the-art methods which can only construct an approximate RNG.
