Delaunay Graph

Reading time ~1 minute

1.介绍

1.1 Voronoi Diagrams

定义:给定点集(points) ,点(point)的Voronoi region 是这样一个点集,它们到的距离要与P中其它任意点都要接近

在P中具有超过一个最近邻的点集,是P的Voronoi Diagram:

  • 具有两个最近邻的集合组成diagram的edges
  • 具有三或更多最近邻的集合组成了diagram的verticles

点集P被称为Voronoi diagram的sites。

  • 当只有2个点时,,regions可以由垂直平分线定义,如图p1所示。
  • 当只有3个点时,, regions可以由三条垂直平分线定义:

图片名称

图p1

  • 更一般的,与点相关的Voronoi region,是由垂直平分线们定义的half-spaces的交叉:,它是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
  • 如果的最近邻,那边是一条Delaunay edge
  • 存在这样一个圆,它穿过,但不包含任意其它点 是一条Delaunay edge
  • 的外切圆为空 是Delaunay三角形

2.其它

另外,百度的人在《On Efficient Retrieval of Top Similarity Vectors》中有delaunay graph有系统的整理。这里重新拿出来分享一下:

2.3 Delaunay Graph

Delaunay Graph在相似搜索中扮演着重要角色。-Delaunay Graph的性质和构造,在文献中有介绍。我们可以将定义泛化成任意二元函数(binary function)中,包括inner product。

定义2.1:对应于f和的Voronoi cell (洛诺伊/泰森多边形)是以下集合:

表示一个极点(extreme point),如果它与一个非空Voronoi cell有关。

定义2.2:对应f和S的Delaunay Graph G是一个无向图,集点S满足,当且仅当.

在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]中的定义,例如:是extreme的,当且仅当x是在S的凸包边界(boundary of the convex hull)上。在二维情况下,edges形成了凸包边界,如图1所示。

2.4 Delaunay Graph上的Search

在Delaunay Graph上的搜过对于相似度搜索是很高效的【Morozov 2018】。在inner product的情况下,给定任意query vector ,我们从一个极点出发,接着移到与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 ,在X上相连,G是对应于f和一些S的Delaunay Graph,那么对于,在greedy search上的local maximum会从一个极点开始,也就是说,会满足:

其中是一个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

参考

PAL position bias介绍

华为在《PAL: a position-bias aware learning framework for CTR prediction in live recommender systems》提出了一种解决position-bias方法。# 摘要在推荐系统中精准预测CTR...… Continue reading

facebook DLRM介绍

Published on November 01, 2019

feedback loops介绍

Published on October 28, 2019