CN120067177A - 查询方法、处理器、处理系统、存储介质和程序产品 - Google Patents

Abstract

本申请提供了一种查询方法、处理器、处理系统、存储介质和程序产品，可以应用于数据查询技术领域。该查询方法包括：接收查询指令；对查询指令对应的查询数据进行压缩得到简化向量；从索引形状图中查询得到与简化向量匹配的目标索引向量；其中，索引形状图表示K个索引向量，K个索引向量是对索引库中的S个源数据进行压缩得到的，S、K为正整数，且S≥K；从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据；根据查询数据与多个初选源数据的相似度，得到与查询数据匹配的目标源数据。该查询方法可以节约存储空间，缩小查询范围，提高查询效率。

Description

查询方法、处理器、处理系统、存储介质和程序产品

技术领域

本申请涉及数据查询技术领域，更具体地涉及一种查询方法、处理器、处理系统、存储介质和程序产品。

背景技术

索引查询是一种通过索引结构检索数据的方法，其通常是预先构建索引结构，当用户发起查询请求时，利用索引结构从索引库定位到满足查询请求的数据，再将满足查询请求的数据返回给用户。

在实现本申请构思的过程中，发明人发现相关技术中至少存在如下问题：相关索引查询方法通常是将所要查询的数据与索引库中的数据项进行遍历匹配，例如逐个比较所要查询的数据与索引库中存储的每一个数据项，直到找到符合条件的结果为止，但是当索引库中的数据量很大时，这种遍历查询的方式会导致查询效率较低，且索引库中的数据项占用的存储空间较大。

发明内容

鉴于上述问题，本申请提供了查询方法、处理器、处理系统、存储介质和程序产品。

根据本申请的第一个方面，提供了一种查询方法，包括接收查询指令；对查询指令对应的查询数据进行压缩得到简化向量；从索引形状图中查询得到与简化向量匹配的目标索引向量；其中，索引形状图表示K个索引向量，K个索引向量是对索引库中的S个源数据进行压缩得到的，S、K为正整数，且S≥K；从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据；根据查询数据与至少一个初选源数据的相似度，得到与查询数据匹配的目标源数据。

本申请的第二方面提供了一种处理器，包括：片上计算组件，用于执行查询方法；片上存储单元，用于存储索引形状图。

本申请的第三方面提供了一种处理系统，包括：第一处理器，用于从索引形状图中查询得到与简化向量匹配的目标索引向量；其中，索引形状图表示K个索引向量，K个索引向量是对索引库中的S个源数据进行压缩得到的，S、K为正整数，且S≥K；第二处理器，用于对查询指令对应的查询数据进行压缩得到简化向量、从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据，以及根据查询数据与至少一个初选源数据的相似度，得到与查询数据匹配的目标源数据。

本申请的第四方面还提供了一种计算机可读存储介质，其上存储有计算机程序或指令，上述计算机程序或指令被处理器执行时实现上述方法的步骤。

本申请的第五方面还提供了一种计算机程序产品，包括计算机程序或指令，上述计算机程序或指令被处理器执行时实现上述方法的步骤。

根据本申请的实施例，通过对查询指令对应的查询数据进行压缩得到简化向量，可以降低查询向量维度，减少计算量，提高查询效率。通过将源数据压缩为索引向量，可以减少存储开销，提高索引构建速度。通过索引形状图表示索引向量，从索引形状图中查询得到与简化向量匹配的目标索引向量，再从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据，可以节约存储空间，并且可以缩小查询范围，提高查询效率。由此，至少部分地解决了相关查询方法中查询效率较低、存储开销较大的技术问题，实现了节约存储空间、提高查询效率的技术效果。

附图说明

通过以下参照附图对本申请实施例的描述，本申请的上述内容以及其他目的、特征和优点将更为清楚，在附图中：

图1示出了根据本申请实施例的查询方法、处理器、处理系统、存储介质和程序产品的应用场景图。

图2示出了根据本申请实施例的查询方法的流程图。

图3示出了根据本申请实施例的基于K个索引向量构建索引二叉树的示意图。

图4示出了根据本申请实施例的索引二叉树中多种子树形状的示意图。

图5示出了根据本申请实施例的子树形状与形状编码的对应关系的示意图。

图6示出了根据本申请实施例的生成索引形状图的示意图。

图7示出了根据本申请实施例的叶节点与源数据集合的关联关系的示意图。

图8示出了根据本申请实施例的生成携带偏移信息的索引形状图的示意图。

图9示出了根据本申请实施例的片上计算组件和片上存储单元的结构示意图。

图10示出了根据本申请实施例的第一处理器和第二处理器的系统交互图。

图11示出了根据本申请另一实施例的查询方法的流程图。

图12示出了根据本申请另一实施例的第一处理器和第二处理器的系统交互图。

图13示出了根据本申请实施例的适于实现查询方法的电子设备的方框图。

具体实施方式

以下，将参照附图来描述本申请的实施例。但是应该理解，这些描述只是示例性的，而并非要限制本申请的范围。在下面的详细描述中，为便于解释，阐述了许多具体的细节以提供对本申请实施例的全面理解。然而，明显地，一个或多个实施例在没有这些具体细节的情况下也可以被实施。此外，在以下说明中，省略了对公知结构和技术的描述，以避免不必要地混淆本申请的概念。

在此使用的术语仅仅是为了描述具体实施例，而并非意在限制本申请。在此使用的术语“包括”、“包含”等表明了特征、步骤、操作和/或部件的存在，但是并不排除存在或添加一个或多个其他特征、步骤、操作或部件。

在此使用的所有术语（包括技术和科学术语）具有本领域技术人员通常所理解的含义，除非另外定义。应注意，这里使用的术语应解释为具有与本说明书的上下文相一致的含义，而不应以理想化或过于刻板的方式来解释。

在使用类似于“A、B和C等中至少一个”这样的表述的情况下，一般来说应该按照本领域技术人员通常理解该表述的含义来予以解释（例如，“具有A、B和C中至少一个的系统”应包括但不限于单独具有A、单独具有B、单独具有C、具有A和B、具有A和C、具有B和C、和/或具有A、B、C的系统等）。

索引查询是一种通过索引结构检索数据的方法，索引查询方法例如包括对向量数据的索引查询，例如：可以通过特征向量提取处理将文本、图像、语音、视频等非结构化数据转换为向量数据，其中向量数据是一种数学表达形式，其通过一组有序数值来刻画一个对象或数据点。向量数据可以包括一维数组，数组中的元素一般以数值形式呈现，例如以如浮点数形式呈现，这些数值能够精确体现对象或数据点在多维空间中的位置、特征以及属性。在将非结构化数据转换为特征向量后，可以将特征向量存储在索引库中。当用户需要查某些数据时，可以从索引库中查找与查询内容对应的若干个特征向量。

相关构建向量数据索引结构的方法包括基于树的方法、基于哈希的方法、基于量化的方法、以及基于图的方法等。

具体地，基于树的索引方法例如包括KD树方法（K - Dimensional Tree，缩写为KD-Tree），其通过将数据点递归地划分到不同的子空间中，不断地选择一个维度并根据该维度上的数值将数据点分为左右两个子树，使得每个子树中的数据点在某个维度上具有一定的有序性。

基于哈希的索引方法例如包括局部敏感哈希（Locality Sensitive Hashing，缩写为LSH）等，其通过哈希函数将连续的实值转化为离散值，并以向量间的相似性作为关键度量指标，对向量进行分割处理，从而将各个向量依据相似程度被归入不同的哈希桶内。

基于量化的索引方法例如包括乘积量化（Product Quantization，缩写为PQ）、倒排PQ乘积量化（Inverted Index Product Quantization，缩写为IVFPQ）等方法，其通过将原始向量分解成更小的子向量，然后简化每个块的表示从而缩小值的潜在范围。

基于图的索引方法例如包括导航网（Navigation Net，缩写为NN-Net）、分层导航小世界（Hierarchical Navigable Small World Graphs，缩写为HNSW）等方法，其通过在数据点之间建立导航关系，根据导航关系查找数据。

但是，基于树的索引方法由于随着维度的增加，树的节点数量会快速膨胀，导致索引的内存开销增加，因此不适用于高维向量的数据检索。基于哈希的索引方法依赖于哈希函数的设计，可能会出现哈希冲突，使相似性不高的多组向量映射到同一哈希桶中，导致检索效率降低，且哈希函数的选择和计算增加索引构建的计算开销。而基于量化的索引方法的召回率较低，具体而言基于量化的索引方法的检索精度较低，一些真正相似的向量可能无法被检出。基于图的索引方法的构建过程相对较慢，不适用于大规模数据集，且参数调优困难，使用难度较高。

此外，在实现本申请构思的过程中，发明人还发现相关技术中至少存在如下问题：向量数据通常具有高维特性，例如通过深度学习模型提取的特征向量可能具有数百甚至数千个维度。并且向量数据通常数据量很大，例如对于一个包含数百万张图像的图像库，需要将每张图像都提取为一个特征向量。此外向量数据通常需要实时处理，也即在短时间内完成查询和计算。但是，相关索引查询方法通常是将查询数据与索引库中的向量数据进行遍历匹配，需要将所要查询的数据与索引库中存储的每一个数据进行逐个比较，在面对高维、数据量较大的向量数据时，这种遍历查询的方法的查询效率较低，难以满足实时处理的要求，且索引库中的数据项占用的存储空间较大。此外，向量数据更新频率较高，而适配向量数据的索引结构通常颇为复杂。每当向量数据更新时，往往需要重新构建索引结构，从而增加了索引更新与维护的开销。同时，向量数据分布常呈现不均匀态势，例如存在高密度与稀疏区域，不均匀态势会致使查询性能大幅波动，难以维持稳定高效的查询状态。

有鉴于此，本申请的实施例提供了一种查询方法，包括接收查询指令；对查询指令对应的查询数据进行压缩得到简化向量；从索引形状图中查询得到与简化向量匹配的目标索引向量；其中，索引形状图表示K个索引向量，K个索引向量是对索引库中的S个源数据进行压缩得到的，S、K为正整数，且S≥K；从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据；根据查询数据与多个至少一个初选源数据的相似度，得到与查询数据匹配的目标源数据。

图1示出了根据本申请实施例的查询方法、处理器、处理系统、存储介质和程序产品的应用场景图。

如图1所示，根据该实施例的应用场景100可以包括第一处理器101、第二处理器102。第一处理器101与第二处理器102之间可以进行数据交互，以执行查询方法。

例如：在接收到查询指令后，第二处理器102可以将查询指令对应的查询数据进行压缩得到简化向量，以使得第一处理器101可以根据简化向量从索引形状图中查询得到与简化向量匹配的目标索引向量。进一步地，第二处理器102可以根据目标索引向量，从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据，第二处理器102还可以根据查询数据与至少一个初选源数据的相似度，得到与查询数据匹配的目标源数据。

以下将基于图1描述的场景，通过图2~图11对本申请实施例的查询方法进行详细描述。

图2示出了根据本申请实施例的查询方法的流程图。

如图2所示，该实施例的查询方法包括操作S210~操作S250。

在操作S210，接收查询指令。

在操作S220，对查询指令对应的查询数据进行压缩得到简化向量。

在操作S230，从索引形状图中查询得到与简化向量匹配的目标索引向量。其中，索引形状图表示K个索引向量，K个索引向量是对索引库中的S个源数据进行压缩得到的，S、K为正整数，且S≥K。

在操作S240，从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据。

在操作S250，根据查询数据与至少一个初选源数据的相似度，得到与查询数据匹配的目标源数据。

根据本申请的实施例，为了提高从数据库中查询数据的效率，可以为数据库中的数据构建索引结构，得到索引库。当用户需要从数据库中查询目标数据时，可以利用索引库定位目标数据的位置。

例如：在目标跟踪领域，需要从图像中提取目标对象的特征信息。对于一个包含100万张图像的数据库，可以为100万张图像构建索引结构，具体可以是将数据库中的每张图像都转换为一个图像特征向量，并将图像特征向量以预定形式存储在索引库中。当用户需要查询与图像A相同或相似的图像时，可以通过索引库定位与图像A相同或相似的图像。具体地，图像中通常包括多维度信息，例如包括颜色信息、纹理信息等。在将图像都转换为向量后，图像中的多维度信息会可能直接映射到向量的某些维度。因此，索引库中的图像特征向量可以表征图像中的多维度信息。当查询与图像A相同或相似的图像时，可以通过索引库中图像特征向量所表征的图像中的多维度信息，确定与图像A相同或相似的图像。

再例如：在智能客服领域，通常会进行文本检索或语音检索，以便从文本数据库或语音数据库中查找与用户问题最匹配的答案。可以将文本数据库中的多条文本数据转换为多个文本特征向量，并将文本特征向量存储至预先构建的索引库中。在需要从文本数据库中检索与用户问题较为相关的文本时，可以从索引库中读取多个文本特征向量，并定位与用户问题较为相关的文本特征向量，再基于定位到的文本特征向量确定与用户问题较为相关的文本数据。

具体地，在操作S210，用户可以输入查询指令，查询指令用于表征用户所要查询的内容。例如：用户上传一张图像A，需要查询与图像A相同或相似的图像。在此情况下，查询指令可以表征用户需要查询与图像A相同或相似的图像。

在操作S220，可以将查询指令转换为向量数据的形式，得到查询指令对应的查询数据。例如可以通过预训练的语言模型将查询指令转换为向量数据，但不局限于此，将查询指令转换为向量数据的方式可以根据实际需求设定，在此不作限定。

具体地，查询指令可以体现N个维度的信息，例如体现图像、语音或文本的多个维度的信息。查询数据可以为N维向量的形式。N维向量为查询指令体现在N个维度的特征值，特征值包括以下至少之一：图像特征、语音特征、文本特征。例如：在查询指令用于体现图像的多维度信息的情况下，N维向量包括以下至少之一：图像纹理，图像颜色，图像亮度，图像中目标物体的形状，图像深度，图像灰度。或者，在查询指令用于体现语音的多维度信息的情况下，N维向量包括以下至少之一：语音音量，语音韵律，语音语速，语音语调，语音音色。再或者，在查询指令用于体现文本的多维度信息的情况下，N维向量包括以下至少之一：文本语义，文本长度，文本段落结构，文本中目标词语的词频。

进一步地，由于查询数据的向量维度通常较高，计算复杂度较高，因此可以对查询数据进行压缩，得到简化向量。对查询数据进行压缩例如包括降低查询向量维度、对查询向量各维度上的数据做二分处理等。通过对查询数据进行压缩得到简化向量，可以减少计算量，提高查询效率。

在操作S230，可以将数据库中的多个数据转换为向量数据的形式，得到S个源数据，将数据库中的多个数据转换为向量数据的方式可以根据实际需求设定，在此不作限定。由于数据库中通常包括大量数据，因此转换后会得到大量向量数据，且向量数据的维度通常较高，而直接对大量高维向量数据构建向量索引的计算开销较大，同时高维向量数据的索引数据也会占用较大的存储空间。因此，为了减少存储开销，提高索引构建速度，可以对S个源数据进行压缩，得到K个索引向量。

具体地，对S个源数据进行压缩例如可以包括：首先对S个源数据进行降维处理，得到S个降维处理后的向量数据；再对S个降维处理后的向量数据进行二值化处理，得到S个索引向量，在此情况下S等于K。

其中，降维处理是通过预定数学变换方法将高维数据映射到低维空间，以提高样本密度和计算效率。降维处理所采用的预定数学变换方法例如包括主成分分析（PrincipalComponent Analysis，缩写为PCA）、多维缩放（MultiDimensional Scaling，缩写为MDS）、等距特征映射（Isometric Mapping，缩写为ISOMAP）、线性判别分析（Linear DiscriminantAnalysis，缩写为LDA）等，预定数学变换方法可以根据实际需求设定，在此不作限定。

通过二值化处理对降维处理后的向量数据进行量化编码。二值化处理包括根据预设数值将降维处理后的向量数据中多个维度的数据分别转换为第一值或第二值，具体可以包括将取值大于预设数值的数据转换为第一值，将取值小于等于预设数值的数据转换为第二值。第一值例如可以为1，第二值例如可以为0，二值化处理后得到的向量可以看作是由0和1构成的数值序列。

预设数值可以基于降维处理后的向量数据中的多个维度数值计算得到，例如预设数值可以包括多个维度数值的中位数，也可以包括多个维度数值的均值，还可以通过其他方式对多个维度数值计算得到，在此不作限定。

具体地，对S个源数据进行压缩例如也可以是包括：先对S个源数据进行降维处理，得到S个降维处理后的向量数据；再对S个降维处理后的向量数据进行二值化处理，得到S个二值化向量；然后对S个二值化向量进行相同向量合并处理，得到K个索引向量，在此情况下S大于K。其中，降维处理和二值化处理的方式参见操作S230的实施例中降维处理和二值化处理的方式，在此不再赘述。

其中，对S个二值化向量进行相同向量合并处理包括：提取S个二值化向量中的相同二值化向量，并将相同二值化向量作为一个索引向量，索引向量的值与相同二值化向量的值相同。例如在S个二值化向量中，有N个二值化向量的值均为（0,0,1），则可以将这N个二值化向量作为一个索引向量，索引向量的值为（0,0,1）。

S个源数据中可能包括相同的数据，在对这些相同的数据分别降维和二值化处理后会得到重复的二值化向量，如果直接对这些重复的二值化向量进行处理，会造成不必要的计算和存储资源的浪费。而通过对S个二值化向量进行相同向量合并处理，可以将相同二值化向量作为一个索引向量进行处理，从而降低计算量，节省存储资源。

进一步地，在得到K个索引向量后，可以通过索引形状图的形式表示K个索引向量。索引形状图包括多个形状节点，多个形状节点之间通过有向边连接。有向边可以表征不同维度的数值，索引向量中多个维度的数值可以通过多个有向边表示。

例如：某个索引向量为（1,0,0），可以通过索引形状图中的形状节点1与形状节点2之间的有向边、形状节点2与形状节点3之间的有向边、形状节点3与形状节点4之间的有向边表示。

具体地，从索引形状图中查询得到与简化向量匹配的目标索引向量可以包括：遍历查询多个形状节点之间的有向边，将有向边所表征的不同维度的数值与简化向量中相应维度的数值进行匹配，将与简化向量完全匹配的索引向量作为目标索引向量。其中，与简化向量完全匹配可以包括目标索引向量各维度的数值与简化向量相应维度的数值完全相同。

例如：简化向量为（1,0,0），可以遍历查询有向边，确定形状节点1与形状节点2之间的有向边、形状节点2与形状节点3之间的有向边、形状节点3与形状节点4之间的有向边所表示的索引向量也为（1,0,0），与简化向量各维度的值完全相同，因此可以将该索引向量作为与简化向量匹配的目标索引向量。

具体地，从索引形状图中查询得到与简化向量匹配的目标索引向量还可以包括：将与简化向量部分匹配的索引向量作为目标索引向量。具体地，K个索引向量中可能不存在与简化向量完全相同的向量，在此情况下，可以将与简化向量部分匹配的索引向量作为目标索引向量。其中，与简化向量部分匹配可以包括目标索引向量与简化向量的相似度满足预设数值范围，预设数值范围可以根据实际需求设定。

例如：简化向量为（1,0,0），从索引形状图中查询到某个索引向量为（1,0,1），由于该索引向量与简化向量相似度较高，因此可以将该索引向量作为与简化向量匹配的目标索引向量。

进一步地，在操作S240，源数据与对源数据进行压缩得到的索引向量之间存在对应关系，一个索引向量对应于至少一个源数据。例如：在对S个源数据依次进行降维处理和二值化处理得到K个索引向量的情况下，一个索引向量可以对应一个源数据；而在对S个源数据依次进行降维处理、二值化处理、相同向量合并处理得到K个索引向量的情况下，一个索引向量有可能会对应多个源数据。在确定与简化向量匹配的目标索引向量后，将与目标索引向量存在对应关系的源数据作为初选源数据。

由于目标索引向量是对至少一个初始源数据进行压缩得到的，简化向量是对查询数据进行压缩得到的，且目标索引向量与简化向量相匹配，因此，至少一个初始源数据与查询数据之间也存在匹配关系。

例如：目标索引向量是对源数据v1和v2压缩得到的，也即初始源数据包括源数据v1和v2，简化向量是对查询数据压缩得到的。由于目标索引向量与简化向量相匹配，例如目标索引向量与简化向量的值完全相同，因此查询数据也与源数据v1和v2相匹配，例如查询数据与源数据v1和v2的值完全相同。

一方面，在索引向量数量较多的情况下，直接存储索引向量会占用较大存储空间，通过对源数据进行压缩得到索引向量，再通过索引形状图表示索引向量，索引形状图相比于索引向量会占用较少的存储空间，从而可以节省存储空间。

另一方面，如果直接将查询数据与索引库中的源数据遍历匹配，在索引向量数量较多的情况下遍历过程会增大计算开销，导致查询效率较低。而通过将查询数据压缩为简化向量，将源数据压缩为索引向量，再通过索引形状图表示索引向量，在查询时先从索引形状图中查到与简化向量匹配的目标索引向量，再确定与目标索引向量对应的初选源数据，从而可以从大量源数据中初步筛选出与查询数据相对应的少量的初选源数据，后续仅需从少量的初选源数据中确定与查询数据相匹配的源数据即可，由此，与直接将查询数据与索引库中的数据进行遍历匹配相比，可以缩小匹配范围，提高查询效率。

根据本申请的实施例，在操作S250，为了进一步从至少一个初选源数据中筛选出与查询数据相匹配的源数据，可以计算查询数据分别与至少一个初选源数据之间的向量距离，得到查询数据与至少一个初选源数据的相似度，向量距离越近，表明查询数据与初选源数据的相似度越高。计算查询数据与初选源数据之间的向量距离的方法例如可以包括计算欧式距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离，也可以包括计算余弦相似度和距离、半正矢距离、汉明距离、杰卡德指数和距离等，具体计算查询数据与初选源数据之间的向量距离的方法可以根据实际需求设定，在此不作限定。可以将与查询数据的相似度大于预设阈值的初选源数据作为目标源数据。

通过对查询指令对应的查询数据进行压缩得到简化向量，可以降低查询向量维度，减少计算量，提高查询效率。通过将源数据压缩为索引向量，可以为了减少存储开销，提高索引构建速度。通过索引形状图表示索引向量，从索引形状图中查询得到与简化向量匹配的目标索引向量，再从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据，可以节约存储空间，缩小查询范围，提高查询效率。

根据本申请的实施例，对查询指令对应的查询数据进行压缩得到简化向量包括：对查询数据进行降维处理，得到降维数据；对降维数据进行二值化编码处理，得到简化向量。

具体地，查询数据通常为高维向量，直接对高维向量进行处理的计算复杂度较高，计算过程较为耗时。可以对查询数据进行降维处理，通过降维处理将高维的查询数据映射到一个低维空间中，减少了计算时所需考虑的维度数，从而降低了计算复杂度，提高了计算效率。可以通过主成分分析法、多维缩放法、等距特征映射法、线性判别分析法等方法对查询数据进行降维处理，也可以根据实际需求采用其他方法查询数据进行降维处理，对于查询数据进行降维处理的方法在此不作限定。对降维数据进行二值化编码处理可以包括将降维数据中多个维度的数值分别转换为二进制形式，例如可以转换为0或1。

通过对查询数据进行降维处理得到降维数据，再对降维数据进行二值化编码处理，得到简化向量，可以降低查询数据维度、降低数据复杂性，从而可以在从索引形状图中查询与简化向量匹配的目标索引向量时，减少计算量，提高查询效率。

根据本申请的实施例，简化向量包括第一值和第二值；对降维数据进行二值化编码处理包括：对降维数据包括的多维子数据进行数值计算，得到参考数值；基于多维子数据各自与参考数值之间的数值偏差，生成多维子数据各自对应的第一值或第二值。

具体地，对降维数据包括的多维子数据进行数值计算具体可以包括计算多维子数据的中位数，或计算多维子数据的平均值，可以将多维子数据的均值或平均值作为参考数值。进一步地，分别计算多维子数据与参考数值之间的差值，得到数据偏差。在数据偏差为正值的情况下，可以生成与子数据对应的第一值，在数据偏差为零或负值的情况下，可以生成与子数据对应的第二值。

例如：第一值为1，第二值为0。针对n维的降维数据，可以计算n个维度上数值的均值，并将计算得到的均值作为参考数值。针对n个维度上数值，在某维度上的数值与参考数值的数值差值为正数，也即该维度数值大于均值的情况下，将该维度的数值编码为1，在该维度数值与参考数值的数值差值为零或负数，也即该维度数值小于等于均值的情况下，将该维度的数值编码为0，由此可以将降维数据转换为由0和1组成的数值序列。

通过二值化处理，可以将降维数据转换为更简单的结构，从而降低降维数据的复杂性，进而提高从索引形状图中查询与简化向量匹配的目标索引向量时的查询效率。

根据本申请的实施例，查询方法还包括基于K个索引向量构建索引二叉树；对索引二叉树进行节点压缩得到索引形状图。

图3示出了根据本申请实施例的基于K个索引向量构建索引二叉树的示意图。

如图3所示，针对3个n维源数据v1、v2、v3，其中n大于或等于4，首先可以进行降维处理，得到降维处理后的4维向量数据，包括降维数据v1′、v2′、v3′，再对v1′、v2′、v3′进行二值化处理，得到索引向量v1′′、v2′′、v3′′，基于索引向量v1′′、v2′′、v3′′构建索引二叉树，索引二叉树例如可以包括多个节点，节点之间的边可以表征索引向量中某一维度的数值。例如，图3中索引二叉树的根节点左侧的多个边依次可以表示：第一维度的数值为0、第二维度的数值为0、第三维度的数值为1、第四维度的数值为1。

基于多个多维向量构建得到的索引二叉树中的节点数量会明显比多维向量的数量多，例如图3中的索引向量数量为3个，基于索引向量构建得到的索引二叉树的节点数量为11个。并且，索引二叉树节点的数量会随着索引向量个数和单个索引向量的维数的增加而显著增加，因此针对大量高维向量数据构建和存储索引二叉树所需的内存开销会相当大，导致存储资源有限的处理器难以容纳数量庞大的索引二叉树节点。因此，可以对索引二叉树进行节点压缩得到索引形状图，索引形状图中的节点数量得到了较大幅度减少，降低了内存占用量。

通过基于K个索引向量构建索引二叉树，再对索引二叉树进行节点压缩得到索引形状图，可以得到节点数量较少的索引形状图，从而可以降低内存占用量。

根据本申请的实施例，K个索引向量各自包括N维第一数值，N为正整数；索引二叉树被划分为N级的多个树节点和树节点之间的关联边，关联边表征N维第一数值；索引形状图被划分为N级的多个形状节点和形状节点之间的有向边，有向边表征N维第一数值；索引形状图中一个形状节点表示索引二叉树中具有相同子树形状的多个树节点。

例如：索引二叉树包括多个树节点，以及树节点之间的关联边。其中，多个树节点被划分为N级，例如根树节点为第一级树节点、与根树节点直接相连的树节点为第二级树节点、与第二级树节点直接相连的树节点为第三级树节点，依此类推。其中，第一级树节点与第二级树节点之间的关联边用于表征索引向量中的第一维数值，第二级树节点与第三级树节点之间的关联边用于表征索引向量中的第二维数值，依此类推。

例如图3中所示，有两个第二级树节点与第一级树节点相连，两个第二级树节点与第一级树节点之间的两条关联边均可表征索引向量中的第一维数值，例如第一级树节点与左边的第二级树节点之间的关联边表征索引向量中的第一维数值为0、第一级树节点与右边的第二级树节点之间的关联边表征索引向量中的第一维数值为1。进一步地，左边的第二级树节点与第三级树节点之间的关联边表征索引向量中的第二维数值为0、右边的第二级树节点与第三级树节点之间的关联边表征索引向量中的第二维数值为1。

进一步地，索引二叉树中包括多种子树形状。

图4示出了根据本申请实施例的索引二叉树中多种子树形状的示意图。

如图4所示，索引二叉树中包括子树形状1~子树形状5。

进一步地，索引二叉树中的多个树节点可能对应相同的子树形状，比如图4中索引二叉树的最左侧的第三级树节点和最右侧的第三级树节点均对应子树形状1。可以通过索引形状图中的一个形状节点来表示具有相同子树形状的多个树节点，例如通过索引形状图中的一个形状节点来表示图4中索引二叉树的最左侧的第三级树节点和最右侧的第三级树节点。

具体地，索引形状图中包括多个形状节点，形状节点之间通过有向边连接。其中，多个形状节点被划分为N级，例如根形状节点为第一级形状节点、与根形状节点直接相连的形状节点为第二级形状节点、与第二级形状节点直接相连的形状节点为第三级形状节点，依此类推。其中，第一级形状节点与第二级形状节点之间的有向边用于表征索引向量中的第一维数值，第二级形状节点与第三级形状节点之间的有向边用于表征索引向量中的第二维数值，依此类推。

通过索引形状图中一个形状节点表示索引二叉树中具有相同子树形状的多个树节点，可以对索引二叉树进行节点压缩，从而降低索引形状图所占用的存储空间。

根据本申请的实施例，对索引二叉树进行节点压缩得到索引形状图包括：确定树节点的形状编码，形状编码用于表征树节点的子树形状类别；将具有相同形状编码的树节点合并，生成索引形状图。

图5示出了根据本申请实施例的子树形状与形状编码的对应关系的示意图。

如图5所示，索引二叉树中可以包括不同的子树形状，不同的子树形状对应不同的形状编码。此外，索引二叉树中的某些位置的节点可能不存在，也即存在空节点，进一步还可以对索引二叉树中的空节点统一设置一个编号，得到与空节点对应的形状编码，或者不对空树节点进行编号。

进一步地，不同子树形状可能对应相同或不同的子树高度，子树高度用于表征针对某一形状的子树，从该子树的根节点到该子树最远节点的最长路径上的节点数。例如编号为2和3的子树形状的子树高度为2，编号为4和5的子树形状的子树高度为3，编号为6的子树形状的子树高度为4。

进一步地，可以将具有相同形状编码的树节点合并，生成索引形状图中的同一形状节点，形状节点的编号与形状编码相同，例如：结合图4和图5可知，图4中索引二叉树的最左侧的第三级树节点和最右侧的第三级树节点均具有形状编码为2的子树形状，因此可以将最左侧的第三级树节点和最右侧的第三级树节点合并为索引形状图中的同一形状节点，该形状节点的编号也为2。进一步地，可以将索引二叉树中的最后一级树节点合并为索引形状图中的同一形状节点，该形状节点的编号与树节点的形状编码相同，例如可以将图4索引二叉树中的全部第四级树节点合并为索引形状图中的同一形状节点，由图5可知树节点的形状编码为1，因此该形状节点的编号也为1。

图6示出了根据本申请实施例的生成索引形状图的示意图。

如图6所示，二值化向量中包括相同向量，例如r1′′和r6′′、r2′′和r7′′、r4′和r8′′，可以将相同二值化向量作为一个索引向量，得到索引向量v1′′′至索引向量v5′′′。针对索引向量v1′′′至索引向量v5′′′构建索引二叉树，并根据图5所示的索引二叉树中的不同子树形状与其对应的形状编码，将索引二叉树中的具有相同形状编码的树节点合并，生成索引形状图。

由图6可以看出，索引二叉树共包含11个树节点，对索引二叉树进行节点压缩后得到的索引形状图中的形状节点数量为6个（如图6中形状编码为6、4、5、3、2、1的形状节点），也即将节点数量压缩到了索引二叉树中树节点数量的一半左右。可见，通过根据子树形状对索引二叉树进行节点压缩得到索引形状图，可以使得生成的索引形状图仅占据较小的存储空间。

此外，索引二叉树的高度越高，越接近满二叉树，将索引二叉树压缩为索引形状图的压缩率越高，其中，满二叉树可以包括二叉树中每一级的节点数都达到最大值的二叉树。对于基于n个维度为D的索引向量构建的满二叉树，满二叉树的高度为D+1，节点总数为2^D+1-1，将索引二叉树压缩为索引形状图时，仅需遍历满二叉树的2^D+1-1个节点即可。因此，将索引二叉树压缩为索引形状图的时间复杂度为O(2^D+1-1)，表示在将索引二叉树压缩为索引形状图时仅需执行2^D+1-1次遍历节点的操作。因此，将索引二叉树压缩为索引形状图的时间复杂度仅与索引向量的维度数D有关，而与索引向量的个数n无关。

根据本申请的实施例，被压缩后与同一个索引向量相对应的多个源数据对应一个源数据集合；索引二叉树包括与K个索引向量对应的K个叶节点，查询方法还包括：将与K个索引向量相对应的K个源数据集合分别与K个叶节点相关联。

具体地，由于索引向量有可能是对多个源数据进行压缩得到的，因此索引向量可能对应多个源数据，可以将一个索引向量所对应的多个源数据作为一个源数据集合。例如：某个索引向量是对源数据v1和源数据v2进行压缩得到的，因此与该索引向量对应的源数据集合中包括源数据v1和源数据v2。

具体地，叶节点可以包括索引二叉树中最末级的树节点。

图7示出了根据本申请实施例的叶节点与源数据集合的关联关系的示意图。如图7中的索引二叉树共包括5个叶节点。

由于索引二叉树被划分为N级的多个树节点和树节点之间的关联边，且关联边可以表征索引向量中的某一维度的第一数值，因此根据通过关联边依次连接的多个树节点之间的多个关联边，可以得到索引向量中的多个维度的第一数值。

例如对于图7中的索引二叉树，索引二叉树中包括多个关联边，其中第一级树节点与左边的第二级树节点之间的关联边表征索引向量中的第一维数值为0、左边的第二级树节点与最左边的第三级树节点之间的关联边表征索引向量中的第二维数值为0、最左边的第三级树节点与最左边的第四级树节点之间的关联边表征索引向量中的第三维数值为0，从而可以表征索引向量（0,0,0）。由图7可知，每个叶节点可以对应一个索引向量，例如最左侧的叶节点对应索引向量（0,0,0）。

进一步地，由于一个索引向量可以对应一个源数据集合，且一个叶节点可以对应一个索引向量，因此，可以将叶节点与源数据集合相关联。例如图7所示，最左侧的叶节点与索引向量（0,0,0）对应，而索引向量（0,0,0）对应于源数据集合1，因此可以将最左侧的叶节点与源数据集合1相关联。

具体地，通过将与K个索引向量相对应的K个源数据集合分别与K个叶节点相关联，可较快定位到相关的源数据，从而可以提高查询效率。

根据本申请的实施例，索引形状图中，与目标索引向量相对应的目标路径中的目标形状节点携带有偏移信息，偏移信息用于表征：在索引二叉树中，与目标索引向量对应的目标叶节点在水平方向上相对于首个叶节点的位置偏移；从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据包括：在沿目标路径逐节点查询目标索引向量的过程中，获取目标形状节点携带的偏移信息；基于偏移信息从K个叶节点中确定目标叶节点；将与目标叶节点关联的目标源数据集合中的数据确定为多个初选源数据。

具体地，将索引二叉树压缩为索引形状图虽然可以减少节点数量，节省存储空间，但是索引形状图也会丢失一部分索引二叉树中的信息。例如最后一级叶节点的位置信息会丢失（索引二叉树中最后一级叶节点在索引形状图中仅对应一个形状节点）。可通过添加偏移信息来实现这部分丢失信息的还原，进而定位到与查询路径相对应的源数据。

图8示出了根据本申请实施例的生成携带偏移信息的索引形状图的示意图。

如图8所示，索引二叉树可以表征出叶节点与源数据集合之间的关联关系，例如最左侧的叶节点与源数据集合1关联。但是由于将索引二叉树中的全部叶节点合并为了同一形状节点，也即形状编码为1的形状节点，所有的查询路径均经过该形状编码为1的形状节点，因此，仅根据索引形状图无法确定目标索引向量或者其查询路径具体是关联哪个源数据集合。因此，可以对索引形状图中的多个形状节点添加偏移信息，通过偏移信息表征在与索引形状图对应的索引二叉树中，与索引向量对应的叶节点在水平方向上相对于首个叶节点的位置偏移，其中，每个形状节点的偏移信息可以表现为该形状节点所对应的索引二叉树的左子树包含的叶节点数量。

偏移信息例如图8索引形状图的形状节点中括号中的内容所示。如图8所示，形状编码为6的形状节点所携带的偏移信息可以表示为（3），对应地，在索引二叉树中，与形状编码为6的形状节点对应的树节点的左子树的最后一级叶节点数量为3；再例如，形状编码为4的形状节点所携带的偏移信息可以表示为（2），对应地，在索引二叉树中，与形状编码为4的形状节点对应的树节点的左子树的最后一级叶节点数量为2。

根据本申请的实施例，可在沿目标路径逐节点查询目标索引向量的过程中，获取目标形状节点携带的偏移信息；并基于偏移信息从K个叶节点中确定目标叶节点，进而定位到与目标叶节点关联的源数据集。

进一步地，从索引形状图中查询得到与简化向量匹配的目标索引向量，可以是查询得到与简化向量完全匹配的目标索引向量；也可以是查询得到与简化向量部分匹配的目标索引向量。

基于此，从K个叶节点中确定目标叶节点的情形也包括两种情形。

第一种情形：在查询到与简化向量完全匹配的目标索引向量的情况下，目标索引向量仅包括一个，与目标索引向量对应的目标路径也仅包括一条，可以基于该条路径中目标形状节点携带的偏移信息，从K个叶节点中确定一个目标叶节点。

具体可以是将目标路径中数值为第一值（例如为“1”）的多条边的各自对应的上级形状节点携带的偏移信息求和，得到总偏移量。该总偏移量表征在对应的索引二叉树中，与该索引向量对应的叶节点在水平方向上相对于首个叶节点的位置偏移，因此，可以根据该总偏移量从K个叶节点中确定目标叶节点，即由第一个叶节点开始向右偏移对应总偏移量的位置，定位到目标叶节点。

例如：简化向量为（0,1,1）。对于如图8所示的索引形状图，可以从根节点，也即形状编码为6的形状节点开始依次遍历查询，首先确定形状编码为6与形状编码为4的形状节点之间的有向边所表征的第一维数值为0，与简化向量的第一维数值0匹配，进一步可以确定形状编码为4与形状编码为3的形状节点之间的有向边所表征的第二维数值为1，与简化向量的第二维数值1匹配，然后可以确定形状编码为3与形状编码为1的形状节点之间的有向边所表征的第三维数值为1，与简化向量的第三维数值1匹配，由此可以得到与简化向量（0,1,1）匹配的目标索引向量（0,1,1），目标路径包括形状编码分别为6、4、3、1的目标形状节点。

将目标路径中数值为1的多条边的多个上级形状节点对应的多个偏移信息求和，如图8中：形状编码为4的形状节点的偏移信息为2、形状编码为3的形状节点的偏移信息为0，计算偏移信息分别为4和3的形状节点的偏移信息的加和，得到总偏移信息为2。

如图8所示，在目标索引向量为（0,1,1）、总偏移信息为2的情况下，首个叶节点为索引二叉树中最左侧的叶节点，也即与源数据集合1关联的叶节点。由于总偏移信息为2，因此可以确定相对于首个叶节点的位置偏移为2的叶节点，也即从左向右数第三个位置的叶节点，得到目标叶节点，具体地目标叶节点为与源数据集合3关联的叶节点。可以将目标叶节点所关联的源数据集合作为目标源数据集合，目标源数据集合中包括至少一个初始源数据。

第二种情形：在查询到与简化向量部分匹配的目标索引向量的情况下，目标索引向量包括多个，与目标索引向量对应的目标路径也包括多条，可以基于这多条路径各自的目标形状节点携带的偏移信息，从K个叶节点中确定多个目标叶节点。

具体可以是将每条目标路径中数值为第一值（例如为“1”）的多条边的各自对应的上级形状节点携带的偏移信息求和，得到与多条目标路径一一对应的多个总偏移量。根据这几个总偏移量一一对应地确定多个目标叶节点，这多个目标叶节点都属于检索的范围。

例如，简化向量为（1,1,1），则从图8中查询，可以查到与该向量部分匹配的两个目标索引向量：（1,0,0）和（1,0,1），则计算得到这两个目标索引向量所在2条目标路径对应的两组总偏移量，分别为3、4，则按照偏移位置为3、4，从索引二叉树的多个叶节点中确定2个目标叶节点，分别为从第一个叶节点开始向右偏移3个位置和偏移4个位置的节点。

这种情形下，从K个叶节点中确定多个目标叶节点的方法还可以是：在查询到与简化向量部分匹配的目标索引向量的情况下，即未能匹配最后一级叶节点，在中间路径上转向了一个空节点，假设到最长匹配节点时（即下一步会转向空节点的形状节点），计算的对应索引二叉树中叶节点的偏移位置为i，最长匹配节点对应的叶节点总数为r，则从第i到第i+（r-1）的叶节点都在匹配范围内。

根据本申请的实施例，在查询不到与简化向量完全匹配的目标索引向量的情况下，通过返回多个目标叶节点对应的数据集，实现了最大程度的匹配查询。

根据本申请的实施例，通过预先确定源数据集合与索引二叉树中叶节点的关联关系、并在索引形状图的形状节点中添加偏移信息，通过偏移信息表征与形状节点所对应的索引二叉树节点在索引二叉树中的位置信息，可以将叶节点与源数据集合的关联关系表征在索引形状图中，从而避免了将索引二叉树压缩为索引形状图所带来的信息丢失问题。

并且，通过在形状节点中添加索引二叉树节点的位置偏移信息，以及预先构建源数据与索引二叉树叶节点的关联关系，作为得到多个初选源数据的关联信息，由此可以在查询数据的过程中同步获取多个初选源数据的关联信息，可较快定位到相关的源数据，无需后续再进行数据匹配的操作，从而提高了查询效率。

根据本申请的实施例，查询方法还包括：在对索引二叉树进行节点压缩得到索引形状图后，删除索引二叉树。

具体地，由于索引二叉树所占据的存储空间较大，如果将索引二叉树和索引形状图均进行存储，会占用较大存储空间。而索引形状图已经可以表征索引二叉树所要表征的信息，例如索引形状图中的偏移信息已经可以表征叶节点与源数据集合的关联关系，在沿目标路径逐节点查询目标索引向量的过程中，即可获取目标形状节点携带的偏移信息，从而确定叶节点与源数据集合的关联关系，因此基于索引形状图即可确定与查询数据对应的初选源数据。在此情况下，可以将索引二叉树删除，仅存储索引形状图，从而释放存储空间。

根据本申请的实施例，查询方法还包括：将被压缩后与同一个索引向量相对应的多个源数据记录在一个数据列表中，并存储K个索引向量与K个数据列表之间的映射关系；从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据包括：基于映射关系，从K个数据列表中确定对应于目标索引向量的目标数据列表。

例如：针对一个索引向量，可以从S个源数据中确定与该索引向量对应的多个源数据，并将这多个源数据存储至一个数据列表中，由此，可以得到与K个索引向量各自对应的K个数据列表。

具体地，为了便于将索引向量与其对应的数据列表关联起来，可以确定并存储K个索引向量与K个数据列表之间的映射关系。具体地，可以分别为K个索引向量设置向量标识，并分别为K个数据列表设置列表标识。可以通过向量标识和列表标识之间的映射关系表征索引向量与数据列表之间的映射关系。例如：向量标识v1′′′与列表标识T1之间存在映射关系，表明向量标识为v1′′′的索引向量对应于列表标识为T1的数据列表。

进一步地，基于映射关系，从K个数据列表中确定对应于目标索引向量的目标数据列表可以包括：确定目标索引向量的目标向量标识；确定与目标向量标识存在映射关系的目标列表标识；确定与目标列表标识对应的数据列表，得到目标数据列表。

通过将被压缩后与同一个索引向量相对应的多个源数据记录在一个数据列表中，并存储K个索引向量与K个数据列表之间的映射关系，再基于映射关系从K个数据列表中确定对应于目标索引向量的目标数据列表，可以简单、准确地确定对应于目标索引向量的初选源数据，降低了查询复杂度。

本申请还提供了一种处理器，包括：片上计算组件，用于执行查询方法；片上存储单元，用于存储索引形状图。

具体地，处理器例如包括现场可编程门阵列（Field-Programmable Gate Array，缩写为FPGA），也可以包括图形处理单元（Graphics Processing Unit，缩写为GPU）等。

具体地，可以通过一个处理器执行查询方法并存储索引形状图，从而完成查询任务。具体地，一方面，通过将索引数据存储在片上存储中，可以在查询数据时直接从片上存储单元读取索引形状图，与在查询时从外部存储获取索引形状图相比，可以减少查询时从外部存储获取索引数据的延迟，从而提高查询效率。

另一方面，片上存储单元的存储空间有限，而索引形状图所占据的存储空间较小，因此其可以存储在片上存储单元中，由此可以减少内存开销。

根据本申请的实施例，片上计算组件包括M组流水处理单元；片上存储单元包括与M组流水处理单元通信连接的M个子存储区，其中，与索引形状图对应的K个索引向量各自包括的N维第一数值存储在M个子存储区中的N个目标子存储区中，M、N为正整数，M大于等于N；M组流水处理单元中的N组目标流水处理单元用于执行以下操作：并行地从N个目标子存储区中读取N维第一数值；并行地将简化向量包括的N维第二数值与N维第一数值进行匹配，得到与简化向量匹配的目标索引向量。

图9示出了根据本申请实施例的片上计算组件和片上存储单元的结构示意图。

如图9所示，片上计算组件例如包括流水处理单元1、流水处理单元2…流水处理单元N、流水处理单元M，片上存储单元例如包括子存储区1、子存储区2…子存储区N、子存储区M。

如图9所示，片上存储单元中的每个子存储区可以存储索引向量中一个维度的第一数值，例如，子存储区1可以存储K个索引向量中的第一维第一数值、子存储区2可以存储K个索引向量中的第二维第一数值、子存储区N中存储有第N维第一数值。可以将存储有第一数值的子存储区作为目标子存储区，例如在索引向量包括N维第一数值的情况下，M个子存储区中包括N个目标子存储区。片上计算组件包括M组流水处理单元，每组流水处理单元可以与子存储区进行通信连接，从而可以读取子存储区中存储的第一数值，以执行查询方法，例如可以通过N组目标流水处理单元从N个目标子存储区中读取N维第一数值。

具体地，N组目标流水处理单元可以并行地从N个目标子存储区中读取N维第一数值，例如：N组目标流水处理单元同时从N个目标子存储区中读取N维第一数值。与依次从N个目标子存储区中读取N维第一数值相比，并行读取的方式可以提高读取速度。

进一步地，在读取到N维第一数值后，N组目标流水处理单元可以并行地将简化向量包括的N维第二数值与N维第一数值进行匹配，从而得到与简化向量匹配的目标索引向量，例如：N组目标流水处理单元同时将简化向量包括的N维第二数值与N维第一数值进行匹配。通过N组目标流水处理单元并行进行匹配的方式，可以提高匹配速度。

本申请还提供了一种处理系统，包括第一处理器和第二处理器。也可以通过第一处理器和第二处理器共同完成查询任务。

其中，第一处理器用于从索引形状图中查询得到与简化向量匹配的目标索引向量；其中，索引形状图表示K个索引向量，K个索引向量是对索引库中的S个源数据进行压缩得到的，S、K为正整数，且S≥K。第二处理器用于对查询指令对应的查询数据进行压缩得到简化向量、从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据，以及根据查询数据与至少一个初选源数据的相似度，得到与查询数据匹配的目标源数据。

具体地，第一处理器例如包括FPGA或GPU。其中，索引形状图可以存储在第一处理器中，例如可以存储在FPGA的片上存储空间中，FPGA的片上存储空间例如包括FPGA的静态随机存取存储器（Static Random Access Memory，缩写为SRAM）。此外，K个索引向量与K个数据列表之间的映射关系可以存储在FPGA的片外存储空间，FPGA的片外存储空间例如包括动态随机存取存储器（Dynamic Random Access Memory，缩写为DRAM）。第二处理器例如包括中央处理器（Central Processing Unit，缩写为CPU）、也可以包括GPU。

图10示出了根据本申请实施例的第一处理器和第二处理器的系统交互图。

如图10所示，可以将查询数据输入第二处理器，由第二处理器对查询数据进行压缩得到简化向量，对查询数据进行压缩例如包括对查询数据进行降维处理得到降维数据，再对降维数据进行二值化编码处理。

简化向量被输入第一处理器，第一处理器中的片上存储空间中存储有索引形状图，此外，片外存储空间中存储有索引向量与数据列表之间的映射关系。第一处理器还包括多组流水处理单元，多组流水处理单元可以执行并行处理，并行处理包括并行地从片上存储空间中读取N维第一数值，以及并行地将简化向量包括的N维第二数值与N维第一数值进行匹配得到与简化向量匹配的目标索引向量。

可以将目标索引向量返回第二处理器，以使得第二处理器可以根据目标索引向量，从S个源数据中确定被压缩后与目标索引向量相对应的至少一个初选源数据，以及根据查询数据与多个至少一个初选源数据的相似度，得到与查询数据匹配的目标源数据。

进一步地，第二处理器还可以基于K个索引向量构建索引二叉树，对索引二叉树进行节点压缩得到索引形状图，以及确定K个索引向量与K个数据列表之间的映射关系。可以将第二处理器生成的索引形状图和映射关系写入第一处理器。

图11示出了根据本申请另一实施例的查询方法的流程图。

如图11所示，该实施例的查询方法包括操作S1110~操作S1160。

在操作S1110，获取S个源数据。

在操作S1120，对源数据进行降维处理，得到降维处理后的向量数据。

在操作S1130，对降维处理后的向量数据进行二值化处理，得到索引向量。

在操作S1140，基于索引向量构建索引二叉树，以及确定映射关系。

在操作S1150，对索引二叉树进行节点压缩得到索引形状图。

在操作S1160，将索引形状图和映射关系写入第一处理器。

图12示出了根据本申请另一实施例的第一处理器和第二处理器的系统交互图。

根据图11和图12可知，可以由第二处理器将索引库中的S个源数据压缩为K个索引向量，其中压缩过程可以包括先对源数据进行降维处理，得到降维处理后的向量数据，再对降维处理后的向量数据进行二值化处理，得到索引向量。第二处理器还可以基于索引向量构建索引二叉树，并将索引二叉树进行节点压缩得到索引形状图，还可以生成索引向量与数据列表之间的映射关系。可以将索引形状图写入第一处理器，例如可以由片上存储空间存储索引形状图。

此外，可以将映射关系写入第一处理器，例如可以由第一处理器的片外存储空间存储映射关系。

具体地，由于第一处理器包括多组流水处理单元，其并行处理能力较好，且存储资源较小，因此可以将第一处理器用于存储索引形状图和映射关系，由第一处理器中的多组流水处理单元并行处理得到目标索引向量，从而发挥第一处理器在处理大规模数据的并行查询任务上的优势。由于第二处理器能够高效地处理各种类型的、需要复杂逻辑控制的任务，因此可以由第二处理器负责执行将查询数据压缩为简化向量，以及负责构建索引图和确定映射关系等需要复杂逻辑控制的任务，从而充分发挥第二处理器在处理各种类型的计算任务上的优势。因此，通过由第一处理器和第二处理器组合完成查询任务，可以充分发挥第一处理器和第二处理器各自的优势，提高了查询效率。

图13示出了根据本申请实施例的适于实现查询方法的电子设备的方框图。

如图13所示，根据本申请实施例的电子设备1300包括处理器1301，其可以根据存储在只读存储器（ROM）1302中的程序或者从存储部分1308加载到随机访问存储器（RAM）1303中的程序而执行各种适当的动作和处理。处理器1301例如可以包括通用微处理器（例如CPU）、指令集处理器和/或相关芯片组和/或专用微处理器（例如，专用集成电路（ASIC））等等。处理器1301还可以包括用于缓存用途的板载存储器。处理器1301可以包括用于执行根据本申请实施例的方法流程的不同动作的单一处理单元或者是多个处理单元。

在RAM 1303中，存储有电子设备1300操作所需的各种程序和数据。处理器 1301、ROM 1302以及RAM 1303通过总线1304彼此相连。处理器1301通过执行ROM 1302和/或RAM1303中的程序来执行根据本申请实施例的方法流程的各种操作。需要注意，程序也可以存储在除ROM 1302和RAM 1303以外的一个或多个存储器中。处理器1301也可以通过执行存储在一个或多个存储器中的程序来执行根据本申请实施例的方法流程的各种操作。

根据本申请的实施例，电子设备1300还可以包括输入/输出（I/O）接口1305，输入/输出（I/O）接口1305也连接至总线1304。电子设备1300还可以包括连接至输入/输出（I/O）接口1305的以下部件中的一项或多项：包括键盘、鼠标等的输入部分1306；包括诸如阴极射线管（CRT）、液晶显示器（KCD）等以及扬声器等的输出部分1307；包括硬盘等的存储部分1308；以及包括诸如KAN卡、调制解调器等的网络接口卡的通信部分1309。通信部分1309经由诸如因特网的网络执行通信处理。驱动器1310也根据需要连接至输入/输出（I/O）接口1305。可拆卸介质1311，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器1310上，以便于从其上读出的计算机程序根据需要被安装入存储部分1308。

本申请还提供了一种计算机可读存储介质，该计算机可读存储介质可以是上述实施例中描述的设备/装置/系统中所包含的；也可以是单独存在，而未装配入该设备/装置/系统中。上述计算机可读存储介质承载有一个或者多个程序，当上述一个或者多个程序被执行时，实现根据本申请实施例的方法。

根据本申请的实施例，计算机可读存储介质可以是非易失性的计算机可读存储介质，例如可以包括但不限于：便携式计算机磁盘、硬盘、随机访问存储器（RAM）、只读存储器（ROM）、可擦式可编程只读存储器（EPROM或闪存）、便携式紧凑磁盘只读存储器（CD-ROM）、光存储器件、磁存储器件、或者上述的任意合适的组合。在本申请中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。例如，根据本申请的实施例，计算机可读存储介质可以包括上文描述的ROM 1302和/或RAM 1303和/或ROM 1302和RAM 1303以外的一个或多个存储器。

本申请的实施例还包括一种计算机程序产品，其包括计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。当计算机程序产品在计算机系统中运行时，该程序代码用于使计算机系统实现本申请实施例所提供的方法。

在该计算机程序被处理器1301执行时执行本申请实施例的系统/装置中限定的上述功能。根据本申请的实施例，上文描述的系统、装置、模块、单元等可以通过计算机程序模块来实现。

在一种实施例中，该计算机程序可以依托于光存储器件、磁存储器件等有形存储介质。在另一种实施例中，该计算机程序也可以在网络介质上以信号的形式进行传输、分发，并通过通信部分1309被下载和安装，和/或从可拆卸介质1311被安装。该计算机程序包含的程序代码可以用任何适当的网络介质传输，包括但不限于：无线、有线等等，或者上述的任意合适的组合。

在这样的实施例中，该计算机程序可以通过通信部分1309从网络上被下载和安装，和/或从可拆卸介质1311被安装。在该计算机程序被处理器1301执行时，执行本申请实施例的系统中限定的上述功能。根据本申请的实施例，上文描述的系统、设备、装置、模块、单元等可以通过计算机程序模块来实现。

根据本申请的实施例，可以以一种或多种程序设计语言的任意组合来编写用于执行本申请实施例提供的计算机程序的程序代码，具体地，可以利用高级过程和/或面向对象的编程语言、和/或汇编/机器语言来实施这些计算程序。程序设计语言包括但不限于诸如Java，C++，python，“C”语言或类似的程序设计语言。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。在涉及远程计算设备的情形中，远程计算设备可以通过任意种类的网络，包括局域网（KAN）或广域网（WAN），连接到用户计算设备，或者，可以连接到外部计算设备（例如利用因特网服务提供商来通过因特网连接）。

附图中的流程图和框图，图示了按照本申请各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，上述模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图或流程图中的每个方框、以及框图或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

本领域技术人员可以理解，本申请的各个实施例中记载的特征可以进行多种组合和/或结合，即使这样的组合或结合没有明确记载于本申请中。特别地，在不脱离本申请精神和教导的情况下，本申请的各个实施例中记载的特征可以进行多种组合和/或结合。所有这些组合和/或结合均落入本申请的范围。

以上对本申请的实施例进行了描述。但是，这些实施例仅仅是为了说明的目的，而并非为了限制本申请的范围。尽管在以上分别描述了各实施例，但是这并不意味着各个实施例中的措施不能有利地结合使用。不脱离本申请的范围，本领域技术人员可以做出多种替代和修改，这些替代和修改都应落在本申请的范围之内。

Claims (15)

1.一种查询方法，其特征在于，所述方法包括：

接收查询指令；

对所述查询指令对应的查询数据进行压缩得到简化向量；

从索引形状图中查询得到与所述简化向量匹配的目标索引向量；其中，所述索引形状图表示K个索引向量，所述K个索引向量是对索引库中的S个源数据进行压缩得到的，S、K为正整数，且S≥K；

从所述S个源数据中确定被压缩后与所述目标索引向量相对应的至少一个初选源数据；

根据所述查询数据与所述至少一个初选源数据的相似度，得到与所述查询数据匹配的目标源数据。

2.根据权利要求1所述的方法，其特征在于，对所述查询指令对应的查询数据进行压缩得到简化向量包括：

对所述查询数据进行降维处理，得到降维数据；

对所述降维数据进行二值化编码处理，得到所述简化向量。

3.根据权利要求2所述的方法，其特征在于，所述简化向量包括第一值和第二值；

对所述降维数据进行二值化编码处理包括：

对所述降维数据包括的多维子数据进行数值计算，得到参考数值；

基于所述多维子数据各自与所述参考数值之间的数值偏差，生成所述多维子数据各自对应的所述第一值或所述第二值。

4.根据权利要求1-3任一项所述的方法，其特征在于，所述方法还包括：

基于所述K个索引向量构建索引二叉树；

对所述索引二叉树进行节点压缩得到所述索引形状图。

5.根据权利要求4所述的方法，其特征在于：

所述K个索引向量各自包括N维第一数值，N为正整数；

所述索引二叉树被划分为N级的多个树节点和树节点之间的关联边，所述关联边表征所述N维第一数值；

所述索引形状图被划分为N级的多个形状节点和形状节点之间的有向边，所述有向边表征所述N维第一数值；

所述索引形状图中一个形状节点表示所述索引二叉树中具有相同子树形状的多个树节点。

6.根据权利要求5所述的方法，其特征在于，对所述索引二叉树进行节点压缩得到所述索引形状图包括：

确定所述树节点的形状编码，所述形状编码用于表征所述树节点的子树形状类别；

将具有相同所述形状编码的树节点合并，生成所述索引形状图。

7.根据权利要求5所述的方法，其特征在于，被压缩后与同一个所述索引向量相对应的多个所述源数据对应一个源数据集合；所述索引二叉树包括与所述K个索引向量对应的K个叶节点；

所述方法还包括：

将与所述K个索引向量相对应的K个所述源数据集合分别与所述K个叶节点相关联。

8.根据权利要求7所述的方法，其特征在于，所述索引形状图中，与所述目标索引向量相对应的目标路径中的目标形状节点携带有偏移信息，所述偏移信息用于表征：在所述索引二叉树中，与所述目标索引向量对应的目标叶节点在水平方向上相对于首个叶节点的位置偏移；

从所述S个源数据中确定被压缩后与所述目标索引向量相对应的至少一个初选源数据包括：

在沿所述目标路径逐节点查询所述目标索引向量的过程中，获取所述目标形状节点携带的所述偏移信息；

基于所述偏移信息从所述K个叶节点中确定目标叶节点；

将与所述目标叶节点关联的目标源数据集合中的数据确定为所述至少一个初选源数据。

9.根据权利要求4所述的方法，其特征在于，所述方法还包括：

在对所述索引二叉树进行节点压缩得到所述索引形状图后，删除所述索引二叉树。

10.根据权利要求1所述的方法，其特征在于：

所述方法还包括：将被压缩后与同一个所述索引向量相对应的多个所述源数据记录在一个数据列表中，并存储K个所述索引向量与K个所述数据列表之间的映射关系；

从所述S个源数据中确定被压缩后与所述目标索引向量相对应的至少一个初选源数据包括：基于所述映射关系，从K个所述数据列表中确定对应于所述目标索引向量的目标数据列表。

11.一种处理器，其特征在于，包括：

片上计算组件，用于执行权利要求1~10中任一项所述的查询方法；

片上存储单元，用于存储所述索引形状图。

12.根据权利要求11所述的处理器，其特征在于：

所述片上计算组件包括M组流水处理单元；所述片上存储单元包括与所述M组流水处理单元通信连接的M个子存储区，其中，与所述索引形状图对应的K个索引向量各自包括的N维第一数值存储在所述M个子存储区中的N个目标子存储区中，M、N为正整数，M大于等于N；

所述M组流水处理单元中的N组目标流水处理单元用于执行以下操作：

并行地从所述N个目标子存储区中读取所述N维第一数值；

并行地将简化向量包括的N维第二数值与所述N维第一数值进行匹配，得到与所述简化向量匹配的目标索引向量。

13.一种处理系统，其特征在于，包括：

第一处理器，用于从索引形状图中查询得到与简化向量匹配的目标索引向量；其中，所述索引形状图表示K个索引向量，所述K个索引向量是对索引库中的S个源数据进行压缩得到的，S、K为正整数，且S≥K；

第二处理器，用于对查询指令对应的查询数据进行压缩得到所述简化向量、从所述S个源数据中确定被压缩后与所述目标索引向量相对应的至少一个初选源数据，以及根据所述查询数据与所述至少一个初选源数据的相似度，得到与所述查询数据匹配的目标源数据。

14.一种计算机可读存储介质，其上存储有计算机程序或指令，其特征在于，所述计算机程序或指令被处理器执行时实现根据权利要求1~10中任一项所述方法的步骤。

15.一种计算机程序产品，包括计算机程序或指令，其特征在于，所述计算机程序或指令被处理器执行时实现根据权利要求1~10中任一项所述方法的步骤。