Generalized Relative Neighborhood Graph (GRNG) for Similarity Search
Generalized Relative Neighborhood Graph (GRNG) for Similarity Search
复制标题
DOI：
10.48550/arxiv.2208.10022
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
C. Foster;Berk Sevilmis;B. Kimia
中科院分区：
文献类型：
--
作者：
C. Foster;Berk Sevilmis;B. Kimia
相似性搜索是各种数据集上信息检索的基本构建块。邻居的概念通常基于二元考虑，例如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.