Yu. A. Malkov等人在paper《Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs》中提出了HNSW,我们来看下:

介绍

随着信息资源的快速增长,在可扩展和高效相似搜索数据结构方面的需求越来越大。信息搜索的一种常用方法是:K-Nearest Neighbor Search(K-NNS)。K-NNS假设你具有一个已定义好的关于数据元素之间的距离函数(distance function),目标是:为一个query从数据集中寻找K个具有最小distance的elements。在许多应用中使用这样的算法,比如:非参数化机器学习算法、大规模数据集中的图片特征匹配、语义文档检索。K-NNS的一种naive方法是:计算query与数据集中的每个element的距离,并选择具有最小距离的elements。不幸的是,naive方法的复杂度与所存储的elements的总数是成线性增长的,这使得它在大规模数据集上是不可行的。因而,需要开发更快、可扩展的K-NNS算法。

由于“维数灾难”,当只有考虑相对低维的数据时,K-NNS的exact方法可以提供一个较大的搜索加速。为了克服该问题,提出了近似最近邻搜索(Approximate Nearest Neighbors Search (K-ANNS) ),它允许存在一小部分的错误(errors),从而放宽exact search的条件。inexact search(recall)的质量被定义成(true NN数目/K数目)的比值。最流行的K-ANNS解法有:基于树的近似版本[6,7]、LSH[8,9]、以及PQ(乘积量化:product quantization)[10-17]。在高维数据集上,邻近图K-ANNS算法由于良好的表现最近变得流行起来。然而,在低维或聚类数据上,邻近图路由(proximity graph routing)的幂律扩展(power-law scaling)会造成严重性能下降。

在本paper中,我们提出了Hierarchical Navigable Small World(Hierarchical NSW, HNSW),一种基于增量K-ANNS结构的新的完全图,可以提供更好的对数复杂度扩展(logarithmic complexity)。主要贡献有:

  • 图的入点节点(enter-point node)的显式选取(explicit selection)
  • 通过不同尺度(scales)将连接(links)进行分离
  • 使用一个高级的启发法(heuristic)来选择neighbors

可选的,HNSW算法可以被看成是一种使用邻近图(proximity graphs,而非链表)的概率型跳表结构(probabilistic skip list structure)的扩展。效果评估表明,针对常用指标空间(general metric space)提出的该方法,效果要好于只应用于向量空间的state-of-the-art方法。

2.相关工作

2.1 近似图技术

图算法的大多数研究中,搜索(searching)会采用在kNN graphs中的贪婪路由(greedy routing)的形式。对于一个给定的邻近图(proximity graph),我们会从某些enter point(可以随机、或者由一个独立算法提供)上开始搜索,并迭代遍历该graph。在遍历的每个step上,算法会检索query和当前base node的neighbors间的距离,接着选择可以最小化该距离的adjacent node作为下一个base node,并可以继续跟踪最好的已发现neighbors。当满足一些停止条件时(比如:距离计算的数目),该search会终止。链接到一个k-NN graph中最近的neighbors,作为Delaunay graph(它可以保证一个基础的贪婪图遍历的结果总会是最近邻)的一个简单近似。不幸的是,如果没有先验信息,Delaunay graph不能被有效构建,但可以通过只使用在所存elements间的距离来得到最近邻从而进行近似。结果表明,使用这样的近似的邻近图(proximity graph)方法,效果完全要好于其它k-ANNS技术(比如:kd-trees和LSH)

k-NN graph方法的主要缺点有:

  • 1) 在routing过程期间,steps的数目与dataset size成幂律(power law)比例
  • 2) 全局连通(global connectivity)的一个可能loss,在聚类数据上会导致很差的搜索结果。

为了克服这些问题,提出了许多混合方法,它们使用只适用于vector data的辅助算法(auxiliary algorithms),通过一个粗粒度搜索(coarse search),来为enter point寻找更好的candidates。

在[25,26,30]中,作者提出了称为NSW(Navigable Small World)一个邻近图K-ANNS算法(也称为MSW: Metricized Small World),它使用可导航图(navibable graphs)(比如:在贪婪遍历期间,hops数与network size成对数或多重对数比例)。NSW graph通过以随机顺序的方式连续插入元素,将它们与M个最近的neighbors(来自之前插入元素)进行双向连接。M个最近neighbors可以使用该结构的搜索过程被找到。到该elements最近neighbors的连接(links)会在构建开始时插入,并在network hubs间进行桥接(bridges),从而保持全图连通性,并允许在greedy routing期间,hops数成对数比例扩展。

NSW structure的构建阶段可以通过高效并行化,无需全局同步(global synchronization)以及在accuracy上的没有影响,对于分布式搜索系统是一个好的选择。NSW方法在一些datasets上能达到SOTA的效果,然而,由于整体的多项对数复杂度扩展(polylogarithmic complexity scaling),该算法仍被证实在一些低维数据集上效果会下降(在这些数据集上,NSW会输给tree-based算法)。

2.2 NSW模型

关于greedy graph routing成对数和多重对数比例的networks被称为:NSW networks。这样的networks是复杂网络理论中一个重要主题,目标是理解真实网络信息中的底层机制,以便将它们用于scalable routing和distributed similarity search。

第一项工作是,paper[34]的navigable networks的spatial models作为社交网络模型,用于著名的米尔格拉姆实验。…

另一个知名的navigable networks是:scale-free models,它可以复制真实网络的一些特性,可用于routing应用[35]。…

上述的NSW算法使用一个更简单的,之前未知的navigable networks模型,允许分散化图构建,很适合任意空间的数据。[44]中建议,NSW network的机制可以作为大规模神经网络的navigability:相似的模型可以描述small brain networks的增长,而模型会预测在大规模神经网络中观察到的high-level features。然而,NSW模型也会得到在routing过程中polylog的搜索复杂度。

3.动机

提升NSW搜索复杂度的方式,可以通过routing process的分析来标识,它在[32,44]中被研究。routing可以被划分成两个阶段:“缩小(zoom-out)”和 “放大(zoom-in)”。greedy算法在”zoom-out”阶段从一个低degree node开始遍历graph,同时node的degree会增加,直到该node links length的特征半径达到距离该query的scale。在后者发生之前,一个node的平均degree可以相对较小,这会产生一个停留在很远的(distant)false local minimum上的递增概率。

你可以在NSW上避免上述问题,它从一个具有最大degree的node(好的candidates是那些插入到NSW结构中的first nodes)开启搜索,直接到该搜索的”zoom-in”阶段。测试表明,该setting中心会像起始点一样,实质增加成功在结构内路由的概率,并能在低维数据上提供更好的性能。然而,在单个greedy search上它仍只有一个多项式复杂度的扩展,对比起Hierarchical NSW它在高维数据上表现更差。

在NSW中一个single greedy search的多项式复杂度扩展(polylog scaling)的原因是:距离计算(distance computation)的总数,与greedy算法的平均数目和greedy path上nodes的平均度跳数乘积成比例。hops scales的平均数目是对数扩展的,而在greedy path上的平均degree也是对数扩展的,因为:

  • 1) greedy search趋向于遍历和网络增长相同的hubs
  • 2) hub connections的平均数目会随网络size的增加而对数增长

因而,我们会获得关于结果复杂度的一个总多项式依存。

Hierarchical NSW算法的思想是:将links根据它们的length scale分离到不同的layers上,接着以multilayer graph的形式进行search。在该case中,我们只需为每个element评估一个固定数目的connections(独立于networks size),从而允许一个log scalability。在这样的structure中,搜索会从upper layer开始(它具有最长的links)(即:“zoom-in”阶段)。该算法会贪婪地遍历upper layer中的elements,直到到达一个local minimum(见图1的演示)。接着,该search会切换到lower layer(它具有更短的links);然后从在前一layer上具有local minimum的element进行restart,并重复该过程。在所有layers中的每个element上的connections的最大数目是常量,这样可以允许在NSW网络路由中进行一个log scaling复杂度。

图片名称

图1 HNSW思想的图解。search会从top layer的一个element开始(红色部分)。红色箭头表示greedy算法的方向,从entry point到该query(绿色部分)

生成这样一个分层结构(layered structure)的一种方式是:通过引入layers,使用不同length scales来显式设置links。对于每一个element,我们会选择一个整数level l:它定义了该element所属layer的最大layer。对于在一个layer中的所有elements,会增量构建一个邻近图(proximity graph)(例如:graph只包含”short” links,它近似于Delaunay graph)。如果我们设置一个关于l的指数衰减概率(例如:根据一个几何分布),我们会获得在该structure中layers的期望数目的一个log scaling。该search过程是一个迭代式greedy search:它从top layer开始,在zero layer完成。

当我们合并来自所有layers的connections时,该structure变得与NSW graph相似(在该case中,可以被放置的l相当于在NSW中的node degree)。对比NSW,HNSW构建算法不需要在插入前进行shuffle——因为它的随机化(stochasticity)可以使用level randomization来达到,从而真正允许增量索引(incremental indexing),即使数据分布随时间变化(尽管插入顺序的轻微变更会影响效果,这是因为只有部分determenistic construction过程)。

HNSW的思想与著名的1D概率跳表结构非常相似,可以使用它的术语进行描述。与skip list的主要不同是:我们可以通过使用proximity graphs替代linked list来生成结构。HNSW方法可以使用相同的方式来做出分布式近似搜索/重叠结构(distributed approximate search/overlay structures)。

对于element insertion期间邻近图的connections的选择,我们会利用一个启发法:它会考虑上候选elements间的距离,来创建不同的(diverse)connections(在SA-tree中使用相似的算法来选择tree children),而非只选择最近的neighbors。该启发法会从nearest element开始检查candidates(相对于插入的element);只有当该candidate比base element(已插入)更接近时(对比起任意已经连接的candidates),会创建到该candidatate的一个connection(详见第4节)。

当候选数目足够大时,该启发法允许获得exact relative neighborhood graph(精准的亲属邻居图)作为一个subgraph,通过只使用nodes间的距离来得到Delaunay graph的一个最小subgraph。relative neighborhood graph很轻易地保持全局连接的component,即使在高度聚类数据中(见图2)。注意,对比起exact relative neighborhood graph,启发法会创建额外edges,允许控制connections数目,这对于搜索性能很重要。对于1D数据的case,通过只使用与elements间距离相关的信息,启发法允许获得exact Delaunay subgraph,这使得从HNSW到1D probalilistic skip list算法有一个直接转换。

图片名称

图2 为两个孤立clusters选择graph heighbors所使用的heuristic启发法。一个新的element会被插入到Cluster 1的边界上。该element的所有最近邻都会属于Cluster 1, 从而忽略在clusters间的Delaunay graph的edges。当插入的element最接近时,对比起Cluster 1的其它element,该heuristic会从Cluster 2选择element ,来保持全局连通

HNSW proximity graph的基础变种也在[18]中被使用,对于proximity graph searching被称为“sparse neighborhood graph”。相似的启发法也是FANNG算法的一个关注点。

4.算法描述

网络构建算法(算法1)通过连续插入存储的elements到graph结构中来进行组织。对于每个插入的element,会随机选中一个integer maximum layer l,并使用一个指数衰减概率分布(通过参数归一化,详见算法1的第4行)。(说明:element更容易落到较高level上)

图片名称

算法1:

input:

  • hnsw: multilayer graph
  • q: 新的element
  • M: 已确立的connections数目
  • :每个payer上每个element的最大connections数目
  • efConstruction:动态候选列表(danamic candidate list)的size
  • :level generation的归一化因子

输出:

  • 插入element q更新后的hnsw

整个插入过程如下:

  • 1.插入过程的第一阶段:从top layer开始,并贪婪地遍历该graph,以便在该layer上找到与插入的element q最近的ef个neighbors
  • 2.之后,该算法从下一layer继续搜索,使用从前一layer已发现最近的neighbors作为enter points,重复该过程。

在每个layer中,最近的neighbors会被算法2(greedy search算法的一个变种,它是[26]算法的一个更新版本)所发现。为了在一些layer 上获得近似的ef个最近的neighbors,会在搜索期间维护一个关于ef个已发现最近的elements(在enter points初始填充)动态列表W。该list会在每个step被更新:通过评估在list中之前未评估的最近的element的neighborhood,直到list中的每个element的neighborhood被评估。对比起限制distance计算的数目,HNSW的停止条件具有一个优点——它允许抛弃用于评估的candidates,从而避免搜索结构的膨胀。正如在NSW中,该list会通过两个优先级队列进行仿真来追求更好性能。与NSW的区别在于:

  • 1)enter point是一个固定参数
  • 2) 作为更换multi-searches的数目的替代,搜索质量会通过一个不同参数ef来搜索(它在NSW中被设为K)

图片名称

算法2

在搜索的第一阶段,ef参数被设置为1(简单贪婪搜索),以避免引入额外参数。

当搜索达到layer no.<=l的layer时,构建算法的第二阶段会被初始化。第二阶段在两点上有不同:

  • 1) ef参数会从1增加到efConstruction,以便控制greedy search过程的recall
  • 2) 在每一layer上,已发现的最近的neighbors也会被作为candidates,用于inserted element的connections

图片名称

算法3

从candidates中选择M个neighbors有两个方法可以考虑:

  • 简单法:到最接近的elements的简单连接(算法3),
  • 启发法:会考虑上candidate elements间距离,用来创建不同方向(diverse directions)的连接(算法4)。如第3节

图片名称

算法4

该heuristic具有两个额外参数:

  • extendCandidates:(缺省为false),它会扩展candidate set,只对极度聚集的数据有用
  • keepPrunedConnections:允许每个element具有固定数目的connection

当被插入的elements的connections在zero layer被确立时,插入过程终止。

在HNSW中所使用的这种K-ANNS search算法如算法5所示。它大致等价于对于layer l=0的一个item的插入算法。不同之处是,在ground layer发现的最接近的neighbors(被当成candidates用于connections)会随搜索结果返回。搜索质量通过ef参数控制(对应于construction算法的efConstruction)。

图片名称

算法5

4.1 construction参数的影响

construction参数会负责维护在所构建graphs的small world navigability。将设置为0、并且将设置为M会生成directed k-NN graphs,它具有幂律(power-law)的搜索复杂度。将设置为0、并且将设置为无穷大会导致生成NSW graphs,它具有polylog的复杂度。最终,将设置成非零值,会产生受控的hierarchy graphs,它通过引入layers允许log搜索复杂度。

为了达到最优的效果,不同layers上的neighbors间的overlap必须很小。为了减小overlap,我们必须减小。然而,同时,减小会产生在每层上的greedy search的平均hop数的增加,这会对效果产生负面影响。这会导致参数最优值的存在。

关于最优的,一种简单选择是1/ln(M),这对应于skip list参数,层间的overlap具有一个平均single element。在Intel Core i& 5930K CPU上模拟得到,的选择是个合理选项(见图3,在10M随机数据, d=4的vectors)。另外,该图展示了使用选择connections的heuristic,在低维数据上,当将从0开始增加时会有一个大的加速,

4.2 复杂度分析

5.性能评估

HNSW算法通过nmslib c++实现,它是一个功能性NSW实现。由于该library的限制,为了达到一个更好的性能,HNSW实现使用定制的距离函数以及C-style的内存管理,这避免了不必要的隐式寻址,并允许在图遍历时进行高效的硬件/软件prefetching。

5.1 与base NSW的对比

5.2 欧氏空间中的对比

5.3 在general spaces上的对比

5.4 使用PQ的对比

参考

https://arxiv.org/pdf/1603.09320.pdf

1.介绍

计算高维向量间的欧氏距离,在许多应用中是一个基本需求。尤其是最近邻搜索问题中被广泛使用。由于维度灾难,最近邻搜索相当昂贵。在D维欧氏空间上,该问题是:在一个n维vectors的有限集合,寻找element ,可以最小化与query vector 间的距离:

…(1)

许多多维索引方法,比如KD-tree或其它branch&bound技术,被提出来减小搜索时间。然而,对于高维空间,发现这样的方法比起brute-force距离计算(复杂度O(nD))并没有更高效多少

一些算法文献通过执行ANN(近似最近邻)搜索来解决该问题。这些算法的关键点是:”只”寻找具有较高概率的NN,来替代概率1. 大多数研究都在欧氏距离上,尽量最近有研究在其它metrics上提出[10]。在本paper中,我们只考虑欧氏距离,它可以适用于许多应用。在本case中,一个最流行的ANN算法是欧氏局部敏感哈希算法(E2LSH),它在有限假设的搜索质量上提供了理论保证。它已经被成功用于local descriptors和3D object indexing。然而,对于真实数据,LSH还是通过启发法来执行,会利用vectors的分布。这些方法包括:randomized KD-trees、hierarchical k-means,这两种方法在FLANN选择算法上有实现。

ANN通常会基于search quality和efficiency间的trade-off来进行比较。然而,该trade-off并不能说明indexing结构的内存需要。在E2LSH的case上,内存的使用要比original vectors更高。另外,E2LSH和FLANN需要基于exact L2距离(如果访问速度很重要,它需要在主存中存储indexed vectros)来执行一个final re-ranking step。该constraint会严重限制可被这些算法处理的vectors的数目。最近,研究者们提出了受限内存使用的方法。该问题的关键是涉及大量数据,例如:在大规模场景识别[17]中,需要索引数百万到数十亿的图片。[17]中通过单个global GIST descriptor来表示一个图片,该descriptor可以被映射到一个short binary code上。当使用无监督时,会学到这样的mapping,以便在embedded space中由hamming距离定义的neighborhood可以影响在原features的欧氏空间中的neighborhood。欧氏最近邻的搜索接着被近似成:通过codes间的hamming距离的最近邻搜索。在[19]中,spectral hashing(SH)的效果要好于由RBM、boosting和LSH生成的binary codes。相似的,Hamming embedding方法[20]会在Bag-of-features的图片搜索框架中使用一个binary signature来重新定义quantized SIFT或GIST descriptors。

在本paper中,我们使用quantization来构建short codes。目标是使用vector-to-centroid distances来估计距离,例如:query vector是没有被量化的(quantized),codes只被分配给database vectors。这会减小quantization noise,进而提升搜索质量。为了获得精确的距离,quantization error必须被限制。因此,centroids的总数目k必须足够大

例如:对于64-bit codes使用。这会抛出一些问题:如何学到密码本(codebook)以及分配一个vector?

  • 首先,要学到该quantizer所需的样本量很大,比如:k的许多倍。
  • 第二,该算法本身的复杂度很高。
  • 最后,地球上的计算机内存量不足以存储表示centroids的floating point。

hierarchical k-means(HKM)提升了learning stage、以及assignment过程的efficiency。然而,前面提到的限制仍存在,特别是:内存使用以及learning set的size。另一个可能是scalar quantizers,但他们提供了更差的quantization error特性。对于均匀向量分布,lattice quantizers提供了更好的quantization特性,但该条件在现实vectors中很难满足。特别的,这些quantizers执行在indexing任务上要比k-means更差。在本paper中,我们只关注product quantizers。据我们所知,这样的semi-structured quantizer从没有在任何最近邻搜索方法中考虑。

我们的方法有两个优点:

  • 首先,可能的distances的数目要比competing Hamming embedding方法要更高,因为在这些技术中使用的Hamming space只允许少量distinct distance。
  • 第二,作为byproduct方法,我们可以获得一个expected squared distance的估计,它对于e-radius搜索或者lowe’s distance ratio criterion来说是必需的。

在[20]使用Hamming space的动机是,高效计算距离。注意,然而,计算Hamming距离的最快方法之一,包含了使用table lookups。我们的方法会使用相同数目的table lookups,来产生相当的效率。

对于非常大的数据集,对所有codes与query vector进行遍历比较开销相当大。因此,引入一个modified inverted file结构来快速访问最相关vectors。会使用一个粗粒度量化器(coarse quantizer)来实现该inverted file结构。其中,对应于一个cluster(index)的vectors会被存储在一个相关列表中。在该list中的vectors通过short codes(通过product quantizer计算得来)来表示,被用于编码对应于聚类中心的其它vector。

我们的方法的关注点是:在两种vectors上进行验证,称为local SIFT和global GIST descriptors。通过SOTA对比,我们的方法要好于之前的技术(比如:SH, Hamming embedding以及FLANN)。

2.背景知识:quantization、product quantizer

关于vector quantization有大量文献提供。在本节,我们聚焦在相关概念上。

A. Vector quantization

Quantization是一个分解性过程(destructive process),它在信息论中被大量研究。它的目标是,减小representation space的基数(cardinality),特别是当输入数据是real-valued时。

正式的:一个quantizer是一个函数q,它将一个D维向量映射到vector q(x)上:

其中:

  • index set 是假设是有限的:
  • reproduction values :表示centroids
  • reproduction values C的集合:称为size k的codebook

vectors映射到一个给定index i上的集合,被称为一个(Voronoi) cell,定义为:

…(2)

一个quantizer的k个cells形成了的一个划分(partition)。通过定义可知:在同一cell 上的所有vectors,可以通过相同centroid 来构建。一个quantizer的quality通常通过input vector x和它的reproduction value 间的MSE来进行测量:

…(3)

其中,是x和y的欧氏距离,是随机变量X的概率分布函数。对于一个专门的概率分布函数,等式(3)数值上使用Monte-Carlo sampling进行计算,作为在一个大数据集样本上的平均。

为了让quantizer是最优的,必须满足L1oyd optimality condition的两个特性。

  • 1. vector x必须被quantized到它最近的codebook centroid,根据欧氏距离:

…(4)

作为结果,cells通过超参数来限定。

  • 2. 重构值(reconstruction value)必须是在Voronoi cell上vectors的期望值

…(5)

Lloy quantizer,它对应于k-means cluster算法,通过迭代式分配一个training set的vectors给centroids、并将这些已分配vectors的centroids进行re-estimating的方式来寻找一个接近最优的codebook

下面,我们会假设两个Lloyd conditions成立,正如我们使用k-means来学习该quantizer。注意,然而,k-means只会根据quantization error来找一个local optimum。

下面会使用到的另一个quantity是:当构建一个由通过相应的centroid 得到的cell 的vector时,获得的均方失真。通过来表示一个vector被分配给centroid 的概率,它可以通过下式计算:

…(6)

注意,MSE可以通过这些quantities来获得:

…(7)

存储index value(没有进一步处理(entropy coding))的内存开销,是 bits。因此,使用一个k的2阶很方法,因为通过quantizer生成的code以binary memory的方式生成。

B. Product quantizers

假设我们考虑一个128维的vector,例如,SIFT descriptor [23]。一个quantizer会产生64-bits codes,例如,每个component只有0.5 bit,包含了的centroids。因此,使用Lloyd算法或HKM并不重要,因为所需的样本数据、以及学习该quantizer的复杂度是:k的数倍。为了表示k个centroids要存储的floating point值是不可能的

product quantization是一个高效的解决该问题的解法。它是source coding中的常用技术,允许选择要进行联合量化(quantized jointly)的components的数目(例如,24个components的groups可以使用强大的Leech lattice来量化)。

input vector x被split成m个不同的subvectors ,维度为,其中D是m的倍数。这些subvectors会使用m个不同的quantizers进行单独量化。一个给定vector x因此根据如下进行映射:

…(8)

其中:

  • 是低复杂度的quantizer,它与第j个subvector有关。
  • subquantizer 与index set 、codebook 、以及相应的reproduction values 有关。

product quantizer的reproduction通过product index set 的一个element进行标识。codebook因此被定义成Cartesian product:

…(9)

以及该set的centroid是m个subquantizers的centroid的拼接(concatenation)。从现在开始,我们假设,所有subquantizers具有相同的有限数目的reproduction values。在该case中,centroids的总数由下式给定:

…(10)

注意:在极端情况下(m=D),一个vector x的所有components是被完全独立量化的。这时,product quantizer就变成了一个scalar quantizer。其中,与每个component有关的quantization function是不同的。

一个product quantizer的力量是:使用多个centroids的小集合(它们与subquantizers有关)来生成一个更大的centroids集合。当使用Lloyd算法学习该subquantizers时,会使用有限数目的vectors,在某种程度上,codebook仍会采用数据分布来表示。学习该quantizer的复杂度为: m X 对个具有的centroids执行k-means聚类的复杂度。

对codebook C显式存储效率不高。相反,我们会存储所有subquantizer的个centroids,例如:个floating points值。对一个element进行量化需要个floating point操作。表1总结了与k-means、HKM、product k-means对应所需的资源。product quantizer很明显是唯一可以被用于当k为大值时可以进行内存索引的方法。

图片名称

表1

当选择一个常数值,为了提供较好的量化属性,通常每个subvector都应具有一个可对比的energy。确保该特性的一个方法是:通过将该vector乘以一个随机正交矩阵来进行quantization。然而,对于大多数vector types,这并不是必需的,也不推荐,因为连续的components通常通过construction来关联,并可以更好地与相同的subquantizer一起被量化。由于subspaces是正交的,与product quantizer的平方失真(squared distortion)为:

…(11)

其中,是与quantizer 相关的失真(distortion)。图1展示了MSE是一个关于不同tuples的code length的函数,其中code length为,如果是2的幂。该曲线通过一个128维SIFT descriptors的集合获得,详见第V部分。你可以观察到,对于固定数目的bits,最好使用一个小数目的subquantizers以及更多centroids,要比使用许多subquantizers和更少centroids的要好。当m=1的极端情况下,product quantizer会成为一个常规的k-means codebook。

图片名称

图1

的值越高,会增加quantizer的计算开销,如表1所示。它们也会增加存储centroids()的内存使用量,当centroid look-up table不再fit cache内存时,这会进一步降低效率。在这种情况下m=1,超过16 bits来保存这样的开销可追踪将承受不起。使用通常是一个合理的选择。

3.使用quantization进行搜索

最近邻搜索依赖于query vector与database vectors间的distances,或者squared distances。这节引入的方法会使用source coding技术的精髓,基于quantization indices的vectors进行比较。我们首先解释了被用于计算distances的product quantizer性质。接着我们提供了一个在distance estimation error上的统计边界,并提出了一个refined estimator来计算squared Euclidean distance。

A.使用quantized codes来计算distances

假设我们考虑query vector x和database vector y。我们提出两种方法来计算它们间的近似欧氏距离:对称法(symmetric)和非对称法(asymmetric)。见图2.

图片名称

图2 sym和asym的距离计算。对于左图,距离d(x,y)通过d(q(x),q(y))来估计;对于右图,距离d(x,y)通过d(x,q(y))来估计。通常,距离上的MSE受限于quantization error

SDC(Symmetric distance computation)

vectors x和y通过它们各自的centroids q(x)和q(y)来表示。距离d(x,y)通过近似,它使用一个product quantizer来高效获取:

…(12)

其中,是从一个与第j个subquantizer相关的lookup table中读取。每个lookup table包含了centroids pairs 间所有的squared distances,或者的squared distances。

ADC(Asymmetric distance computa)

database vector y通过q(y)表示,但query x不会被编码。距离d(x,y)通过来近似,它使用decomposition进行计算:

…(13)

其中:

  • squared distances: 是在search之前计算好的

对于最近邻搜索,我们在实际中不会计算均方根(square roots):square root函数是单调递增的,squared distances会生成相同的vector ranking。

表II总结了涉及到vector x与dataset Y中搜索k个最近邻的不同steps的复杂度。可以看到,SDC和ADC具有相同的query准备开销,它不依赖于dataset size n。当n很大时(), 大多数开销操作是公式12和等式13的求和。对于搜索k个最小elements在该表中的复杂度为:当elements是任意顺序时,对于的平均复杂度。

图片名称

表2

SDC比ADC好的一个优点是:限制与queries相关的内存使用量,因为query vector通过一个code定义。这在大多数情况没啥太大意义,因而你可以使用一个asym版本,它对于一个相似复杂度可以获得一个更低distance distortion。后续部分我们主要关注ADC。

4.非穷举搜索(non-exhaustive search)

使用PQ的最近邻搜索很快(对于每个距离计算,只需要m个加法),并且可以极大减小内存需求。另外,该search是穷举(exhaustive)的。该方法在global image description的内容上仍然是可扩展的。然而,如果每张图片通过一个local descriptors集合描述,穷举搜索是禁止的,因为我们需要检索数十亿descriptors并执行多个queries

为了避免穷举搜索,我们会组合一个IVF系统(inverted file system),并使用asynmmetric distance computation(IVFADC)。一个inverted file会对对descriptors进行量化,并在相应的lists中存储图片索引,见图5的“coarse quantizer”。这会允许快速访问图片索引的一小片,这对于非常大规模的搜索是很成功的[26]。除了只存储图片索引外,我们会为每个descriptor添加一个small code,这在[20]中首次这样做。这里,我们会使用一个product quantizer来对vector和它相应的coarse centroid间的不同之处进行编码,见图5。该方法可以极大加速search,每个descriptor只需很少的额外bits/bytes开销。再者,它对search accuracy的提升很微小,因为对残差(residual)进行编码要比对vector自身编码更精准。

图片名称

图5

A.Coarse quantizer,局部定义了product quantizer

与“Video-Google”[26]方法相似,通过使用k-means学到一个codebook,这会带来一个quantizer ,被称为“coarse quantizer”。对于SIFT descriptors,与相关的centroids数目为,通常范围为k’=1000 ~ 1,000,000。对比在第3节中使用的product quantizers的k来说较小些。

除了coarse quantizer外,我们会采用一个与[20]提出的相似的strategy,例如,一个vector的description通过一个code(由一个product quantizer获得)重定义。然而,为了解释由coarse quantizer提供的信息,例如,centroid 与一个vector y相关,product quantizer 被用于编码residual vector:

…(28)

对应于在Voronoi cell中的offset。对比vector自身,residual vector的energy很小。该vector通过下式近似:

…(29)

它通过tuple 表示。通过与“二进制表示”类比发现,coarse quantizer提供了最高有效位(most significant bits),而product quantizer的code相当于最低有效位(least significant bits)。

d(x,y)的估计值(其中x是query,y是database vector),可以通过x和间的距离 对比:

…(30)

通过定义了第j个subquantizer,我们使用以下decomposition来有效计算该estimator:

…(31)

与ADC的做法相类似,对于每个subquantizer ,在partial residual vector 所有centroids 间的距离是预先计算好并进行存储好的。

在residual vectors集合上学到的product quantizer通过一个learning set收集到。尽管该vectors被coasrse quantizer量化到不同indexes上,生成的residual vectors被用于学习一个唯一的product quantizer。我们假设:当在所有Voronoi cell上的residual的分布是边缘的时,相同的product quantizer是精准的。这可能会为该方法给出差的结果(该方法包含了learning,并为每个Voronoi cell使用一个不同的product quantizer)。然而,这在计算上开销很大,需要存储个product quantizer codebooks,例如:的浮点值,它对于的公共值来说内存过大(memory-intractable)。

B. indexing结构

我们使用coarse quantizer来实现一个inverted file结构作为一个lists数组: 。如果是到index的vector dataset,与的centroid 相关的list ,会存储集合

在inverted list ,一个entry对应于y,包含了一个vector identifier以及被编码的residual

图片名称

表3

由于intered file结构,identifier字段是overhead。依赖于要存储的vectors的特性,identifier不必是唯一的。例如,为了通过local descriptors来描述图片,image identifiers可以替代vector identifiers,例如,所有相同图片的vectors具有相同的identifier。因此,一个20-bit field足够标识来自100w数据集中的一个图片。该内存开销可以使用index压缩进一步减小,它可以将存储该identifier平均开销减小到8bits,取决于参数。注意,一些几何信息可以被插入到该entry中,如[20]中提出的。

C. Search算法

该inverted file是非穷举(non-exhaustive)版本的核心。当搜索一个vector x的最近邻时,inverted file提供了Y的一个子集,用于估计距离:只对应的inverted list 会被扫到。

然而,x和它的最邻近并没有被量化到相同的centroid上,而是在附近一个centroid上。为了解决该问题,我们使用多个assignment策略[29]。该query x会被分配到w个indexes上(而非单个),它对应于在的codebook中x的w个最近邻。所有相应的inverted lists都会被扫描到。多个assignment不会被应用到database vectors,因为这将增加内存使用。

图5给出了一个关于一个database是如何被index和search的总览。

Indexing一个vector y的过程

  • 1) 将y量化到
  • 2) 计算residual:
  • 3) 将量化到,对于product quantizer来说,相当于将分配给,其中
  • 4) 添加一个new entry到对应的inverted list中。它包含了vector (或image) identifier以及binary code(product quantizer的indexes)。

Searching

一个query x的最近邻包含了:

  • 1) 将x量化到在codebook 中的w个最近邻。为了简明,在下两个step,我们会通过将r(x)表示与w assignments相关的residuals。这两steps会被应用到所有的w assignments中。
  • 2) 对于每个subquantizer j和每个centroid ,计算squared distance
  • 3) 计算在r(x)间的squared distance,以及inverted list的所有indexed vectors。使用在前一step计算的subvector-to-centroid distances,这包含了对m个looked-up values求和;
  • 4) 基于estimated distances选择x的K个最近邻。这可以通过维护一个固定容量的Maxheap结构来高效实现,它可以存储K个最小值。在每次距离计算后,只有point identifier被添加到该结构,如果它的距离在Maxheap的最大距离之下。

只有step 3依赖于database size。通过与ADC进行对比,将x量化到的求和step 包含了在D维vectors间计算个距离。假设inverted lists是balanced,那么需要解析个entries。因此,search要比ADC更快,下一节将介绍。

5. NN Search的评估

分析SDC、ADC、IVFADC的参数影响。我们的方法会对比三个SOTA方法:spectral hashing、hamming embedding、FLANN。最终评估复杂度和加速。

参考

faiss中有IVF的概念。其实就是inverted file (IVF)。它在2003的《Video Google: A Text Retrieval Approach to Object Matching in Videos》中提出。我们来看下,该paper有两段提及,我们来看下:

一、

文本检索系统通常需要采用一些标准steps。文档首先被解析成words。接着,words通过它们的stems来表示,例如:“walk”、”walking”、”walks”会使用stem ‘walk’来表示。第三,会使用stop list来拒绝常用words,比如:”the”、”an”,它们很常见。剩余words接着会被分配一个唯一的id,每个document会通过一个vector来表示,该vector的components由该文档中所包含的words的词频组成。除了components会以多种方式加权外,在google的case中,一个web page的weighting取决于web pages链接到特定页的数目。上述所有steps都在实际检索前完成,在语料中的所有文档会表示成vectors集合,通过一个inverted file进行组织来更高效的检索。一个inverted file的结构类似于一个理想的book index。在corpus中每个word都有一个entry,它会跟一个该word出现的所有文档(以及在该文档中的位置)的list。

一个text会通过计算词频向量进行检索,并返回最近向量(通过角度)的文档。

二、目标检索(object retrieval)

实现-使用inverted files:在一个经典的文件结构中,所有words会存储在它们出现的文档中。一个inverted file结构,会为每个word生成一个entry(hit list),并存储在所有文档中该word的出现次数。在我们的case中,inverted file会为每个可视化的word生成一个entry,它会存储所有matches,例如:在所有帧中相同word的出现次数。document vector是非常稀疏的,使用一个inverted file可以使得检索非常快。在2GHz的pentium上使用matlab实现,查询一个4k frames的database只需要0.1秒。

三、faiss IVF

上面提到的都是IR中的inverted file。关于faiss IVF,Chris McCormick在它的blog中有提到,我们可以看下:

Inverted File Index(IVF) 是pre-filtering技术,以便你无需对所有vectors做exhaustive search。实现相当简单:首先,你使用聚类(比如:kmeans)将数据集聚类生成较大数目(比如:100个)的数据分区(partitions)。接着,在query时,你会将你的query vector与partition centroids进行对比,(例如:找到10个最近的聚类),接着你只在这些分区上对vectors进行搜索

在IR中,”inverted index”指的是文本搜索索引,它会将词汇表中的每个词映射到数据文档中的所有位置。看起来有点像textbook的索引,将words映射到page numbers,因而称为inverted index。

然而,在我们的上下文中,该技术的意思是,使用k-means聚类将数据集进行划分,以便你可以重定义你的搜索(只需搜索部分分区,忽略其它)。

在构建index时,使用聚类将数据集聚到多个partitions上。在dataset中的每个vector会属于这些clusters/partitions的其中之一。对于每个partition,你都具有一个属于它的所有vectors的list(被称为:inverted file lists)。你具有关于所有这些partition centroids的一个matrix,它会被用于找出哪些partitions会进行search。

按这种方式划分数据集并不完美,因为如果一个query vector落到离它最近cluster的外面,那么它的最近邻很可能停留在多个附近的cluster上。解决该问题的简单方法是,搜索多个partitions。搜索多个附近的partitions很明显会花费更多时间,但它会给出更好的accuracy。

在搜索时,你可以比较你的query vector与所有partition centroids来找到离它最近的partition。可以配置多少个。一旦你发现了这些centroids,你只需从这些partitions中选择dataset vectors,使用product quantizer来进行KNN search。

需要注意一些术语:

  • verb “probe”指的是,选择partitions进行search。代码中你会看到index参数”nprobe”意味着:有多少partitions进行probe。
  • Faiss的作者喜欢使用术语:Voronoi cells(而非“dataset partitions”)。一个Voronoi cell指的是,属于一个cluster的space区域。也就是说,它会包含在space中的所有points(vector与某个cluster的centroid会比其它clusters更接近)。

4.faiss doc上的解释

Inverted list objects & scanners

faiss实现了two low-level APIs来泛化inverted list存储。这对于以key-value数据库存储lists很有用。

  • InvertedLists抽象类定义了inverted lists是如何从搜索代码被访问的。任意提供该interface的对象可以被用来保存lists。
  • InvertedListsScanner提供了细粒度的访问,因为scanning function可以在用户提供的id和code tables上被调用

4.1 IndexIVF回顾

IndexIVF类(以及它的子类)可以被被用于Faiss的所有大规模应用中。它会将input vectors聚类成nlist个groups(nlist是IndexIVF的一个field)。在add时,一个vector会被分配一个groups。在search时,与query vector最相似的groups会被识别出,并进行穷举扫描(exhaustively scan)。

因而,IndexIVF具有两个components:

  • quantizer(也称为:coarse quantizer)index。给定一个vector,quantizer index的search function会返回该vector所属的group。当使用nprobe>1的结果进行search时,它会返回与query vector最接近的nprobe个groups(nprobe是IndexIVF的一个field)。
  • InvertedLists对象。该object会将一个group id()映射到一个(code, id) pairs序列上.

4.2 InvertedLists对象

  • Codes:指的是一个常量size(code_size)的byte strings。例如,36维的IndexIVFFlat具有的code_size=36 * sizeof(float) = 144 bytes。
  • Ids:64-bit integer(负值是保留的,因此有用位只有63bits)

实际上,codes和ids会以两个独立的arrays返回,因为一些applications只需要其中之一,并且memory alignement是不同的。

4.2.1 search方法

该object有有三个相关的方法:

/// get the size of a list
size_t list_size(size_t list_no);

/// @return codes    size list_size * code_size
const uint8_t * get_codes (size_t list_no);
void release_codes (const uint8_t *codes) const;

/// @return ids      size list_size
const idx_t * get_ids (size_t list_no);
void release_ids (const idx_t *ids) const;

通过get_codes(以及get_ids)获得的指针需要通过release_codes(以及release_ids)来释放。如果你喜欢RAII,InvertedLists::ScopedCodes(以及InvertedLists::ScopedIds)会有用。

有一个额外的prefetch_lists方法,它会通过search方法被用来通知InvertedLists对象:一些inverted lists会在不久被用到。

因此,search过程的调用顺序如下:

search(v) {
    list_nos = quantizer->search(v, nprobe)
    invlists->prefetch(list_nos)
    foreach no in list_nos {
        codes = invlists->get_codes(no)
        // linear scan of codes
        // select most similar codes 
        ids = invlists->get_ids(no)
        // convert list indexes to ids
        invlists->release_ids(ids)
        invlists->release_codes(codes)
    }
}

4.2.2 add()方法

添加vectors需要有对InvertedLists对象的read-write权限。这通过add_entries方法提供。其它方法update_entries和resize被用于扩充(bulk)操作,比如,merging、 splitting、removing elements。

4.3 InvertedLists对象的行为

4.3.1 内存管理

如果own_invlists为true,InvertedLists对象通过IndexIVF的destructor被删除。缺省的,ArrayInvertedLists对象会在IndexIVF实例化时被构建,own_invlists被设置为true。缺省的invlists可以被replace_invlists所替代,用户必须决定所属关系(ownership)。

4.3.2 Threading

只读操作允许多线程访问。一些注释关于并发读写操作。

4.3.3 I/O

InvertedLists对象不需要和index object一起存储。如果不是这样,index object只包含处理外存(external storage)的所需信息。

4.4 Build-in InvertedLists类

InvertedLists类主要考虑可扩展性而设计。然而,在Faiss中有两个InvertedLists classes。

4.4.1 ArrayInvertedLists

这是一个std::vector<std::vector<…> >。这是最简单的in-RAM inverted lists实现,开销很少,add时间很快。它有一个特殊状态(status),因为当一个IndexIVF被构建时它会被自动实例化,因此这些vectors会被马上add。

4.4.2 OnDiskInvertedLists

该inverted list data被存储到磁盘的一个内存映射文件上(memory-mapped file)。会存在一个间接表(indirection table),它将list ids映射到file上的offset。 由于data是memory-mapped,没必要显式地从disk上取数据。然而,prefetch函数很有用,可以用上分布式文件系统的并发读。

有意思的是,通过将IO_FLAG_MMAP flag设置为read_index,一个“normal” IndexIVF可以被加载进一个OnDiskInvertedLists中。这使得它可以加载任意数目的indexes,无需担心是否满足RAM。

4.5 InvertedListScanner对象

Inverted list scanning可以在Faiss之外被控制。这使得没必要实现list访问函数作为回调,这不是惯例。

为了支持它,Faiss提供了:

  • encode_vector函数:它可以将inverted list codes计算成一个array中,用来放到不受faiss管理的inverted lists
  • InvertedListScanner对象:可以通过IndexIVF类获得。它会扫描lists、或计算单个query-to-code distance。

该访问非常low-level,但用户具有对scanning的total control,无需实现像InvertedLists对象的回调。

4.6 Encoding vectors

为了编码vectors,calling code应:

  • 对该vector进行quantize,来寻找要存到哪个inverted list
  • 调用encode_vectors来实际编码它

两个函数会进行batch操作以便提高效率。

以下是一个简化代码,它会将nb vectors存储到xb中,来定制inverted lists:

// size nb
idx_t *list_nos = ... ; 
// find inverted list numbers 
index_ivf.quantizer->assign (nb, xb, list_nos);

// size index->code_size * nb
uint8_t *codes = ...; 
// compute the codes to store
index->encode_vectors (nb, xb, list_nos, codes);

// populate the custom inverted lists 
for (idx_t i = 0; i < nb; i++) {
      idx_t list_no = list_nos[i]; 
      // allocate a new entry in the inverted list list_no
      // get a pointer to the new entry's id and code
      idx_t * id_ptr = ... 
      uint8_t * code_ptr =  ...
      // assume the vectors are numbered sequentially
      *id_ptr = i; 
      memcpy (code_ptr, codes + i * index->code_size, index->code_size);
}

详见test_lowlevel_ivf.cpp (add)

4.7 Searching

为了执行search,存在一些loop levels。

以下是执行query的简化代码。它会查询在index中np个vectors xq。

// size nprobe * nq
float * q_dis =  ...
idx_t *q_lists = ...
// perform quantization manually
index.quantizer->search (nq, xq, nprobe, q_dis, q_lists); 

// get a scanner object
scanner = index.get_InvertedListScanner();

// allocate result arrays (size k * nq), properly initialized
idx_t *I = ...
float *D = ...

// loop over queries
for (idx_t i = 0; i < nq; i++) {
    // set the current query
    scanner->set_query (xq + i * d);

    // loop over inverted lists for this query
    for (int j = 0; j < nprobe; j++) {
        // set the current inverted list
        int list_no = q_lists[i * nprobe + j];
        scanner->set_list (list_no, q_dis[i * nprobe + j]);

        // get the inverted list from somewhere
        long list_size = ...
        idx_t *ids = ....
        uint8_t *codes = ....
        // perform the scan, updating result lists
        scanner->scan_codes (list_size, codes, ids, D + i * k, I + i * k, k); 
   }
   // re-order heap in decreasing order
   maxheap_reorder (k, D + i * k, I + i * k);
}

参考

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

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

参考