了解和普及近近邻近邻搜索单体近近近图 (Understanding and Generalizing Monotonic Proximity Graphs for Approximate Nearest Neighbor Search)

Graph-based algorithms have shown great empirical potential for the approximate nearest neighbor (ANN) search problem. Currently, graph-based ANN search algorithms are designed mainly using heuristics, whereas theoretical analysis of such algorithms is quite lacking. In this paper, we study a fundamental model of proximity graphs used in graph-based ANN search, called Monotonic Relative Neighborhood Graph (MRNG), from a theoretical perspective. We use mathematical proofs to explain why proximity graphs that are built based on MRNG tend to have good searching performance. We also run experiments on MRNG and graphs generalizing MRNG to obtain a deeper understanding of the model. Our experiments give guidance on how to approximate and generalize MRNG to build proximity graphs on a large scale. In addition, we discover and study a hidden structure of MRNG called conflicting nodes, and we give theoretical evidence how conflicting nodes could be used to improve ANN search methods that are based on MRNG.

翻译：基于图形的算法显示了近邻搜索问题的巨大经验潜力。目前,基于图形的ANN搜索算法主要使用超自然学设计,而这种算法的理论分析却相当缺乏。在本文中,我们从理论角度研究了基于图形的ANN搜索中使用的近距离图的基本模型,称为“单声相邻相邻图 ” (MRNG),从理论角度来研究。我们使用数学证据来解释为什么以MRNG为基础的近距离图往往具有良好的搜索性能。我们还在MRNG上进行实验,并用图形对MNNG进行概括化,以便更深入地了解模型。我们的实验为如何将MNNG进行近距离图的近距离图的近距离图建立大尺度提供了指导。此外,我们发现并研究了MRNG称为冲突节点的隐蔽结构,我们提供了理论证据,说明如何使用相互矛盾的节点来改进以MNNG为基础的AN搜索方法。