$\text{0. Inro}$

1️⃣一些要用到的符号

1. $(U,\mathrm{dist})$为基础度量空间，$S\subseteq U$为包含$n\ge 2$个对象的$\text{Input}$​
2. $h=\lceil {\log }_2\mathrm{diam}(S)\rceil$​
3. $\lambda$​为$(S,\mathrm{dist})$​的倍增维数

2️⃣本节讨论的定理：存在结构可在$\{\begin{array}{l}空间复杂度\text{: }{2}^{O(\lambda )}h\\ \\ 时间复杂度\text{: }{2}^{O(\lambda )}hn\end{array}$内回答$\text{3-ANN}$问题

$\text{1. Sample Nets}$

1️⃣样本网定义：对于$X\subseteq S$，要求$Y$是$X$的$r$-样本网需要满足

1. $Y\subseteq X$
2. $\forall y_1,y_2\in Y$有 $\mathrm{dist}\left(y_1,y_2\right)>r$​
3. $X\subseteq \bigcup _{y\in Y}B(y,r)$即$\forall x\in X,\exists y\in Y$使得$\mathrm{dist}(x,y)\le r$

2️⃣样本网络实例：度量空间为$({\mathbb{N}}^2,\text{dist=Euclidean})$

1. Y ⊆ X ⇒ { Y = { 黑点 } X = { 黑点 + 白点 } Y \subseteq X\Rightarrow\small\begin{cases}Y=\{黑点\}\\\\X=\{黑点+白点\}\end{cases} Y⊆X⇒⎩ ⎨ ⎧​Y={黑点}X={黑点+白点}​​
2. $\mathrm{dist}\left(y_1,y_2\right)>r\Rightarrow$​单个黑点不能出现在两个圆中
3. $X\subseteq \bigcup _{y\in Y}B(y,r)\Rightarrow$所有点只出现在圆的重叠平面内

$\text{2. Structure G}$

1️⃣结构的定义

1. 定义每层结点：$Y_i$层的点即为$S$的$2^i$-样本网$(i=0,1,...,h)$​
   • $Y_h$只有一个对象，并且$2^h\ge \text{diam}(S)$
   • 框定$|Y_i|\le n$后，使得$G$的空间复杂度变为了$O(hn)$​
2. 定义结点的连接
   • 对于$y\in Y_i$与$z\in Y_{i-1}$如果满足$\mathrm{dist}(y,z)\le 7\cdot 2^i$则建立有向连接$y⟶z$ ​
   • 用$N_i^{+}(y)$表示 $y$ 的出度$\text{(out-neighbors)}$

2️⃣结构的性质：$\left|N_i^{+}(y)\right|=2^{O(\lambda )}$即$\left|N_i^{+}(y)\right|$随着$\lambda$​的增加指数级增加

$\text{3. Query}$

1️⃣查询过程

1. 先将$S$转化为图$G$​的结构
2. 对于查询对象$q\in U\backslash S$我们在图$G$中沿某条路径下降(称之为$\pi$)
   • 起始：访问$G$根节点$Y_h$​
   • 下降：$y\in Y_i$与$z\in Y_{i-1}$ 且$i\ge 1$时，按照$\mathrm{dist}(q,z)$​ 最小化原则下降，平局时任选
3. 查询结果即返回$\pi$路径中离$q$最近的一点，即$e^{\ast }$​

2️⃣查询性质

1. 查询的时间复杂度：$\left|N_i^{+}(y)\right|h=2^{O(\lambda )}h$​​
2. 该查询是$q$的$\text{3-ANN}$，即 ∃ e ∈ { y h y h − 1 … y 0 } \exist{}e\in{}\{y_hy_{h-1}\ldots{}y_0\} ∃e∈{yh​yh−1​…y0​}满足$\text{dist}(q,e)\le 3\ast \text{dist}(q,e^{\ast })$