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比例增长，即：

\[L \propto log\ N\]

其中，聚集度（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 \(q \in D\)（其中：D是所有可能对象的集合），我们需要从一个有限对象集合\(X \subseteq D\)中寻找k个最近的对象 \(P \subseteq X\)。两个对象\(o', o'' \in D\)的相近度或近似度可以定义成一个距离函数\(\delta(o', o'')\)。

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

我们的解法是：将数据结构表示成一个graph \(G(V,E)\)，其中来自X每个object \(o_i\)会与V中的一个顶点(vertex) \(v_i\)唯一关联。为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的分析有\(O(d^*N^{1-1/d})\)的复杂度，其中d是维度。

在[8]中提出了一个完全近邻搜索（exact-proximity search）结构，它使用Delaunay graph和greedy search算法。作者表示，在通用metric space中发现exact Delaunay graph是不可能的，为了保持search的exact，他依赖回溯（backtracking）。提出的数据结构在高维数据上的构建时间为\(O(n log^2n / log log n)\)、搜索时间为\(O(n^{1-\theta(1/log log n)})\)；在低维数据上为\(0 < \alpha < 1\)。

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

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

• 方法一：使用预定义的accuracy \(\epsilon(\epsilon-NNS)\)。它意味着，query和在结果中的任何element间的距离不超过\(1+\epsilon\) 乘以 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概率\(r^{-\gamma}\)遵循幂律的random long-range links，其中\(\gamma\)对应navigation，2维lattice对应用结果纠正。为了具有NSW特性，link length分布必须具有一个指定值\(\gamma\)。在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 \(v_i\)共享一个公共edge，被称为vertex \(v_i\)的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 \(V_{entry\_point} \in V[G]\)，它是一个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 \(q \in D\)都有一个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的近似\(w_0\)，我们可以运行随机query tests，首先使用更大的m（比如：\(m=2*w0 + 10\)），假设：对于搜索结果为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