RNG 图就是下面这个月牙里面不能有其他节点，if and are connected by edge ∈ , then ∀ ∈ , with (, ) < (, ), or (, ) < (, )

RNG的搜索路径可能较长（图a），不是单调搜索网络

MRNG

先构建RNG图，找到p到q的路径上的所有点，如果说p和这些点都不相连，则将q作为p的邻接结点。（下图是由图b得来）

NSG索引构建

m是最大出度

1. 用已有算法构建一个KNN图

2. 确定一个质心c，以c为查询向量，贪婪搜索随机向量r，将返回结果作为Navigating Node(n)

3. 对于图中的每一个结点v，通过贪婪搜索算法，得到一条路径(单调？)，将路径上的每一个结点（和v的邻居？）都放到邻居候选集中，按距离排序

4. 利用MRNG选边策略为v挑选m个邻居。添加最近结点和没有冲突的结点5. 最后还要从导航节点出发构建一棵DFS树，确保图的连通。当DFS终止时，对于未链接到树的结点，将他们链接到近似最近邻（用贪婪算法获得）定理及其证明定理1

Theorem 1. Given a finite point set S of n points, randomly distributed in space Ed and a monotonic search network G constructed on S, a monotonic path between any two nodes p, q in G can be found by Algorithm 1 without backtracking.

就是说用这个算法1(贪婪算法)，一定能在一个图中无回溯地找到p、q两点的单调搜索路径(q是查询向量，p是入口向量)

这个定理相当于：对于t次迭代，如果满足∀i∈{1,...,t},d(vi,q)>d(vi+1,q)\forall i \in \{1,...,t\} , d(v_i,q)> d(v_{i+1},q)∀i∈{1,...,t},d(vi​,q)>d(vi+1​,q)，那么就说明找到的路径是单调路径。

数学归纳法证明：

t=1时，存在路径v1=p→r→qv_1=p \rightarrow r \rightarrow qv1​=p→r→q是单调路径。根据算法定义，r是v1的邻居,且δ(v1,q)⩾δ(r,q)δ(v_1,q) \geqslant δ(r,q) δ(v1​,q)⩾δ(r,q)

如果r=v2v_2v2​,那么从v1v_1v1​到v2v_2v2​关于q是单调的。否则，由于 v2 是通过算法 1 找到的，无需回溯，因此 v2 是 v1 的邻居中距离 q 最近的节点。因此，δ(v2, q) ≤ δ(r, q) < δ(v1, q)。假设t=m时，v1,v2,...,vmv_1,v2,...,v_mv1​,v2,...,vm​是单调路径。t=m+1时，同上可证定理二

定理二指出，对于 MSNET，任意两点之间的路径长度为O(n1/dlog⁡(n1/d)/Δr)O\left(n^{1 / d} \log \left(n^{1 / d}\right) / \Delta r\right)O(n1/dlog(n1/d)/Δr)

总结

这篇论文主要就是用这个MRNG重写了邻近图的选边策略，使搜索路径更短，同时保证连通性