基于乘积量化器的倒排索引优化方案

12210数据点粗心细码丢失基于乘积量化器的可伸缩最近邻搜索倒排索引Haechan Noh，Taeho Kim，Jae-PilHeo*成均馆大学{noru0114，kth0522，jaepilheo} @ skku.edu摘要倒排索引是大规模数据集上非穷举最近邻搜索最常用的结构之一。它允许一个显着的加速因子，通过减少距离计算的数量，只有一小部分的数据库。特别地，反转索引使得乘积量化（PQ）能够在残差向量空间中学习它们的码字PQ的量化误差可以在这样的组合中得到显著改善，因为残差向量空间由于其与原始数据相比的紧凑分布而更加量化友好。在本文中，我们首先提出了一个未被注意但却至关重要的问题;为什么反向指数和乘积量化器被分别优化，即使它们是密切相关的？例如，倒排索引上的改变使整个残差向量空间失真。为了解决所提出的问题，我们建议一个联合优化的粗和细量化器的原始目标的粗量化器端到端的量化失真的替代。此外，我们的方法是通用的，适用于不同的组合，如倒置的多指标和优化PQ的粗和细量化。1. 介绍近几十年来，近似最近邻搜索一直是包括计算机视觉在内的各个领域中的重要问题。这是特别困难的高维和大规模的数据集，因为它的计算成本和内存开销的不切实际的要求。为了解决这样的困难，高效的索引和紧凑的数据表示技术已经被强调。乘积量化（PQ）[16]及其变体[11，19，3，29，15，8，23，21]已被公认为最流行和最成功的解决方案，因为它们提供了数据压缩率和距离估计效率的重要因素。具体地，PQ将高维向量划分为M个不相交的子向量，并且*通讯作者更新粗中心常规提议图1：该图描述了常规倒排索引的粗中心更新与我们提出的方法的粗中心更新之间的差异。虽然传统的反转索引只考虑了粗中心的失真，但所提出的方法还考虑了粗中心更新中的细量化器的量化误差。将这些子向量独立地量化为K个子码字以这种方式，PQ利用具有小存储器占用的MK表示。此外，经验表明，基于PQ的技术提供了优于针对相同目标的并行研究的搜索质量，二进制哈希方法[2，27，14，28，13，9]倒排索引通过基于数据聚类的简单的短列表机制提供非穷举搜索。一个实用的可扩展搜索系统是通过以下过程实现的;在给定查询的情况下，倒排索引收集作为整个数据的一小部分的候选列表，并且PQ根据与紧凑码的估计距离对候选进行重新排序。在它们之间的这种可见的协同效应背后，在速度和内存方面都具有高可伸缩性，倒排索引将数据转换为量化友好的残差向量。12211适用于PQ。由于残差向量与其原始数据相比具有更紧凑的分布，因此PQ从中受益以进一步减少量化失真。在本文中，我们提出了一个新的问题，上述的紧密关系之间的粗（倒排索引）和细（产品）量化;为什么要分开学习？例如，粗量化器的变化显著影响残差矢量的分布因此，我们建议，粗和细量化器应联合和协作优化。为此，我们提出了一个联合优化的粗和细量化器的粗量化器的目标取代端到端的量化失真。最后，所设计的方案是正交于传统的倒排索引技术，而没有任何额外的时间和内存开销在编码，解码和查询时间。在几个基准上使用各种索引和编码技术的实验五、我们的主要贡献总结如下：• 我们强调的必要性，联合优化的粗和细量化。• 我们提出了一个联合优化的粗和细量化器的目标，取代粗量化器的失真的罚款量化器。• 我们提出的方法是正交的传统的倒排索引技术，而没有任何额外的时间开销在编码，解码和查询时间。• 实验结果表明，我们的方法实现了国家的最先进的性能超过五个大规模的人工神经网络数据集。2. 相关工作2.1. 产品量化乘积量化（PQ）[16]是一种矢量量化方法，旨在通过学习的代表性码字压缩数据通常，PQ用于需要大量内存大小的大规模数据集。 PQ分裂 将输入矢量分解成若干子矢量，并对每个子矢量应用矢量量化。此外，PQ允许有效计算未压缩查询和大量压缩向量之间的欧几里得距离，这被称为经由实例查找表的非对称距离原始PQ均匀地划分输入向量，而不考虑维度之间的相关性。这种方法可以很好地处理SIFT等结构化特征，但并不总是最好的方法。为了有效地管理输入向量，原始PQ论文提出对所有向量初步应用随机旋转以使维度不相关。此外，[17]的作者提出了优化通过一组具有方差平衡准则的反射来生成正交矩阵。最优乘积量化（OPQ）[11]是这些思想的扩展。OPQ计算旋转矩阵，通过公式化正交Procrustes问题[12]迭代地最小化量化虽然原始PQ将向量表示为来自子维度的码字的连接，但加法量化（AQ）[3]和复合量化（CQ）[29]将向量表示为其维度与原始向量相同的码字的总和这些基于加法的方法是PQ的推广，并且PQ是AQ的特殊情况，其中来自不同码本的码字是正交的。2.2. 带PQ的虽然PQ的具有非对称距离计算（ADC）的线性扫描提高了搜索速度，但是搜索仍然是穷举的。为了处理超大规模数据库，[16]提出了一种具有反向索引的搜索系统[25]，称为IVFADC。它组的数据库成几个不相交的子集的K-均值聚类，并允许加速搜索比较距离只有一小部分的数据库。对于每个粗略组残差向量，给定向量与其所属的组的中心之间的位移由PQ编码局部优化乘积量化（LOPQ）[19]通过独立地为数据库的每个子集局部定义乘积量化器来提高IVFADC的性能然而，它需要更大的内存消耗和减缓检索，因为它的多个量化器。倒排多重索引（IMI）[4]是IVFADC的多维扩展。IMI将数据空间分解成两个子空间的笛卡尔乘积，并独立地clusters每个子空间。然后，数据库的子集由来自每个子空间的索引对定义。通过索引的组合来表示子集使得能够在不增加查询时间的情况下对搜索空间进行更精细的划分。IVFADC编码残差矢量的思想类似于残差矢量量化（RVQ）[7]，其中来自先前量化步骤的残差被进一步递归地编码。它的改进版本[6，1]联合优化了跨不同步骤的精细然而，在IV-FADC和RVQ两者中，粗量化器和细量化器的优化保持独立，而它们是高度相关的。此外，联合优化技术仅限于穷举检索任务，而没有在处理大规模数据集的关键非穷举检索任务12212n=12∈∈··m m2Kk=1--迭代联合优化计算精细失真细畸变累积调整粗量化器更新精细量化器图2：所提出的粗量化器和细量化器的联合优化的图示。灰色圆圈表示数据点。黑色实线箭头和红色虚线箭头分别指示精细码字和精细失真蓝色箭头显示更新的方向。优化的整个过程由四个步骤组成。首先，利用所提出的目标计算精细失真（等式（1））。第9段）。然后，累积计算的精细失真（等式10）。第11段）。接下来，利用累积误差向量（等式10）调整粗量化器。第10段）。最后，用调整后的粗索引更新精细量化器。因此，粗量化器和细量化器被协同优化。3. 背景和动机3.1. 背景让我们简要回顾一下乘积量化（PQ）和IVFADC，并定义我们将在整个论文中使用的符号。 当D维数据库X={x n}N，xn∈RD和给定查询y∈RD，发现虽然产品量化器减少了检索时间显着，它是强烈建议结合PQ和倒排文件系统，以避免穷举搜索的大规模数据库。通过K-均值聚类学习具有K′个粗中心的粗量化器qc然后残差向量r（x）=x qc（x）利用数据库X及其最近的粗略中心y的最近邻被公式化如下：训练乘积量化器Qp，我们将其称为精细n=arg minn ∈{1，…，N}||.||.（一）量化河最后，y，x~是x的重构，定义如下：当量1需要O（DN）的时间复杂度和4DN字节的内存消耗。为了管理这种时间和内存使用，PQ提出了一种紧凑的代码编码方法，以权衡检索精度和资源。首先，给定D维向量XRD被分成M个子向量，X=[X1，… x M]，x iRD/M。接下来，通过对每个子空间m ∈ {1，…，M}到K个码字的集合C m={c m}K. 然后，将向量xn编码为PQx~=qp（x−qc（x））+qc（x）。（四）数据库向量之间的近似距离d（，）x和给定查询y的计算如下：d（x，y）≈d（x~，y）=d（x~-qc（y），y-qc（y）），（5）其中x和y在相同的粗簇中，并且qc（x）=qc（y）。码，q p（x，n）=[i1（x1），…i M（XM）]，如下所示：n训练乘积量化器qp：im（xm）= argminn||x−c||.（二）3.2. 动机现有的反向索引技术利用K均值来确定索引的长度。n n k12213m m2MKk∈{1，…K}nKk ∈{1，…K}表示编码矢量的丢失信息量的量化失真可以如下测量：对倒排索引进行聚类。K均值聚类的目标函数是找到使以下目标最小化的数据S的分区E（xn，C）=Σm=1min||x−c||.（三）argminΣΣ||x−µi||第二章（六）i=1x∈SiS12214（吨）我xj∈S（t）我我µ=x我CpcΣΣ||---||Σ{− }8200 180M8000算法1粗精联合优化过程78007600740072007000我们6800常规六千六百0一个二个三个四个五个六个七个八个九个十个步骤(a) SIFT-1M178M176M174M172M170M168M012345678九个10步骤(b) Conv-1M量化器输入：粗量化器qc，细量化器qp，粗中心数K′，比例因子s，学习集X，最大优化步数T。输出：优化的qc和qp。一曰：3：对于i= l，…没做4：具有固定精细量化器：图3：该图示出了传统方法和我们的方法的端到端量化误差。从预先训练的倒排索引系统开始，通过10次迭代进一步更新qc，并且针对每个步骤用更新的qc重新训练qp虽然粗和细量化器的联合优化改善了端到端的失真，但传统的目标仍然围绕初始误差。其中μi是集合Si的平均向量。训练K-means聚类由以下两个交替步骤组成S（t）={xp：||xp−µ（t）||2≤||xp−µ（t）||2j，1≤j≤K′}。5：UpdateCoarseQuantizer（）6：具有固定粗量化器：7：UpdateFineQuantizer（）第八章：第九章： 程序UPDATEC OARSEQ UANTIZER10：计算初始量化误差（等式11）。（3）第三章。11：whileTruedo12：对于i= l，…K′do13：计算平均误差向量（等式14）。第11段）。14：更新粗略中心（等式14）第10段）。15：重新分配步骤（等式15）（七）.16：计算量化误差（等式16）（3）第三章。i i j（七）17：如果量化误差收敛。然后分配步骤为每个向量找到最接近的聚类，以及中心更新步骤为最小化等式（1）。六、18：中断十九：二十： 程序UPDATEFINEQUANTIZER（t+1） 1Σ我|S|我（八）21：计算残差向量（等式21）第12段）。22：利用残差向量训练精细量化器反转索引或粗码字μ=[μ1，... 由K均值算法学习的[μ K ' ]在训练精细量化器中起着至关重要的作用，因为残差向量由其最近的粗码字定义。然而，K均值算法的该过程不能保证使精细量化器的量化误差最小化我们坚持粗量化器的目标函数不仅要考虑自身的误差，而且要考虑细量化器的误差。4. 我们的方法4.1. 最小化精细误差为了在考虑端到端量化失真的情况下对粗量化器进行优化，我们将粗量化器的目标函数替换为细量化器的目标函数。K'最小化矢量x与其对应的粗略中心qc（x）之间的误差。图1描述了传统的K均值目标函数（等式1）与传统的K均值目标函数（等式2）之间的差异。6)和所提出的一个（Eq. 第9段）。类似于K-均值，所提出的目标（等式10）是：9)通过两个交替步骤训练：分配和更新。我们修改了粗索引的更新步骤[c′1，…，c′K′]如下：c′（t+1）=c′（t）+s*Ei，（10）其中s是缩放因子，并且Ei是第i个粗略中心的平均误差E=1（x q（x））q（xq（x））（11）|SI|x∈Siarg minqp（x µi）（x µi）2（9）S我们的常规失真失真J12215i=1x∈Si它使残差矢量的量化误差r（x）=x−qc（x），而K-means算法仅我们从训练的K均值聚类开始初始状态在更新步骤之后（等式10），来自学习集合X的矢量在分配步骤中被用更新的粗量化器重新分配（等式11）。（七）.重复这些过程，直到所提出的目标函数收敛。12216DD×个C∈∈∈方法K′64位128位R@1R@10R@100R@1R@10R@100IVFADC我们二、十二、十0.29620.31080.70360.73010.95660.96520.47140.49640.90260.92770.99300.9921IVFOADCIVFOADC +我们二、十二、十0.29520.32140.71940.75550.96260.97150.47520.50010.91250.93110.99450.9930多D-ADCMulti-D-ADC +我们的二八二八0.30270.31810.72910.74820.96730.97660.48430.51290.92420.93380.99800.9973表1：SIFT-1 M数据集的方法K′64位128位R@1R@10R@100R@1R@10R@100IVFADC我们二、十二、十0.19980.20280.58140.59770.89590.90830.32140.33180.75800.78480.95850.9729IVFOADCIVFOADC +我们二、十二、十0.19780.20720.58280.60940.91090.92150.32280.33860.77830.80370.97060.9788多D-ADCMulti-D-ADC +我们的二八二八0.18330.19430.56860.58220.90320.91430.30900.32190.76040.79050.97020.9780表2：Conv-1 M数据集的比较。4.2. 粗、精定量机的联合优化。在传统的倒排索引系统中，粗量化器和细量化器是独立训练的。首先，粗量化器的K均值聚类算法进行训练。然后，使用粗索引与数据库向量之间的残差来训练细量化器。我们介绍了联合优化的粗，精量化器。我们的优化方案如图所示二、我们的目标函数（Eq. 9)更新粗量化器以最小化细量化器的量化误差。然后，粗索引和数据库向量之间的残差向量被重新定义如下：我们的目标的量化误差显著减小。然而，常规对象的失真保持在初始水平附近，而不管额外的聚类迭代。实验结果表明，本文的协同优化方法改进了传统方法。4.3. 反向多重索引倒排多索引（IMI）引入了一种新的倒排索引结构，它可以在不增加查询时间的情况下实现更精细的索引它将向量XRD分解为两半，其中X1R2和X2R2.然后，它独立地计算X1和X2上的倒排索引，并且产生两个粗码本U=[u1，…u [K]和r（x）（t+1）=x − q（t+1）。（十二）V=[v1，…v K']。 数据库分为K′K′不相交子集的数目，而比较器的数目粗中心和查询向量之间的isons仍然存在因此，我们可以通过重新训练精细量化器以利用重新定义的残差向量来定制来进一步最小化量化误差因此，还可以进一步优化粗量化器以最小化重新定义的细量化器的失真。优化的顺序是重新K′+ K′。所提出的方法可以应用到IMI正交。为此，更新步骤可以修改如下：迭代地进行。 我们的方法的整个过程是u（t+1）=u（t）+s*Eu，在算法1中总结。我我我v（t+1）=v（t）+s*Ev（十三）我们进行了一个实验，通过为粗量化器和重新定义的细量化器增加十次额外的迭代来测量量化失真，如图所示3.第三章。122172我我我其中Eu和Ev是来自X1，X2∈RD的平均误差向量，分别从相同的预训练的倒排索引系统开始12218×个--方法K′R@1R@10R@100IVFADC二一三0.09730.34100.6744我们0.11430.38480.7088多D-ADC二、十0.12530.37320.6786Multi-D-ADC +我们的0.13720.37690.6878多D-ADC二一一0.13170.36580.6360Multi-D-ADC +我们的0.14490.37900.6381方法K′R@1R@10R@100IVFADC二一三0.17380.38860.6361我们0.17510.39250.6527多D-ADC二、十0.16450.35380.5887Multi-D-ADC +我们的0.16660.35290.5907多D-ADC二一一0.17060.36030.5908Multi-D-ADC +我们的0.17340.36120.5931方法K′64位128位R@1R@10R@100R@1R@10R@100IVFADC我们二、十二、十0.07800.09000.21900.24100.48500.49900.13500.14700.34100.36700.66700.6830IVFOADCIVFOADC +我们二、十二、十0.13800.14700.36600.37800.70100.72900.18600.21000.54200.56100.87900.8770多D-ADCMulti-D-ADC +我们的二八二八0.12500.14300.36400.38800.73900.73700.23400.23900.56300.58200.88600.8960表3：GIST-1 M数据集的表4：SIFT-1B数据集的5. 评价5.1. 议定书我们在以下基准上评估我们的方法• SIFT-1 M [16]：它包含一百万个128维SIFT局部描述符[20]向量，用于数据库，100 K学习集和10K查询向量。• SIFT-1B [16]： 它 是 SIFT-1 M 数 据 集 的 扩 展 版本。它包含10亿个数据库向量，1亿个学习集。我们使用从学习集中随机采样的500K向量进行训练。• Deep-1B [5]：它包含来自GoogLeNet [26]架构的全连接层的96维DNN特征，用于Web上的十亿张图像。• Conv-1 M：我们从ImageNet数据库中随机抽取1M图像用于数据库，100 K用于学习集，10 K用于查询。然后，我们从VGG网络的conv5层提取512维全局平均池化特征[24]。• GIST-1 M [16] ： 960 维 全 局 颜 色 GIST 描 述 符[22]，它有一百万个数据库，500 K学习集和1 K查询向量。我们从学习集中随机选择了100K个向量进行训练。我们比较了粗量化器和细量化器的以下组合：表5：Deep-1B数据集• IVFADC：基于产品量化[16]的反转文件系统[25]• IVFOADC：IVFADC和OPQ [11]。• 我们的：提出了与IVFADC的粗量化和细量化的联合优化。• IVFOADC + Ours：建议使用IV-FOADC对粗量化和细量化进行联合优化[11]。• Multi-D-ADC：使用PQ反转多索引[4]。• Multi-D-ADC + Ours：建议使用Multi-D- ADC联合优化粗量化和细量化。检索性能通过平均召回率@R来测量，平均召回率@ R是在量化空间中的前R个最近邻居内具有未压缩空间的第一最近邻居除了消融研究和十亿规模数据集之外，我们固定了所有实验的超参数，对于乘积量化器，M=8，16和K=256，优化步骤的数量T = 10和缩放因子s =0。1 .一、数量对于IV，粗索引的值被设置为K′=210和K′=28分别在SIFT-1 M、Conv-1 M和GIST-1 M上的FADC和IMI。注意，IMI对于每个子空间具有K’个索引，并且数据库被划分为K’K’个不相交子集。 对于每个查询，我们保证数量候选人L至少50k。12219----方法LR@1R@10R@100IVFADC0.1M0.08090.25600.4248我们0.09330.27300.4330IVFADC0.5M0.09540.32550.6160我们0.11100.36220.6340IVFADC5M0.09850.34900.7147我们0.11530.39960.7685IVFADC10M0.09850.34930.7166我们0.11550.40020.7714多D-ADC1K0.07700.18310.2446Multi-D-ADC+我们的0.07910.19360.2600多D-ADC10K0.09790.26080.3604Multi-D-ADC+我们的0.10090.27350.3856多D-ADC0.1M0.12020.37000.6115Multi-D-ADC+我们的0.12980.37150.6260多D-ADC0.5M0.12500.37530.6774Multi-D-ADC+我们的0.13480.37890.6849多D-ADC5M0.12620.36890.6594Multi-D-ADC+我们的0.13930.37440.6700表6：SIFT-1B 64位编码的L消融研究5.2. 百万级数据集表. 1，表。2、桌子3份报告分别在SIFT-1 M、Conv-1 M和GIST-1 M上进行非穷举ANN搜索的召回@R通常，使用Ours的方法比不使用它的方法显示出更好的结果。例如，我们的、IVFOADC +我们的和Multi-D-ADC +我们的64位编码改进了其传统的对应物4。93%，8. 88%，5。09%，如表所示。1.此外，R@1分数的性能改善大于R@10和R@100。在SIFT-1 M和 Conv-1 M 数 据 集 上 ， 我 们 的 算 法 不 仅 优 于 IV-FADC，而且优于不结合OPQ的IVFOADC如表中所示。2，IVFOADC仅改善IVFADC 2。24%，而所提出的方法增加了其conventional对应3。77%和5。在64比特编码上，在R@10得分方面，分别具有和不具有OPQ的46实验结果表明，该方法与粗量化器和细量化器的各种组合一致地改善，因此它是正交于传统的反演指标系统。5.3. 十亿级数据集对于十亿级数据集，IVFADC 和IMI 分别设置K′=213和K′=210、211。最小候选者L的数量被设置为用于bil的一百万Lion Scale数据库表. 4、桌子5报告每-表7：SIFT-1 M 64位编码上K′的消融研究SIFT-1B和Deep-1B的性能比较。结果表明，该方法适用于十亿级数据集，其性能优于百万级数据集。例如，我们的R@1评分相对于IVFADC的改善为17。SIFT-1B为47%，而SIFT-1B为4。SIFT-1 M的93%。此外，Multi-D-ADC+Ours的性能增益为9。49%和10个。在K′=210和K′=211时，其平均转化率分别为02%和0 2%它们的增益大约是SIFT-1 M的两倍。5.4. 消融研究我们针对两个参数进行消融研究：粗索引的数量K’和候选的最小数量L。首先，我们在L = 0上验证我们的方法。01%，0. 05%、0. 1%、0. 5%、1%，同时固定其他参数。例如，1M个候选者为0。10亿规模数据库的1%。表中总结了SIFT-1B数据集上L的消融研究结果。6.无论L的大小，所提出的方法consistently提高了性能。特别地，就R@10和R@100而言，性能差距随着L增大而增大。例如，所提出的方法将R@100分数提高约7。65%，L=10M，而它是1。93%，2。92%，L=0。1M和L=0。分别为5M。第二，烧蚀研究的数量粗方法K′R@1R@10R@100IVFADC0.28380.69730.9517我们二九0.29850.72290.9574IVFOADC0.29180.70980.9587IVFOADC +我们的0.31700.73550.9683IVFADC0.29620.70360.9566我们二、十0.31080.73010.9652IVFOADC0.29520.71940.9626IVFOADC +我们的0.32140.75550.9715IVFADC0.29020.70210.9574我们二一一0.30860.73700.9684IVFOADC0.30900.72360.9657IVFOADC +我们的0.32900.75480.9774多D-ADC二七0.30270.72680.9677Multi-D-ADC +我们的0.31820.74530.9768多D-ADC二八0.30270.72910.9673Multi-D-ADC +我们的0.31810.74820.9766多D-ADC二九0.31660.74270.9723Multi-D-ADC +我们的0.32800.77030.9795多D-ADC二、0.33970.76360.979912220----| |方法K′固定 L，平均召回 固定L，平均值W固定 W，平均值召回固定W，平均值LIVFADC二八0.984012.65010.984854242.7205我们0.980512.25840.978656314.9056IVFADC二、十0.996548.83160.996352370.7237我们0.994248.59480.993352592.1584IVFADC二、十二0.9992181.72260.999056188.6639我们0.9983187.82000.998453996.8614表8：对SIFT-1 M 64位编码的修剪质量研究指数是在SIFT-1 M数据集上进行的。在IVFADC和IV-FOADC的方法上，当K′=29，210，211 时，当M=8，L′=50，000时，在IMI的方法上，当K′=27，28，29，210时，对该方法进行了验证。如表所示。7，所提出的方法一致地提高了性能，而不管粗索引K’的数量。5.5. 标引质量分析虽然该方法具有相同的时间复杂度与IVFADC，倒排表的不平衡例如，如果粗聚类具有不均匀的聚类大小，则一些查询应该多次重新计算其残差向量和查找表以保证足够数量的候选数据。为了验证所提出的方法不会损害倒排表的质量或平衡，我们进行了索引质量分析。我们测量具有固定最小候选大小L=50，000的所访问的倒排列表的平均数量W，以及具有固定数量的所检索的倒排列表W的候选的平均数量L。具有固定L或W的召回指示地面实况是否被包括在候选列表中，而不管其排名如何。表. 8显示了实验结果，并验证了所提出的方法不会损害粗索引的索引质量。在固定L和固定W两种情况下，IVFADC和Ours的平均召回率差异都远小于1%。被访问的倒排列表的平均数量W和候选的平均数量L相差小于5%。5.6. 管理费用分析注意，所提出的方法在编码、解码和搜索时间上没有任何额外的开销，但是训练时间。利用学习集X，其中X=N，所提出的方法的训练时间复杂度被描述为：方法KL搜索时间（ms）IVFADC我们二一三1M38.935639.2435IVFADC我们二一三5M178.7390176.1460多D-ADCMulti-D-ADC +我们的二、十1M44.405349.8225多D-ADCMulti-D-ADC +我们的二、十5M165.1767160.8871表9：SIFT-1B数据集上的平均检索时间表. 9展示了使用FAISS框架[18]在SIFT-1B数据集上每次查询的实际平均检索IVFADC和我们的搜索时间差可以忽略不计。6. 结论本文首先指出了传统的倒排索引系统中粗、细量化器的非协作优化问题。为了解决这个问题，我们已经提出了一个联合优化的粗和细量化器，通过将原始的目标函数的倒排索引的失真的罚款量化器。所提出的方法可以正交地应用于传统的倒排索引技术，包括IVFADC，IVFOADC，和IMI没有任何时间和存储器开销的编码，解码和搜索时间。我们已经评估了我们的方法与各种组合的粗和细量化器的几个基准，所提出的方法的优势是一致的基线证明。O（T*u *ND（K+K′））（14）其中T是优化步骤的数量，u是学习粗量化器的平均迭代次数。编码、解码和检索的时间和存储器消耗与IVFADC相同。这项工作得到了MCST/KOCCA（No.R2020070002 ） 、 MSIT/IITP （ 编 号 2020-0-00973 、2019-0-00421、2020-0-01821和2020-0-01550）、MSIT/NRF（No. NRF-2020R1F1A1076602）和 MSIT& KNPA/KIPoT （ Police Lab 2.0 ， No.210121M06）。12221引用[1] 艾烈夫，于俊青，吴泽斌，何云峰，关涛。优化的残差矢量量化，用于高效的近似最近邻搜索。MultimediaSystems，23（2）：169[2] 亚历山大·安多尼和彼得·因迪克。高维近似最近邻的近优散列算法。在2006年第47届IEEE计算机科学基础研讨会（FOCS[3] Artem Babenko和Victor Lempitsky。用于极端矢量压缩的加性量化。在Proceedings of the IEEE Conference onComputer Vision and Pattern Recognition，pages 931[4] Artem Babenko和Victor Lempitsky。倒排多指标. IEEETransactionsonpatternanalysisandmachineintelligence，37（6）：1247[5] Artem Babenko和Victor Lempitsky。深度描述符的十亿级 数 据 集 的 高 效 索 引 。 在 Proceedings of the IEEEConference on Computer Vision and Pattern Recognition，第2055-2063页[6] W-Y Chan，Smita Gupta和Allen Gersho。通过联合码本设 计 增 强 多 级 矢 量 量 化 。 IEEE Transactions onCommunications，40（11）：1693[7] 陈永健，关涛，王成。残差矢量量化的近似最近邻搜索Sensors，10（12）：11259[8] Xinyan Dai，Xiao Yan，Kelvin KW Ng，Jiu Liu，andJames Cheng.范数显式量化：最大内积搜索的向量量化改进。在AAAI人工智能会议论文集，2020。[9] Mayur Datar，Nicole Immorlica，Piotr Indyk，and VahabS Mirrokni.基于p-稳定分布的局部敏感哈希算法。在ProceedingsofthetwentyannualsymposiumonComputational geometry，pages 253[10] Jia Deng，Wei Dong，Richard Socher，Li-Jia Li，KaiLi，and Li Fei-Fei. Imagenet：一个大规模的分层图像数据库。2009年IEEE计算机视觉和模式识别会议，第248-255页[11] 葛铁铮，何开明，柯启发，孙建。优化的产品量化近似最近邻搜索。在Proceedings of the IEEE Conference onComputer Vision and Pattern Recognition，第2946-2953页[12] 龚云超，斯韦特兰娜·拉泽布尼克，阿尔伯特·戈多，和弗洛-伦特·佩龙宁.迭代量化：一个procrustean的方法来学习二进制代码的大规模图像检索。IEEE Transactionson Pattern Analysis and Machine Intelligence ， 35（12）：2916[13] 何开明，方文，孙建。K-means hashing：一种用于学习二进制紧凑代码的仿射保持量化方法。在Proceedings ofthe IEEE conference on computer vision and patternrecognition，pages 2938-2945，2013中。[14] Jae-Pil Heo 、 Youngwoon Lee 、 Junfeng He 、 Shih-FuChang和Sung-Eui Yoon。球形散列。IEEE计算机视觉和模式识别会议，2012。[15] Jae-Pil Heo，Zhe Lin，and Sung-Eui Yoon.距离编码乘积量化。在IEEE计算机视觉和模式识别会议上，2014年。[16] Herve Jegou、Matthijs Douze和Cordelia Schmid。最近邻搜索的乘积量化。IEEE Transactions on Pattern Analysisand Machine Intelligence，33（1）：117[17] 她的名字是MatthijsDouzeCordeliaSchmid和Patrick Pérez。将局部描述符聚集成紧凑的图像表示。2010年IEEE计算机协会计算机视觉和模式识别会议，第3304- 3311页。IEEE，2010。[18] Je f fJohnson，MatthijsDouze，andHer ve'Je'gou. 用gpu进行十亿级相似性搜索。IEEE Transactions on Big Data，2019。[19] 扬尼斯·卡兰蒂迪斯和扬尼斯·阿弗里斯。局部优化的产品量化近似最近邻搜索。在Proceedings of the IEEEConference on Computer Vision and Pattern Recognition，第2321-2328页[20] 大卫·G·洛从尺度不变关键点中提取独特的图像特征。国际计算机视觉杂志，60（2）：91[21] Julieta Martinez，Joris Clement， Holger H Hoos，andJames J Little.再谈加性量化。在European Conference onComputer Vision中，第137-153页施普林格，2016年。[22] 奥德·奥利瓦和安东尼奥·托拉尔巴对场景的形状进行建模：空间包络的整体表示。国际计算机视觉杂志，42（3）：145-175，2001。[23] Ezgi Can Ozan、Serkan Kiranyaz和Moncef Gabbouj。近似 最 近 邻 搜 索 的 竞 争 量 化 。 IEEE Transactions onKnowledge and Data Engineering，28（11）：2884[24] Karen Simonyan和Andrew Zisserman用于大规模图像识别的深度卷积网络。在Yoshua Bengio和Yann LeCun，编辑，第三届学习表征国际会议，ICLR 2015，美国加利福尼亚州圣地亚哥，2015年5月7日至9日，会议跟踪程序，2015年。[25] 约瑟夫·西维克和安德鲁·齐瑟曼。视频google：一种用于视频对象匹配的文本检索方法。在null中，第1470页。IEEE，2003年。[26] Christian Szegedy ， Wei Liu ， Yangqing Jia ， PierreSermanet ， Scott Reed ， Dragomir Anguelov ， DumitruErhan，Vincent Vanhoucke，and Andrew Rabinovich.更深的回旋。在IEEE计算机视觉和模式识别会议论文集，第1-9页[27] Antonio Torralba，Rob Fergus，and Yair Weiss.小代码和大型图像数据库进行识别。2008年IEEE计算机视觉和模式识别会议，2008年。[28] Yair Weiss 、 Antonio Torralba 和 Rob Fergus 。 光 谱 散列。神经信息处理系统的进展，第1753-1760页，2009年[29] Ting Zhang，Chao Du，and Jingdong Wang.近似最近邻搜