十亿级最近邻的倒指数搜索方法

十亿级近似最近邻的倒指数研究Dmitry Baranchuk1， 2，Artem Babenko1， 3，Yury Malkov41Yandex2莫斯科国立罗蒙诺索夫大学3国立研究型大学高等经济学院4俄罗斯科学抽象。 这项工作解决了十亿级最近邻搜索的问题。目前，十亿级数据库的最先进的检索系统多索引提供特征空间的非常细粒度的分区，其允许提取用于搜索查询的候选者的简明且准确的短列表。在本文中，我们认为，简单的倒排索引的潜力没有充分利用在以前的作品，并主张其使用高度纠缠的深描述符和相对解开SIFT描述符。我们引入了一个新的检索系统，是基于倒排索引和性能优于多索引的大幅度相同的内存消耗和建设复杂性。例如，与FAISS库中的反向多索引的有效实现相比，我们的系统在10亿个深度描述符的数据集上实现了最先进的1介绍最近十年高效的十亿级最近邻搜索已经成为一个重要的研究问题[1大规模视觉搜索[7]，低镜头分类[8]和人脸识别[9]。特别是，由于互联网上的图像数量增长非常快，多媒体检索系统需要可扩展的和有效的搜索算法，以响应查询的数据库中的数十亿个项目在几毫秒。所有现有的十亿级系统都通过限制数据库中被考虑用于查询的部分来避免不可行的穷举搜索。此限制是在索引结构的帮助下执行的。索引结构将特征空间划分为大量不相交的区域，并且搜索过程仅检查来自最接近特定查询的区域的点。被检查的点被组织在候选者的短列表中，并且搜索系统详尽地计算查询与所有候选者在某些情况下，当数据库不适合RAM时，将使用数据库点的压缩表示的2Baranchuk D. Babenko A. 马尔科夫压缩表示通常通过乘积量化[10]获得距离计算的步骤具有在候选者的数量上是线性的复杂性，因此由索引结构提供的短列表应该是简洁的。第一个能够在十亿级数据集上操作的索引结构在[1]中引入。它基于反向索引结构，该结构将特征空间分割为一组K均值质心的Voronoi区域，这些质心是在数据集上该系统被证明可以在几十毫秒内实现合理的召回后来在[2]中提出了倒排索引结构的推广。该方法将特征空间分解为多个正交子空间，并将每个子空间独立地划分为Voronoi区域。然后在每个子空间中的区域的笛卡尔积形成整个特征空间的隐式划分由于大量的区域，IMI空间分区是非常细粒度的，并且每个区域仅包含几个数据点。因此，IMI形成准确和简洁的候选列表，同时具有内存和运行时效率。然而，IMI分区中区域的结构化性质也对最终检索性能产生负面影响特别是，[5] 大多数IMI区域不包含点，并且有效区域数远小于理论值。对于某些数据分布，这导致搜索过程花费大量时间访问不产生候选者的空区域。事实上，这种缺陷的原因是IMI独立地为不同的子空间学习K-Means码本，而相应的数据子向量的分布在实践中在统计上并不独立。特别是，CNN产生的描述符的不同子空间之间存在显着的相关性，这些描述符是当今最相关的。在本文中，我们认为，以前的作品低估了简单的倒排索引结构，并主张使用它的所有数据类型。我们的论文的贡献包括：1. 我们证明了倒排索引的性能可以通过使用更大的码本来大幅提升，而多索引设计不允许这样的提升。2. 我们引入了一个高效的内存分组程序的数据库点，进一步提高检索性能。3. 我们提供了一个优化的实现我们的系统在压缩域中的十亿级搜索，以支持对这个问题的以下研究。正如我们所展示的，与FAISS库[6]中的高级IMI实现相比，在相同的内存消耗下，所提出的系统实现了最先进的我们的系统的C++实现是公开的在线5。5https://github.com/dbaranchuk/ivf-hnsw十亿级人工神经网络反演指标的再探讨3M本文件的结构如下。我们在第2节中回顾了十亿级索引的相关工作。第三部分介绍了一种基于倒排索引的新系统。第4节详细介绍了证明我们系统优势的实验。最后，第五章对全文进行了总结。2相关工作在本节中，我们简要回顾与我们的方法相关的先前方法。这里我们还介绍了以下部分的符号。乘积量化（PQ）是用于高维向量的有损压缩方法[10]。通常，PQ用于大规模数据集不适合主内存的情况。简而言之，PQ通过来自M个D维码本R1，…，R2的M个码字的级联来编码每个向量x∈R_D。. . ，RM. 每个码本通常包含256个码字{r m，. . .，r m} RD，使得码字id可以适合一个字节。换句1 256换言之，PQ将向量X分解成M个单独的子向量[X1，. . .，X M]和将矢量量化（VQ）应用于每个子矢量Xm，同时使用单独的码本Rm。则向量x的M字节代码是码字的元组索引[i1，. . . ，iM]，有效近似为x ≈ [r1，. . . ，r M]。作为i1iMPQ是一个很好的属性，它允许有效地计算未压缩查询和大量压缩向量。通过ADC程序[10]使用查找表进行计算：ΣMq − x. . ，r M]2=qm−rmi1iMImm=1其中qm是查询q的第m个子向量。假定从查询子向量到码字的距离被预先计算并存储在查找表中，则可以在M次加法和查找中计算该和。由于高压缩质量和计算效率，基于PQ的方法目前是大型数据集紧凑表示的首选。PQ引起了计算机视觉和机器学习界对高维向量压缩的积极研究[11IVFADC [1]是第一个能够有效处理十亿级数据集的检索系统之一。IVFADC使用倒排索引[20]来避免穷举搜索和产品量化以进行数据库压缩。反转索引将特征空间分割成K个区域，这些区域是码本C={c1，. . . ，c K}。码本通常经由标准K均值聚类来获得然后IVFADC编码每个点从其所属区域的质心的位移编码通过乘积量化来执行，其中全局码本由所有区域共享。反相多指数和多D-ADC。 倒排多索引（IMI）[2]是对倒排索引的推广，是目前最先进的高维空间和大型数据集的索引方法而不是使用的全维码本，IMI分裂成几个4Baranchuk D. Babenko A. 马尔科夫2正交子空间（通常考虑两个子空间），并为每个子空间构造单独的码本因此，反向多索引具有用于向量的不同半部的两个D维码本，每个D维码本具有K个子空间质心。特征空间分区然后被产生为对应子空间分区的笛卡尔乘积因此，对于两个子空间的倒置多指标有效地产生K2区域。即使是中等K值，也比IVFADC系统或其他使用倒置指数的系统中的区域数量大得多由于区域的数量非常大，因此仅应访问数据集的一小部分以到达正确的最近邻。[2]还描述了产生最接近特定查询的区域序列的多序列过程。对于数据集压缩，[2]还使用乘积量化，在所有单元格中共享码本来编码矢量从区域质心的位移。所描述的检索系统被称为Multi-D-ADC。通过使用最小化子空间之间的相关性的全局数据旋转，可以进一步提高Multi-D-ADC方案中的索引性能[3]。另一个改进[4]引入了多LOPQ系统，该系统使用本地PQ码本进行IMI结构的位移压缩其他几个作品考虑的问题，内存效率的十亿规模的搜索。[5]提出了使用两个非正交码本来产生区域质心的反向多索引的修改。[16]建议使用复合量化[15]而不是乘积量化来产生分区质心。虽然这些修改与原始多索引相比实现了更高的召回率，但它们的典型运行时间约为10毫秒，在实际场景中可能非常慢一些作品研究了用于十亿级搜索的高效GPU实现[6，21]。在本文中，我们关注的是与运行时操作的CPU方法的利基大约一毫秒。3再论倒排索引在本节中，我们首先将倒排索引与IMI进行比较。特别是，我们表明，简单的增加的码本大小可以大大提高索引质量的倒排索引，而几乎是无用的IMI。其次，我们引入了一个修改的倒排索引，可以用来提高索引性能，甚至进一步没有效率下降。3.1指数与多指数我们在表3.1中比较了倒排索引和IMI的主要特性。表格的顶部列出了使IMI成为当今最先进的索引结构的特性：精确的候选列表、由于小的码本大小（对于十亿大小的数据库，通常K不超过2× 14）而导致的快速索引和查询分配。十亿级人工神经网络反演指标的再探讨5结构倒排索引倒排多索引候选人名单质量介质高查询分配索引成本介质低随机存储器搜索期间访问小大大K高小内存消耗可伸缩性O（K）O（K2）表1.倒排索引和IMI的主要特性比较K表示两个系统中的码本大小IMI提供更精确的候选列表，并且由于较小的码本大小而具有低的索引和查询分配成本另一方面，倒排索引在搜索时需要较少数量的昂贵的随机存储器访问，并且可以受益于大的码本，而IMI性能在K约为2- 14时饱和。此外，K的增加在IMI中是存储器低效的，因为其额外的存储器消耗成二次方地缩放。尽管如此，多索引中的细粒度划分带来了一些限制，这些限制在表3 - 1的底部进行了总结。首先，与倒排索引相比，IMI必须访问更多的分区区域以累积合理数量的候选。跳到下一个区域需要随机存储器访问操作，其与顺序PQ距离计算相比更昂贵，特别是对于短代码长度。 大量的随机访问操作减慢了搜索，特别是当需要大量的候选者时。有利于反向索引的另一个属性是增加其码本大小K的可能性。据我们所知，索引与多索引比较中使用的最大码本大小分别为217和214我们认为，多索引的性能是更接近饱和相对于倒排索引K，和使用K>214不会导致实质上更好的特征空间分区。另一方面，在倒排索引中，可以使用比K=217大得多的码本，而不会使空间分区质量饱和。为了支持这一说法，我们比较了从数据点到表2中DEEP1B数据集[5]的倒排索引和IMI的最近质心的距离以及不同的K值较小的距离通常指示质心更好地表示实际数据分布表2表明，与反向索引相比，多索引中K的增加导致最近距离的小得多的减小例如，在倒置指数中K从218增加到222的16倍导致平均距离下降18%。另一方面，IMI分区中区域数的16倍增加（对应于K从213增加到215的四倍）仅导致11%的下降。我们还比较了具有不同K值的两个系统所需的额外存储器消耗的百分比，以证明IMI对于大型码本是存储器低效的例如，对于K=215，对于10亿个数据库，反向多索引需要每点大约四个额外字节，这是不可忽略的，特别是对于短代码6Baranchuk D. Babenko A. 马尔科夫长度二次可伸缩性的原因是IMI必须保持K2倒排表来表示特征空间的划分.倒排索引倒排多索引K平均距离存储器 K平均距离存储器2180.31597Mb2130.345256MB2200.282388Mb 2140.3211024MB2220.2591552Mb 2150.3054096Mb表2.的索引质量和额外的内存消耗量在DEEP1B数据集上具有不同码本大小的倒排索引和IMI索引质量由从数据点到最近区域质心的平均距离来评价。IMI索引质量不受益于K>214，而所需的存储器二次增长。来自表2的数字鼓励使用具有较大码本的反转索引而不是IMI，尽管分区区域的数量较小唯一实际的原因，阻止他们的使用，是昂贵的查询分配过程，需要O（K）的操作。但是在下面的实验部分中，我们证明了由于百万级ANN搜索的最新进展，可以使用高精度的近似搜索来进行查询分配。我们表明，使用近似搜索不会导致搜索性能下降和近似查询分配的倒排索引的整体方案优于国家的最先进的IMI实现。3.2分组和修剪现在，我们描述一种技术，是特别有用的IVFADC计划的压缩域搜索。在一般情况下，我们提出了一个程序，在每个区域中的点组织成几个组，这样的点在附近的位置属于同一组。换句话说，我们希望将每个倒排索引区域分割成一组较小的子区域，对应于一组子质心的Voronoi单元。通过每个区域中的K均值聚类的该问题的朴素解决方案将需要存储全维子质心码本，这将需要太多的存储器。相反，我们提出了一个几乎无记忆的方法，在每个区域构造的子质心码本作为一组凸组合的区域质心和它的相邻质心。我们将所提出的技术称为分组过程，并在下面对其进行正式描述。该模型分组过程是针对所有因此对于具有质心C的单个区域描述它就足够了。我们假设数据库点{x1，. . .，xn}属于该区域。让我们用s1表示。. .，s L∈C，质心c的最近质心：{s1，. . . ，s L}= NN L（c）（2）十亿级人工神经网络反演指标的再探讨7QQFig. 1. 200个二维点（小黑点）的数据集的索引和搜索过程，倒排索引（左）和倒排索引增加了分组和修剪过程（右）。大的绿色点表示区域质心，并且对于每个质心，预先计算L=5个相邻质心。对于右图中心的三个区域，区域次质心表示为红色的点。相同查询q遍历的数据库的片段（有修剪和没有修剪）以蓝色突出显示。这里，查询被设置为仅访问τ=40%的最近子区域。其中NNL（c）表示所有质心的集合中c的L个最近邻的集合。 区域次质心则取为{c + α（s l− c）}，l = 1，. . . ，L，其中α是从数据学习的标量参数，如下所述。请注意，在不同区域中使用不同的α值 点{x1，. . . ，xn}分布在由这组子质心产生的Voronoi子区域上。对于每个点xi，我们确定最近的子质心li= arg minxi−（c+α（sl−c））2（3）L在索引结构中，区域点被存储在组中，即，来自相同子区域的所有点被连续排序。在这个方案中，我们只存储子区域的大小，以确定特定的点属于什么组分组后，从相应的次质心xi−（c+α（sli−c））（4）与原始IVFADC中一样，使用PQ进行压缩。注意，到子质心的位移通常具有比到区域质心的位移更小的范数，如在IVFADC方案中因此，可以用相同的码长更准确地压缩它们这导致检索方案的更高的召回率，如将在实验部分中示出的。8Baranchuk D. Babenko A. 马尔科夫距离估计现在我们描述如何计算分组后到压缩点必须计算一个表达式：q-c-α（s-c）-[r1，. . . ，r M]=2（5）其中[r1，. . . 是数据库点位移的PQ近似。表达式（5）可以按以下方式变换：q-c-α（s-c）-[r1，. . . ，r M]2=（1 − α）q − c2 +ΣM+αq−s2− 2m=1∠qm，rm∠+const（q）（6）上面的总和中的第一项可以很容易地计算为距离q − c距离q−s2在访问区域点之前在线计算请注意，相邻区域的质心集合通常具有较大的交叉点，并且为了效率，我们不重新计算距离q−s2，这是之前为先前区域计算在区域遍历之前，预先计算查询子向量与PQ码字之间的标量积最后一项与查询无关，我们将其量化为256个值，并将其量化值作为点代码中的附加字节显式保留。注意，到相邻质心的距离的计算导致额外的运行时间成本。在下面的实验中，我们证明了这些成本是完全合理的压缩精度的提高子区域的数量L以这样的方式设置：与压缩的数据库大小相比，附加的存储器消耗（K·L·sizeof（float）字节）可以忽略不计。次区域修剪。上述分组技术的使用还允许搜索过程在区域遍历期间跳过最不有希望的子区域。这提供了总的搜索加速而不损失搜索精度。下面我们将这样的子区域跳过称为修剪。让我们更详细地描述修剪 考虑遍历具有质心c的特定区域，相邻质心s1，. . .，sL和缩放因子α。到子质心的距离然后可以容易地预先计算如下：<$q − c − α（s l− c）<$2=（1 − α）<$q − c<$2+ α<$q − s l<$2+ const（q），l = 1。. . L（7）在上面的求和中，第一项和第二项如前一段中所描述的那样计算，而最后一项是离线预先计算的并且针对每个相邻质心显式地存储如果搜索过程被设置为访问k个倒排索引区域，则计算到子质心的kL距离，并且仅访问最近子区域的特定分数τ在实践中，我们观察到，搜索过程可以过滤掉多达一半的子区域，而没有精度损失，这提供了额外的搜索加速。图1示意性地演示了针对同一查询的具有和不具有修剪的检索阶段。学习缩放因子α。 最后，我们描述了如何学习具有质心c和相邻质心的特定区域的缩放因子α。十亿级人工神经网络反演指标的再探讨9LiLi质心S1，. . . ，S L. α是在保持学习集上学习的，并且我们假设该区域包含学习点x1，. . . ，X n。我们的目标是解决以下最小化问题：minα∈[0;1]Σni=1minxi−c−α（sli−c）2（8）Li换句话说，我们希望最小化数据点和缩放的子质心之间的距离，假设每个点都被分配到最近的子质心。我们还限制α属于[0; 1]分段，使得每个子质心是c和相邻质心s之一的凸组合。上述问题的精确解需要在以下方面进行联合优化连续变量α和离散变量li。我们求解（8）大约分两步：1. 首先，对于每个训练点xi，我们确定最佳sli值。这是通过最小化辅助函数来执行的，该辅助函数是（8）中的目标函数的下界：Σni=1minli，αi∈[0;1]xi−c−αi（sli−c）对于每个学习点xi，该问题可分解为n个相同的最小化子问题：minαi∈[0;1]，slixi−c−αi（sli−c）<$2（10）这个子问题通过在所有可能的sli上的穷举搜索来解决。对于固定的sii，αi上的最小化具有封闭形式的解，并且可以显式地计算目标函数（10）的对应的最小值。那么子问题（10）对于点xi的解是：....（xi−c）T..（s li− c）..sli= arg min.. xi−c−（s li−c）..（十一）sli ......你好。s li−c2. 其次，我们用s*的值在α上最小化（8）获自上一步。在这种情况下，最优值的封闭形式解为：Σnα=i=Σ1 （xin-c）T（s*−c）s（十二）i=1li讨论上述分组和修剪过程允许增加压缩准确性和候选列表质量。这导致最终系统性能的显著增强，如将在实验部分中示出注意，这些过程对于倒排索引更有效，并且由于其空间分区中的非常大数量的区域，它们不能在IMI中被有效地利用。210Baranchuk D. Babenko A. 马尔科夫4实验在这一节中，我们提出的建议索引结构和相应的检索系统与当前国家的最先进的实验比较数据集。我们在公开可用的数据集上执行所有实验，这些数据集通常用于十亿级ANN搜索评估：1. DEEP1B数据集[5]包含来自Web的自然图像的10亿个96维CNN生成的特征向量。该数据集还包含3.5亿个描述符和10，000个查询的学习集，其中具有用于评估的地面实况最近邻居。2. SIFT1B数据集[1]包含10亿个128维SIFT描述符作为基集，1亿个向量的保持学习集，以及10，000个具有预先计算的groundtruth最近邻居的查询向量。在大多数实验中，通过Recall@R度量来评估搜索精度，Recall @R度量被计算为在长度为R的短列表中呈现真正最近邻的查询的比率。所有可训练参数都是在保持学习集上获得的。所有实验都在Intel XeonE5-2650 2.6GHz CPU上以单线程模式进行。倒排索引中的大码本。正如我们在第3节中所展示的，即使使用数百万个质心的码本，倒排索引的索引质量也不会饱和。 由于穷举查询分配对于大型码本将是低效的，因此我们通过HNSW算法使用近似最近的质心搜索[22]。该算法是基于邻近图，构造上的一组质心。正如我们在实验中观察到的，HNSW允许在亚毫秒的时间内以几乎完美的精度获得最近质心的小顶部我们还在码本学习阶段使用HNSW来加速K-Means迭代期间的分配步骤HNSW搜索的唯一成本是维护邻近度图所需的额外存储器在我们的实验中，邻近图的每个顶点连接到32个其他顶点，因此所有边列表的总存储器等于32·K·sizeof（int）字节，其中K表示码本大小。请注意，HNSW的准确性和效率对于成功使用具有近似分配的大型码本至关重要 早期使用较大码本的努力并不成功：[2]基于具有非常大的码本的倒排索引来评估该方案，其中经由kd树找到最接近的质心[23]。结果表明，该方案是不能够实现国家的最先进的召回率，由于最近的质心搜索的不准确性。索引质量。在第一个实验中，我们评估不同的索引方法提取简洁，准确的候选列表的能力。此处不执行候选日期重新排序。我们比较以下结构：1. 反向多指数（IMI）[2]。我们使用大小为K= 214的码本评估IMI，并考虑在数据空间分解[3]之前具有全局旋转的IMI的变体，其提高了以下数据集上的IMI性能：十亿级人工神经网络反演指标的再探讨11反向多指标K= 214倒置指数K= 22020倒置指数K= 2修剪+剪枝1.00.90.8DEEP1B SIFT1B1.00.90.80.7 0.70.6 0.60.5 0.50.4 0.40.3 0.30.2 0.20.1 0.10.00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Log2 R0.00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20Log2 R图二、调用作为候选列表长度的函数，用于具有K=214的反向多索引、具有K=220的反向索引，具有和不具有修剪。在DEEP1B的反转指数优于IMI的R的所有合理的值由一个大的利润率。对于SIFT1B，具有修剪的倒排索引的候选列表质量与R大于213的IMI的质量相当。深层描述符在所有实验中，我们使用FAISS库[6]中的实现。2. 反相索引[20]。我们使用K=220个质心的大码本。通过HNSW执行查询分配。3. 倒排索引+分组+修剪。在这里，我们使用3.2节中描述的分组和修剪过程来增强上面的倒排索引设置子区域的数量被设置为L=64，并且修剪比率被设置为τ= 50%。不同R值的Recall@R值如图2所示尽管区域数量少得多，但与DEEP1B数据集的IMI相比，倒排索引产生更准确的短列表。注意，倒排索引中的修剪过程甚至进一步提高了短列表质量该图中最实际的部分对应于R= 104− 105，在此范围内，倒排索引的性能优于IMI高达10%。对于SIFT 1B数据集，K=214的IMI对于R的小值产生稍微好一点的候选列表。对于R >213，倒排索引的质量与IMI质量相当IMI在SIFT向量上是成功的，因为它们是基于直方图的，并且对应于它们的不同半部的子向量描述了通常具有相对弱的统计相互依赖性的不相交图像部分然而，正如我们在接下来的实验中所示，由于多序列算法的效率低下和大量的随机存储器访问，IMI中的候选提取的运行时成本很高ANN：索引+重新排序。作为最重要的实验，我们评估了建立在上述索引结构之上的检索系统的性能，几乎相同的内存消耗。所有的反向多指标K= 214倒置指数K= 22020倒置指数K= 2修剪+剪枝召回@R12Baranchuk D. Babenko A. 马尔科夫R@10，8字节R@10，16字节系统在压缩域（即，数据库点从它们的区域质心的位移是OPQ压缩的，代码长度等于每点8或16字节。在该实验中，基于查询和压缩的候选点之间的距离对候选列表进行重新排序。OPQ码本是全球性的，由所有地区共享我们比较以下系统：0.280.600.260.550.240.500.22 0.450.20 0.400.18 0.350.160.450.20.40.60.81.01.21.41.61.82.00.300.850.20.40.60.81.01.21.41.61.82.00.430.800.410.750.390.700.370.650.350.600.33 0.550.31 0.500.29 0.450.27 0.400.250.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0 2.2 2.4 2.6 2.8时间（ms）0.350.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 1.8 2.0 2.2 2.4 2.6 2.8时间（ms）图三.重新排序后的R@1和R@10值作为DEEP 1B上运行时间的函数。基于倒排索引的系统实质上优于基于IMI的系统。具有分组的IVFOADC系统优于具有相同存储器消耗的较大码本的IVFOADC1. O-Multi-D-OADC是我们的主要基准系统。它使用具有全局旋转的逆多索引和大小K=214的码本。该系统需要1 Gb的额外内存来维持IMI结构。2. IVFOADC基于具有大小K=222的码本的反转索引。该系统需要2。5Gb的额外存储器，用于存储码本和HNSW图形。3. IVFOADC-fast是使用表达式（6）进行有效距离估计的系统，其中α= 0。这个系统也是基于倒置O-Multi-D-OADC 214IVFOADC 222IVFOADC-fast221IVFOADC+G 220IVFOADC+G+P 220R@1，16字节R@1.8字节十亿级人工神经网络反演指标的再探讨13索引而不分组，但需要每个点一个附加的代码字节来存储来自（6）的查询无关项我们使用K=2- 21为这个计划，使总的内存消耗相同的前一个系统。存储器消耗包括用于附加码字节的1Gb和用于附加码字节的1. 25Gb来存储码本和给出2. 总共25GB4. 此外，IVFOADC+ ADC还采用了每个区域L=64个亚质心 在这个系统中，我们使用一个码本与K =220，导致在总的内存消耗1。87GB。5. IVFOADC+修剪+修剪采用L=64个亚质心的分组和修剪过程。修剪被设置为过滤掉50%的子区域。在这个系统中，我们也使用一个码本与K=2- 20。我们在DEEP 1B数据集上绘制了不同长度候选列表的Recall@1和Recall@10，结果总结于图3中。我们强调几个关键的观察结果：1. 基于倒排索引的系统在准确性和搜索时间方面优于基于IMI的特别是，对于1.5 ms时，IVFOADC+G+P系统在DEEP 1B数据集和8字节代码上的性能分别比O-多-D-OADC高7和17个百分点的R@1和R@10。至于运行时间，与O-Multi-D-OADC相比，该系统达到相同召回值的速度快了几倍。2. 具有分组和修剪的IVFOADC系统优于具有较大码本而没有分组的IV-FOADC系统。当来自分组的附加编码容量更有价值时，该优点对于短8字节代码是最显著的。倒排多索引的局限性。在这里，我们进行了几个实验，以证明近似查询分配和分组更有利于IVFADC比IMI。理论上，还可以通过使用近似最近子空间质心搜索来加速基于IMI的方案然而，在这种情况下，人们将不得不找到几百个最接近的项目，从一个中等的码本大小K=2- 14，我们观察到，在这种设置中的近似搜索与HNSW需要几乎相同的时间作为蛮力。此外，这样的加速将不会加速由于大量的空区域而在多索引中相当慢的候选累积。其次，与倒排索引相比，分组过程对于IMI不太有效在K= 214的情况下，IMI空间分区中的每个区域仅包含几个点，因此分组是无用的。为了评估具有较粗码本的IMI的分组有效性，我们执行以下实验。我们计算在L=64分组之前和之后从数据点到最近（子）质心的平均距离的相对减小在这里，我们比较的倒排索引与K=220和IMI与K=210，导致在空间分区具有相同数量的区域。分组前后的平均距离平均距离的相对减小对于IMI较小，这意味着与IMI相比，分组对于倒排索引更有效然而，我们假设14Baranchuk D. Babenko A. 马尔科夫其中一个有趣的研究方向是研究分组是否可以有效地并入IMI中。LR@1 R@10 R@100t（ms）倒排索引倒排多索引32 2017年12月31日1.22无分组0.2820.41564 0.433 0.785 0.8781.28与分组0.2550.385128 2009年12月31日1.48减少百分之十占7%表3. 左：针对DEEP 1B数据集上每个区域的不同数量的亚质心的IV-FOADC+分组+修剪系统的召回值和运行时间。这里我们使用长度为30K的候选列表和16字节代码。右：DEEP1B数据集上K= 220的倒排索引和K= 210的 IMI的分组次区域的数目。我们还证明了所提出的方案的性能为每个区域L的不同数量的亚质心。在表3中，左边我们提供了针对大小为30K和16字节代码的候选列表对DEEP1B上的IVFOADC+分组+修剪系统的评估由于运行时间和内存消耗的增加，L>64的使用很难被证明是合理的与最先进的技术相比。最后，我们将所提出的IVFADC+G+P与文献中报道的关于DEEP1B和SIFT1B的结果进行比较，参见表4。除了召回值和时间，我们还报告了每个系统所需的每个点的附加内存量。DEEP1BSIFT1B方法KR@1 R@10 R@100 不 Mem R@1 R@10 R@100 不 Mem[24]第二十四话214 0.397 0.7660.909 8.5 17.34 0.360 0.7920.9015 17.34多LOPQ [4]214 0.410.79-20 18.68 0.454 0.862 0.90819 19.22GNOIMI[5]214 0.450.81-20 19.75-----IVFOADC+G+P220 0.452 0.832 0.947 3.3 17.87 0.405 0.851 0.957 3.518表4.比较以前的作品为16字节的代码。搜索运行时以毫秒为单位报告。我们还提供检索系统所需的每个点的内存（数字以字节为单位，不包括点ID的4个字节5结论在这项工作中，我们提出并评估了一个新的十亿级最近邻搜索系统。该系统扩展了众所周知的倒排索引结构，并没有对数据库点的分布做任何假设，这使得它成为一个通用的工具，任何数据统计数据集。该计划的优势是证明了20亿规模的公开可用的数据集。十亿级人工神经网络反演指标的再探讨15引用1. Jegou，H.，塔弗纳德河Douze，M.，Amsaleg，L.：在十亿个向量中搜索：用源代码重新排序。在：ICASSP中。（2011年）2. Babenko，A.，Lempitsky，V.S.：反向多索引。在：2012年IEEE计算机视觉和模式识别会议，Providence，RI，美国，2012年6月16-21日。（2012年）3. Ge，T.，他，K.，Ke，Q.孙杰：优化产品量化。技术报告（2013）4. Kalantidis，Y.，Avritis，Y.：局部优化的产品量化近似最近邻搜索。In：inProceedingsofInternationalConferenceonComputerVisionandPatternRecognition（CVPR 2014），IEEE（2014）5. Babenko，A.，Lempitsky，V.S.：深度描述符的十亿级数据集的高效索引。在：CVPR中。（2016年）6. 约翰·索恩， Douze，M.， 我走了H ：Billion-scalesimi a rar a r a r ithgp us。预印本arXiv：1702.08734（2017）7. Philbin，J.，Chum，O.，Isard，M.，Sivic，J.，齐瑟曼，A.：具有大词汇量和快速空间匹配的对象检索。在：CVPR中。（2007年）8. Douze，M.，Szlam，A.，Hariharan，B.，Jegou，H.：大规模扩散的低镜头学习。在：CVPR中。（2018年）9. Wang，D.，中国科学院，奥托角Jain，A.K.：大规模人脸搜索。TPAMI（2017）10. 我是H Douze，M.， S chmid，C. ： 为保留的内容或搜索提供查询。TPAMI 33（1）（2011）11. Ge，T.，他，K.，Ke，Q.孙杰：用于近似最近邻搜索的优化乘积量化。在：CVPR中。（二零一三年）12. Norouzi，M.，Fleet，D.J.：笛卡尔k均值在：CVPR中。（二零一三年）13. Babenko，A.，Lempitsky，V.：用于极端矢量压缩的加性量化在：CVPR中。（2014年）14. Babenko，A.，Lempitsky，V.S.：用于大规模相似性搜索和分类的树量化。在：CVPR中。（2015年）15. 张，T.，杜，C.，Wang，J.：近似最近邻搜索的复合量化。在：ICML。（2014年）16. 张，T.，Qi，G.J.，唐，J.，Wang，J.：稀疏复合量化。在：CVPR中。（2015年）17. Martinez，J.Clement，J.，呼H. HLittle，J.J.：再谈加性量化。In：ECCV.（2016年）18. Douze，M.， 我走了H Perronnin，F. ：polysemousc odes. In：ECCV. （2016年）19. Jain，H.， P'erez，P.， Gribonval，R.， Zepeda，J.， 我走了H ：利用量化的稀疏表示来对ppr 〇ximate eser ch。In：ECCV. （2016年）20. Sivic，J.，齐瑟曼，A.：Video google：一种视频中对象匹配的文本检索方法In：ICCV. （2003年）21. Wieschollek，P.，Wang，O.，Sorkine-Hornung，A.，Lensch，H.P.A.：GPU上高效的大规模近似最近邻搜索在：CVPR中。（2016年）22. Malkov，Y.A.，Yashunin，D.A.：使用分层可导航小世界图的高效和鲁棒的近似最近邻搜索。arXiv预印本arXiv：1603.09320（2016）23. Bentley，J.L.：用于关联搜索的多维二叉搜索树。Commun. ACM 18（9）（1975）24. Babenko，A.，Lempitsky，V.S.：反向多索引。IEEE Trans. PatternA nal.Mach。我告诉你。37（6）（2015）1247