1.介绍

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

…(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使用\(k=2^{64}\)。这会抛出一些问题：如何学到密码本（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维向量\(x \in R^D\)映射到vector q(x)上：

其中：

• index set \(I\)是假设是有限的：\(I=0, \cdots, k-1\)。
• reproduction values \(c_i\)：表示centroids。
• reproduction values C的集合：称为size k的codebook。

vectors映射到一个给定index i上的集合\(V_i\)，被称为一个(Voronoi) cell，定义为：

…(2)

一个quantizer的k个cells形成了\(R^D\)的一个划分（partition）。通过定义可知：在同一cell \(V_i\)上的所有vectors，可以通过相同centroid \(c_i\)来构建。一个quantizer的quality通常通过input vector x和它的reproduction value \(q(x)\)间的MSE来进行测量：

…(3)

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

为了让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 \(c_i\)得到的cell \(V_i\)的vector时，获得的均方失真\(e(q,c_i)\)。通过\(p_i=P(q(x)=c_i)\)来表示一个vector被分配给centroid \(c_i\)的概率，它可以通过下式计算：

…(6)

注意，MSE可以通过这些quantities来获得：

…(7)

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

B. Product quantizers

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

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

input vector x被split成m个不同的subvectors \(u_j, 1 \leq j \leq m\)，维度为\(D^* = D/m\)，其中D是m的倍数。这些subvectors会使用m个不同的quantizers进行单独量化。一个给定vector x因此根据如下进行映射：

…(8)

其中：

• \(q_j\)是低复杂度的quantizer，它与第j个subvector有关。
• subquantizer \(q_j\)与index set \(I_j\)、codebook \(C_j\)、以及相应的reproduction values \(c_j,i\)有关。

product quantizer的reproduction通过product index set \(I=I_1 \times \cdots \times I_m\)的一个element进行标识。codebook因此被定义成Cartesian product：

…(9)

以及该set的centroid是m个subquantizers的centroid的拼接（concatenation）。从现在开始，我们假设，所有subquantizers具有相同的有限数目\(k^*\)的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 对\(k^*\)个具有\(D^*\)的centroids执行k-means聚类的复杂度。

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

表1

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

…(11)

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

图1

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

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)通过\(d(x,y) \triangleq d(q(x), q(y))\)近似，它使用一个product quantizer来高效获取：

…(12)

其中，\(d(c_{j,i}, c_{j,i'})^2\)是从一个与第j个subquantizer相关的lookup table中读取。每个lookup table包含了centroids pairs \((i,i')\)间所有的squared distances，或者\((k^*)^2\)的squared distances。

ADC（Asymmetric distance computa）

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

…(13)

其中：

• squared distances： \(d(u_j(x), c_{j,i})^2: j=1 \cdots m, i= 1 \cdots k^*\)，是在search之前计算好的。

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

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

表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 \(q_c\)，被称为“coarse quantizer”。对于SIFT descriptors，与\(q_c\)相关的centroids数目为\(k'\)，通常范围为k’=1000 ~ 1,000,000。对比在第3节中使用的product quantizers的k来说较小些。

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

…(28)

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

…(29)

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

d(x,y)的估计值（其中x是query，y是database vector），可以通过x和\(\ddot{y}\)间的距离 \(\ddot{y}(x,y)\)对比：

…(30)

通过\(q_{p_j}\)定义了第j个subquantizer，我们使用以下decomposition来有效计算该estimator：

…(31)

与ADC的做法相类似，对于每个subquantizer \(q_{p_j}\)，在partial residual vector \(u_j(x-q_c(y))\)与\(q_{p_j}\)所有centroids \(c_{j,i}\)间的距离是预先计算好并进行存储好的。

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

B. indexing结构

我们使用coarse quantizer来实现一个inverted file结构作为一个lists数组： \(L_1 \cdots L_{k'}\)。如果\(y\)是到index的vector dataset，与\(q_c\)的centroid \(c_i\)相关的list \(L_i\)，会存储集合\(\lbrace y \in Y: q_c(y) = c_i \rbrace\)。

在inverted list \(L_i\)，一个entry对应于y，包含了一个vector identifier以及被编码的residual \(q_p(r(y))\)：

表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的一个子集，用于估计距离：只\(q_c(x)\)对应的inverted list \(L_i\)会被扫到。

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

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

Indexing一个vector y的过程

• 1) 将y量化到\(q_c(y)\)
• 2) 计算residual：\(r(y) = y - q_c(y)\)
• 3) 将\(r(y)\)量化到\(q_p(r(y))\)，对于product quantizer来说，相当于将\(u_j(y)\)分配给\(q_j(u_j(y))\)，其中\(j=1 \cdots m\)
• 4) 添加一个new entry到\(q_c(y)\)对应的inverted list中。它包含了vector (或image) identifier以及binary code（product quantizer的indexes）。

Searching

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

• 1) 将x量化到在codebook \(q_c\)中的w个最近邻。为了简明，在下两个step，我们会通过将r(x)表示与w assignments相关的residuals。这两steps会被应用到所有的w assignments中。
• 2) 对于每个subquantizer j和每个centroid \(c_{j,i}\)，计算squared distance \(d(u_j(r(x)), c_{j,i})^2\)
• 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量化到\(q_c(x)\)的求和step 包含了在D维vectors间计算\(k'\)个距离。假设inverted lists是balanced，那么需要解析\(n \times w/ k'\)个entries。因此，search要比ADC更快，下一节将介绍。

5. NN Search的评估

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

略

参考

• 0.Product quantization for nearest neighbor search

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（\(0 \cdots nlist-1\)）映射到一个(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);
}

参考

• Video Google: A Text Retrieval Approach to Object Matching in Videos

• http://mccormickml.com/2017/10/22/product-quantizer-tutorial-part-2/

• https://github.com/facebookresearch/faiss/wiki/Inverted-list-objects-and-scanners

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 \(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

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\)：

在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\)（洛诺伊／泰森多边形）是以下集合：

\(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\)会满足：

其中\(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

参考

• https://www.cs.jhu.edu/~misha/Spring16/11.pdf
• https://www.aclweb.org/anthology/D19-1527.pdf

Thiago Silveira等人在《How good your recommender system is?》中对Novelty概念做了个总结，我们来看下：

Novelty

novelty的概念通常涉及到：在推荐系统中有新(novel)的items。尽管一开始看起来很简单，但novelty在文献中有许多种定义。因此，为了让定义更简单，我们对novelty定义和指标划分成三个level，如下所示。Novelty指标被称为：\(nov(R_u)\)。

• level 1: Life level。在用户生命周期中一个item是novel的，也就是说，该用户从未在它的生命周期中听说过该item
• level 2: System level。根据用户的历史消费行为，该item对该用户是未知的
• level 3: Recommendation list level。在推荐列表中无冗余的items（Non-redundant）

Life level novelty

有一些作者将novelty定义在life level上。Kappoor et al.[19]将未知items（unknown）描述成：在用户的生命周期中从未消费或未知的items。Ricci et al.[29]则认为novel items应对用户未知。这些作者的定义看起来指的都是level 1 novelty，并进一步提出了一种假想的方法来measure novelty：询问用户是否知道该item。另外，Zhang et al.[38]认为，当提到预测时，从一个RS影响而消费的items会被推荐器考虑到。那么，在用户生命周期之前用户未知的items是novel items。

对于life level novelty进行measure而创建metrics是no-trivial的。对于level 1 novelty的一个合理metric是：考虑上超出系统上下文的信息，以便能measure用户是否已知。

System level novelty

system level novelty在文献中也有许多定义。一个用户的novel item可以认为是：该用户对该item完全不知或知道很少。Herlocker et al. [14]等将这样的items认为是：当一个RS预测items时，这种novelty items对用户来说是完全不知的，或者通过其它源未被发现的。另外，novelty也可以被定义成：推荐的item与用户已经消费的items相当不同[36]。最终，novelty也可以被定义成：对某用户的预测列表中未知items的比例[15]。实际上，这样的novel items定义只考虑了：当在用户的消费历史中观察到之前已消费items；在系统外消费的items不会被考虑其中。总之，即使作者使用了不同的话术，他们仍具有相同的意思：level 2的novelty意味着：当考虑上系统信息时，用户不知的items。

在文献中提出的大多数metrics的评估适用于level 2. Nakatsuji et al. [26]提出了一种metric，它会在推荐列表中计算novelty，认为是：在推荐列表中的items与用户历史中(\(H_u\))之间的相似度。该metric如等式(7)所示。作者使用items的类目(classes)来对items间的距离进行measure。d是一个distance function，\(class(i)\)表示了item i的classes。该idea可以被推广到items的features或genres。metric如下：

…(8)

Zhou et al.[40]指出的metric则会计算该用户在推荐列表中items的流行度（popularity）。等式(8)展示了novelty metric。例如：一个item的popularity(pop)可以通过有多少消费过它的用户数来计算。Zhang et al.[38]定义的novelty可以被认为是level 1, 该作者的metric与level 2有关，因为popularity通过消费该item的用户量来计算，会使用用户消费数据。因此，该items的novelty仍然是system level的。对于novelty所使用Popularity-based matrics在Ricci et al.[29]中提出。如等式(8)所示，该metric会简单计算一个推荐列表的novelty：通过在list中的items的popularity计算得到。另外作者也提供的metric的变种，比如：\(- log_2 \frac{pop(i)}{\| U \|}\)，这与Zhang et al.[38]相似。

…(9) (10)

recommendation list level novelty

level 3指的是在推荐列表级别的novelty，也就是说，items不会被重复推荐。某种意义上，novelty被定义成在推荐列表中没有重复items，并不会涉及到用户信息。Adamopoulos et al. [1] 认为novelty与在推荐列表中的non-redundant items 有关。level 3可以认为是level 2的特例，其中在推荐列表中没有冗余items或重复items。

level 3的novelty指标衡量指的是在推荐列表中的items。不需要用户信息。等式（10）会计算在推荐列表中的items间相似度。另外，\(d(i,j)\)意味着item i和j间的距离。然而，该指标看起来类似于intra-list similarity，不适合对novelty进行measure。

另外，Vargas and Castells [36] 提出了一种不同的metric来measure推荐列表中的novelty。等式(11)展示了该metric。该metric会考虑items在ranked recommendation list中的items的位置，以便计算关于浏览完整个list的一个discount（\(disc(i_k)\)）。另外，该metric也会计算：当浏览时该用户已经看到过item的概率\(p(seen \| i_k)\)。由于该概率可能会/不会考虑用户的消费信息，该指标最适合level 2和level 3间novelty的划分。

参考：

https://rd.springer.com/article/10.1007/s13042-017-0762-9