1.介绍
1.1 Voronoi Diagrams
定义：给定点集(points) \(P=\lbrace p_1, \cdots, p_n \rbrace\)，点(point)\(p_i\)的Voronoi region \(V(p_i)\)是这样一个点集，它们到\(p_i\)的距离要与P中其它任意点都要接近\(p_i\)：
\[V(p_i) = \lbrace x \mid |p_i - x| \leq |p_j -x|, \ \ \forall 1 \leq i,j \leq n \rbrace\]在P中具有超过一个最近邻的点集，是P的Voronoi Diagram：
- 具有两个最近邻的集合组成diagram的edges
- 具有三或更多最近邻的集合组成了diagram的verticles
点集P被称为Voronoi diagram的sites。
- 当只有2个点时，\(P=\lbrace p_1, p_2 \rbrace\)，regions可以由垂直平分线定义，如图p1所示。
- 当只有3个点时，\(P=\lbrace p_1, p_2 \rbrace\), regions可以由三条垂直平分线定义：
图p1
- 更一般的，与点\(p_i\)相关的Voronoi region，是由垂直平分线们定义的half-spaces的交叉：\(V(p_i) = \cap_{j \neq i} H(p_i, p_j)\)，它是convex多边形。
图p2
Voronoi region与points是1-to-1对应关系。大多数Voronoi vertices具有3阶。Voronoi faces可以是unbounded。
关于Voronoi region的性质，略。
1.2 Delaunay Triangulation
Delaunay三角化是Voronoi Diagram的直线对偶（straight-line dual）。注意：Delaunay edges不必跨过（cross）它的Voronoi duals。
图p3
它的性质有：
- D(P)的edges不会交叉
- 如果没有4个点共圆，D(P)是个三角形
- D(P)的boundary是P的convex hull
- 如果\(p_j\)是\(p_i\)的最近邻，那边\(\overline{p_i p_j}\)是一条Delaunay edge
- 存在这样一个圆，它穿过\(p_i\)和\(p_j\)，但不包含任意其它点 \(\Leftrightarrow\) \(\overline{p_i p_j}\)是一条Delaunay edge
- \(p_i, p_j, p_k\)的外切圆为空 \(\Leftrightarrow\) \(\triangle p_i p_j p_k\)是Delaunay三角形
2.其它
另外，百度的人在《On Efficient Retrieval of Top Similarity Vectors》中有delaunay graph有系统的整理。这里重新拿出来分享一下：
2.3 Delaunay Graph
Delaunay Graph在相似搜索中扮演着重要角色。\(l^2\)-Delaunay Graph的性质和构造，在文献中有介绍。我们可以将定义泛化成任意二元函数（binary function）中，包括inner product。
定义2.1：对应于f和\(x_i\)的Voronoi cell \(R_i\)（洛诺伊／泰森多边形）是以下集合：
\[R_i := \lbrace q \in X: f(x_i, q) \geq f(x,q) \ for \ all \ x \in S \rbrace\]\(x \in S\)表示一个极点（extreme point），如果它与一个非空Voronoi cell有关。
定义2.2：对应f和S的Delaunay Graph G是一个无向图，集点S满足\(\lbrace x_i, x_j \rbrace \in G\)，当且仅当\(R_i \cap R_j \neq 0\).
在inner product space上一个关于Voronoi cells以及对应Delaunay Graph的示例如图1所示。不同颜色的区域对应着极点（红色点）的Voronoi cells。Delaunay Graph连接着极点（extreme points）。不同于指标相似度（例如：l2-norm），对应inner product一些数据点的Voronoi cells可能为空。通过定义2.2, 当它的Voronoi cell为空时，该数据点是孤立的（例如：没有入射边：incident edges）。如图1所示，有许多孤立点（蓝色点）。极点的比例总体上相对较小。根据定理2.1, 极点可以为任意非零query达到一个最大inner product score。
图1
极点的定义等价于paper[Barber]中的定义，例如：\(x \in S\)是extreme的，当且仅当x是在S的凸包边界（boundary of the convex hull）上。在二维情况下，edges形成了凸包边界，如图1所示。
2.4 Delaunay Graph上的Search
在Delaunay Graph上的搜过对于相似度搜索是很高效的【Morozov 2018】。在inner product的情况下，给定任意query vector \(q \in X\)，我们从一个极点出发，接着移到与q具有一个较大inner product的neighbor上。我们重复该step，直到获得一个这样的极点：它与q的内积要大于所有它的neighbors，我们会返回它。这样返回的local optimum实际上是global optimum。
通常，对于任意searching measure f，如果相应的Voronoi cells是相连的，那么通过greedy search返回的local optimum也是global optimum。证明明在Morozov 2018中有介绍。
定理2.1 假设f满足：对应于S的任意子集的Voronoi cell \(R_i\)，在X上相连，G是对应于f和一些S的Delaunay Graph，那么对于\(q \in X\)，在greedy search上的local maximum会从一个极点开始，也就是说，\(x_i \in S\)会满足：
\[f(x_i, q) \geq \overset{max}{x \in N(x_i)} f(x,q)\]其中\(N(x_i) = \lbrace x \in S: \lbrace x_i, x \rbrace \in G \rbrace\)是一个global maximum。
假设定理2.1的该猜想（例如：连通的Voronoi cells）是有效的，我们认为，在Delaunay Graph上搜索可以找到global maximum。对于inner product的情况，很容易确认该猜想有效与否，因为关于内积的Voronoi cells可以为空，或者一个凸锥形（convex cone），因此他们是连通的。接着，我们可以宣禾水金，在内积的Delaunay Graph上的searching，S中的vector具有与query vector的最大内积。
3.Inner Product Delaunay Graph
尽管Delaunay Graph在相似度搜索上展示了它的潜力，Delaunay Graph在大规模和高维数据集上的直接构建是不可行的，因为在高维空间中edges数目会指数增长。为了解决该问题，实际算法通常会近似Delaunay Graphs。在这部分，我们会提出新的算法来在inner product space上构建approximate Delaunay Graph，称为“IPDG：Inner product Delaunay Graph”。这个算法有两个关键特性：
- i) edge selection只适用于inner product
- ii) 有两轮的graph construction