Delaunay Graph

Reading time ~1 minute

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

参考

ali COLD介绍

ali在《COLD: Towards the Next Generation of Pre-Ranking System》中讲述了他们的实现。# 摘要长期以来,pre-ranking只是ranking模块的一个简化版本,它要处理待排序的更大集合的候选。这里的努力是为了简化r...… Continue reading

dynamic embedding介绍

Published on August 02, 2020

md embedding介绍

Published on July 01, 2020