NSW

Reading time ~1 minute

Yury Malkov在《Approximate nearest neighbor algorithm based on navigable small world graphs》提出了NSW算法。

在了解NSW之前,我们先看下SW(small world)的定义,from wikipedia。

0.Small world

一个small-world network是一种graph。在该graph中,大多数nodes相互之间都不是neighbors,但对于任意给定的node的neighbors,这些neighbors很可能相互之间也是neighbors,大多数nodes可以通过一个较小数目的hops或steps从每个其它node来到达。特别的,一个small-world network被定义成这样一个网络:其中两个随机选中的nodes间的一般距离(typical distance)L,会与在该网络中与nodes N的数目成log比例增长,即:

其中,聚集度(clustering coefficient)并不小。在社交网络场景中,这会导致Small world现象:陌生人间通过一个关于熟人的短链进行连接。许多经验图(empirical graphs)展示了small-world效应,包括:社交网络、wikipedia的wikis、基因网络、以及Internet的底层架构。在现代计算机硬件中的许多片上网络(network-on-chip)架构也受它的启发。

Ducan Watts 1998. 将一种特定类型的small-world networks定义成一类random graphs。他们注意到,graphs可以根据两个独立的结构化特征进行分类,称为:聚集度(clustering coefficient)、以及平均node-to-node距离(也被称为:平均最短路径长度)。纯随机图(purely random graphs),根据ER模型构建,会有一个很小的平均最短路径长度,以及一个较小的聚集度。Watts等发现:事实上许多实际网络具有一个较小的平均最短路径长度,以及一个要比random chance所期望的要高很多的一个聚集度。Watts等接着提出了一个新的graph模型,称为WS model,它具有:

  • (i)一个较小的平均最短路径长度
  • (ii) 一个大的聚集度

图片名称

图0

SMall-world的性质

small-world趋向于包含团(cliques)、近团(near-cliques),它们表示子网络,这样的子网络中任意两个nodes间都有connections。这由较高的聚集度的定义性质产生。第二,大多数nodes pairs至少由一个短路径进行连接。这由较小的平均最短路径长度性质产生。一些其它性质也经常与small-world network相关。通常,在网络中存在过多的hubs-nodes,会具有大量connections(也被称为:较高的degree nodes)。这些hubs作为公共connections,作为与其它edges间短路径长度的中介。通过类比,航空公司的small-world network具有一个较小的mean-path length(例如:两个城市间,你可能必须花三或更少的航班),因为许多航班会通过hub城市进行路由。该性质通常通过考虑在网络中的nodes的比例(具有特定数目connections经过它们,即该network的degree分布)来进行分析。比起具有更大hubs的network会具有一个更大比例的高degree的nodes,因此,degree分布会在高degree值上被增强。也被称为是“宽尾分布(fat-tailed distribution)”。具不非常不同拓朴的graphs,可以作为small-world networks,只要他们满足上述两个必须的定义。

介绍

任意软件系统的可扩展性受它的数据结构的扩展性限制。大规模分布式系统,像Bittorrent 、Skype都基于分布式hash tables。后者的数据结构具有良好的可扩展性,但它们的搜索功能只限定于exact matching。该限制的提出是因为:当一个element value做出微小变更时,会导致在hash value上出来大的变化,使得hash-based方法很难应用于range search以及相似度搜索问题上。

然而,有许多应用(比如:模式识别、图片内容检索、机器学习、推荐系统、DNA序列相似发现、语义文档检索等)需要进行相似度搜索,而非exact matching。KNNS问题是相似度搜索的一个数学公式。被定义如下:

给定一个query (其中:D是所有可能对象的集合),我们需要从一个有限对象集合中寻找k个最近的对象 。两个对象的相近度或近似度可以定义成一个距离函数

KNNS问题的一个naive解法是:计算q与X中的每个element的距离函数。这会导致线性搜索时间复杂度,使得它很难用于large size的datasets上。

我们的解法是:将数据结构表示成一个graph ,其中来自X每个object 会与V中的一个顶点(vertex) 唯一关联。为query q搜索X中的最近elements的问题,就转化成了:在graph G中搜索一个vertices集合。

这为构建面向分布式相似度搜索(decentralized similarity search oriented)的存储系统带来了机遇,其中物理数据位置(physical data location)不依赖于内容(content),因为每个数据对象可以被放置在任意一个物理机器上,可以通过links相互连接,就像p2p系统一样。

在具有metric objects的graphs中的基础顶点搜索算法(basic vertex search algorithms)之一是:贪婪搜索算法(greedy search)。它有一个简单实现,可以从任意顶点初始化。为了让该算法正确工作(总是返回精确结构),该网络必须包含Delaunay graph作为它的subgraph,它与Voronoi tessellation成对偶关系。然而,与Delaunay graph相关的主要缺点是:它需要知道metric space的内部结构,这会遭受维度灾难。再者,对于上述应用,不需要precise exactness的search。因此,发现exact的最近邻的问题,可以通过ANNS来替代,因而我们不需要支持whole/exact Delaunay graph。

具有log scalibility的graphs的greedy search算法,被称为NSW graphs,它们定义在Euclidean spaces上。注意,像paper[10]中的small world模型(不是navigable small world)不会有该特性。尽管在graph中有短路径(short paths),greedy算法不会趋向于寻找它们,在结束时具有幂次的搜索复杂度。构建一个NSW graphs的解法,是针对general spaces提出的,但他们通常更复杂,需要做采样、迭代、rewiring等。我们展示了small word的navigation特性可以通过一个更简单的技术来达到,无需对metric space内部结构的先验知识(例如:维度、数据的density分布)。

在本paper中,我们为该数据结构构建提出了一个简单算法,它基于一个NSW network拓朴,使用greedy search算法来做ANNS。graph G(V,E)包含了Delaunay graph的近似,具有long-range links以及small-world navigation特性。我们提出的search算法可以选择search的accuracy,无需修改结构。提出的算法不会使用坐标表示,不会假定Euclidean spaces的特性,因为它们只基于objects与query间的距离比较,因此原则上,可以应用于general metric(或non-metric) spaces的数据上。实验表明,对于欧氏数据只能很弱的维度依赖。

2.相关工作

kd-tree和quadra trees首先应用在kNN问题上。它们在2-3维数据表现良好(搜索复杂度接近O(logn)),但这些结构最坏case的分析有的复杂度,其中d是维度。

在[8]中提出了一个完全近邻搜索(exact-proximity search)结构,它使用Delaunay graph和greedy search算法。作者表示,在通用metric space中发现exact Delaunay graph是不可能的,为了保持search的exact,他依赖回溯(backtracking)。提出的数据结构在高维数据上的构建时间为、搜索时间为;在低维数据上为

总之,当前没有方法能有效在高维指标空间上进行有效的exact NNS。背后的原因是维数灾难。为了避免维数灾难,仍在elements数目中保留对数开销,提出减少kNN问题解的需求,使它近似(近似kNN)。

两种近似最近邻搜索的常用定义

  • 方法一:使用预定义的accuracy 。它意味着,query和在结果中的任何element间的距离不超过 乘以 query到它真正第k个最近邻的距离。这样的方法在[19-23]中有描述。
  • 方法二:使用”recall”(true k最近elements的比例)来给出概率,保证找到离query最近的k个true closest的点。

一些结构(19-23)只能应用到欧氏空间(Euclidean space)。其它方法[24-31]则应用到通用指标空间(general metric spaces)上。更多详见[32-33]。

PI(排列索引)是一种有效的无分布算法,很适合通用指标空间。PI背后的思想是,将每个database object使用索引集合的排列进行表示,并通过与该object的距离进行排序。objects间的距离暗示着各自排列间的距离。PI对于高维数据集具有很高的precision和recall。

paper [26] 则构建一个概率化tree-like结构来在通用指标空间上进行ANNS,它基于最近邻的选择。该算法会模似现实数据。paper[27]则在构建算法时决定最近邻,在搜索时使用greedy算法。该算法的主要缺点是与dataset size的线性扩展性很差。两种算法都提供了很高的recall。

paper[9]使用NSW和greedy search算法来寻找最近邻。该算法依赖于link length概率遵循幂律的random long-range links,其中对应navigation,2维lattice对应用结果纠正。为了具有NSW特性,link length分布必须具有一个指定值。在Voronet[35]中,Kleignberg的方法被扩展到任意2维数据上,通过构建一个二维的Delaunay三角化来替代regular lattic。在[13]中。。。

3.核心思想

structure S通过一个graph G(V,E)所表示的NSW network来构建。

  • graph G(V,E):表示的一个navigable small word网络,其中,来自集合X的objects是唯一映射到set V的vertices上,会通过structure S来构建。
  • edge E的集合由sturecture构建算法来决定。

术语:

  • vertex/element/object:由于每个vertex会唯一映射到集合X的一个element上,我们会交替使用术语“vertex”、”element”和”object”。
  • friend:我们会使用术语“friends”来表示共享一个edge的vertices。
  • friend list:vertices的列表会与vertex 共享一个公共edge,被称为vertex 的friend list。

我们会使用greedy search算法的一个变种作为base算法来进行k-NN search。它会遍历该graph,每次从一个element到另一个element,会选择一个离该query最近的未访问friend,直到它达到一个停止条件。见4.2节所述。

注意,在graph中的links(edges)有两个不同作用:

  • 1) short-range links:一个子集,被用于Delaunay graph的一个近似,由greedy search算法所需
  • 2) long-range links:另一个子集,它被用于greedy search的对数扩展(log scaling)。它负责contructed graph的NSW属性。

结构的表现如图1所示。

图片名称

图1 structure的图表示。

  • 圆(verticles):是在metric space中的data
  • 黑色的edges:是Delaunay graph的近似
  • 红色的edges:是log scaling的long range links
  • 箭头:表示greedy算法的样本路径,从entry point到query(绿色)。

该structure的构建基于所有elements上的连续插入。对于每个新进入的element,我们会发现离该structure最近的neighbors的集合(Delaunay graph 近似)。该set被连接到该element,反之亦然。随着越来越多的elements被插入到该structure,之前作为short-range links的links会变成long-range links,从而生成一个NSW。在该结构中的所有queries是独立的;它们可以并行完成,如果elements被随机放置到物理计算机节点上,处理query的负载可以跨物理节点共享。

4.搜索算法

4.1 basic greedy search算法

basic single NN搜索算法会以从一顶点到另一顶点的方式遍历graph G(V,E)上的edges。该算法有两个参数:query和vertex ,它是一个search的起始点(entry point)。从entry point开始,该算法会计算query q到当前vertex的friend list上的每个vertex的距离,接着选择具有最小距离的一个vertex。如果query和所选vertex间的距离小于当前距离(query和当前element),那么该算法会移到所选vertex上,它将变成新的current vertex。当它达到一个local minimum时,该算法会停止:一个vertex的friend list不包含这样的vertex(比起friend list上的vertex,该vertex与query更近)。该算法如下:

图片名称

算法1

该element对于query 都有一个local minimum:在该set X中的所有elements中的一个element,它与query q的距离真实最接近(true closet)、或者错误最接近(false closet,即一个error)。

如果structure中的每个element,都在它的voronoi neighbors的friend list中有保存,那么这会阻止false global minima的存在。维护这样的条件等价于构建Delaunay graph,它是Voronoi diagram的对偶(dual)。

结果表明,为一个未知metric space决定exact Delaunay graph是不可能的,因为我们不能避免false global minima的存在。对于上述定义的近似搜索的问题,它并不是个障碍,因为近似搜索不需要整个Delaunay graph。

注意,与在[19-23]中定义的ANN(其中它被表述成e-neighborhood)是有区别的。像[24-31],在我们的sturcture中,对于算法NN结果和true NN结果间的距离绝对值没有限制。该结果保证是有概率的,意味着:只有寻找true最近邻的概率是有保证的。当数据分布高度倾斜,并且很难为所有regions定义value e时,使用这样的搜索有效性定义更便利。

4.2 k-NN搜索的修改版

在我们[36]的工作中,我们使用一种基于m个searches的series的k-NN搜索的简单算法,并返回它们的最佳结果。对于每个后续的search,找不到最邻近的概率会指数递减,无需重构建(reconstruction)就可以增强(boosting)该sturcture的accuracy。

在该部分,我们提出了一个更复杂版本的kNN算法,它有两个关键修改:

  • 1) 使用了不同的stop condition:该算法会在与该queries最接近的、但之前未访问过的elements上进行迭代(例如:那些link list未被读到的elements)。当在下次迭代时它会停止,对该query的k个最近的结果不会变。简言之,该算法会继续以一种greedy的方式探索最接近elements的neighborhood,只要在每个step上它可以提升已知的k个closest elements。
  • 2) 列表visitedSet:即之前被访问过的elements,它会被跨搜索序列共享,以便阻止无用的重复抽取。

图片名称

算法2

有序列表TreeSet的使用,允许以与该query的接近顺序来保存评估过的elements,这可以很方便地从该set中抽取最近的elements,它在steps 6, 9, 20被需要。

如果m足够大,该算法会成为一个exhaustive search,假设entry points不会被重复使用。如果该网络的graph具有small-world属性,那么它可以选择一个随机vertex,无需任意metric计算,在随机steps数目(与dataset size的log成比例)后,这不会产生整体的log搜索复杂度。

5.数据插入算法

由于我们会构建一个Delaunay graph的近似(approximation),在构建算法(construction algorithm)细节上有很大的自由度。主要目标是:最小化false global minima的概率,并能保持links数目尽可能小。可以使用一些基于metric space拓朴的方法。例如,[13]中提出了构建近似Delaunay graph的方法:对于graph中的每个vertex所对应的一个固定数目的edges,通过最小化相应的Voronoi region的volume(通过monte-carlo法)的来构建。我们提出通过1-by-1的方式插入数据来生成该structure,并在每个step将它们相连接(使用在该sturcture中已经存在的f个closest objects)。我们的方法基于elements set(它们是Voronoi neighbors)和f个closest elements的交叉(intersection)。

该graph可以通过所有elements的顺序插入来构建。对于每个新进来的element,我们会从该sturcture中寻找与它相关的最近邻集合(Delaunay graph近似)。该set会与该element连接,反之即然。这种方法的一个优点是,使用general metric数据,以随机顺序到达的方式创建的一个graph,具有small word navigation特性,无需任何其它额外安排。

为了决定f个最近elements的集合,我们使用近似knn搜索算法(4.2节),该算法会具有三个参数:

  • object: 在该sturcture中被插入的element
  • f: 连接的最近邻数目,正整数
  • w: multi-searches的数目,正整数

首先,该算法决定了一个包含f个local closest elements的neighbors集合,它会使用K-NNSearch过程(4.2)节。在new_object之后,被连接到在set中的每个object,反之亦然。

图片名称

算法3

5.1 参数选择

参数w影响着在构建算法中最近邻的accurate的测定。如4.2节,将w设置到一个大数目,等价于在structure中最近elements的exhaustive search,产生一个perfect recall。该思想是,将w设得足够大,以便recall接近1 (比如:0.95-0.99)。recall越小会产生一部分wrong links,这会公增加算法复杂度,而我们的实验表明,在插入时增加超过0.99的recall,对于search quanlity没有重大效果。测试已经表明,对于最优的recall,w会随dataset size变化很慢(成log关系),因此如果我们已经知道,对于一个好的recall的近似,我们可以运行随机query tests,首先使用更大的m(比如:),假设:对于搜索结果为true k个最近邻来说,m足够大,那么,增加w,重复测试直到我们具有一个高的recall(例如:0.95-0.99)。操作复杂度与dataset size成log关系,因为它不会影响整个构建复杂度。

测试表明,对于Eucild数据(d=1,…, 20),对于connect(f)的neighbors的数目的最优值是3d,使得内存消耗与维度成线性关系。f的值越小,可以被用来减小single search的复杂度,满足它的recall quality。

6.结果与讨论

6.2 small world navigation特性

为了验证small world navigation特性,对于不同维度Euclidean spaces上的点(见图2),我们会通过greedy search算法来测量搜索的平均path length。f的值被设置成3d。该图很明显地表明,greedy search的path length与dataset size成log依赖,表明提出的structure是一个navigable small word。注意,对于更高维度的依赖是更弱的。这不能归因于f的不同值,但可能是因为“拓朴直径”的减小。当greedy算法遇到long range links,它会选择该方向上与query接近的elements,并忽略其它方向,使得搜索准一维(quasi-one-dimensional)。

如果我们添加elements可以保证扩展set的volume(例如:非随机插入)、或者更新elements的links(删除那些不与任一最近f个elements相连的links),那么log复杂度会降低。这些事实表明,naivgable small world特性是基于Delaunay近似links的long-range links的(它在构建的开始被创建)。

图片名称 图2

参考

Approximate nearest neighbor algorithm based on navigable small world graphs

baidu Query-Ad Matching算法介绍

baidu在《MOBIUS: Towards the Next Generation of Query-Ad Matching in Baidu’s Sponsored Search》介绍了它们的query-ad matching策略。# 摘要为了构建一个高效的竞价搜索引擎...… Continue reading

PAL position bias介绍

Published on February 25, 2020

facebook DLRM介绍

Published on November 01, 2019