CN111801665B - 用于大数据应用的分层局部敏感哈希(lsh)分区索引 - Google Patents

Abstract

本发明描述了用于对多个数据对象进行分区的系统和方法，其中，每个数据对象由各自的高维特征向量表示。该方法包括：对每个高维特征向量执行哈希函数，以为由所述高维特征向量表示的数据对象生成各自的低维二进制紧凑特征向量；对每个紧凑特征向量执行另一个哈希函数，以将子索引ID分配给所述紧凑特征向量；将紧凑特征向量分区到各自的分区组中，其中，所述各自的分区组对应于分配给所述紧凑特征向量的子索引ID。

Description

用于大数据应用的分层局部敏感哈希(LSH)分区索引

相关申请

本申请要求于2018年3月1日递交的第62/637,278号美国临时专利申请和于2018年7月24日递交的第16/044,362号美国实用型专利申请的益处和在先申请优先权，该内容皆以引入的方式并入本文中。

技术领域

本发明通常涉及数据库的索引和搜索，特别涉及非结构化数据的分区索引。

背景技术

存储在数字信息存储库(例如在线互联网和基于云的数据库)中的非结构化多媒体数据对象(例如包括图像数据、视频数据、音频数据，文本数据和其他复杂的数字对象)的数量正在急剧增长。以准确且资源有效的方式处理非结构化数据的搜索查询是一项技术挑战。

相似度搜索是一种基于查询对象和搜索数据库中的数据对象的相似度之间的比较来搜索非结构化数据对象的数据搜索方法。相似度搜索通常涉及为数据库中存储的每个数据对象创建元数据，为查询对象创建元数据，然后比较所述查询对象的元数据与所述数据对象的元数据。每个对象的元数据可以采用特征向量的形式，该特征向量是表示所述对象的多维数值特征向量。在这方面，相似度搜索可以被定义为从数据库中存储的多个特征向量中找到与给定特征向量(例如，查询向量)最相似的特征向量。相似度搜索算法可用于模式识别与分类、推荐系统、统计机器学习以及诸多其它领域。

因此，相似度搜索通常涉及使用特征提取算法将查询对象(例如，图像、视频样本、音频样本或文本)翻译为(转换为)表示所述查询对象的查询特征向量。然后，所述查询特征向量用于搜索特征向量的数据库，以定位与所述查询特征向量最相似的一个或多个数据对象特征向量(例如，存储在所述数据库中的数据对象的特征向量)。

在非结构化数据对象的情况下，所述特征向量通常是高维向量。在高维特征空间中，给定数据集的数据变得稀疏，因此距离和相似度失去了统计意义，造成查询性能会随着维度数量的增加呈指数下降。这称为“维数灾难”问题。

解决“维数灾难”问题的一种方法包括：对存储在数据库中的每个特征向量应用降维算法，以生成每个特征向量的较短版本(例如，紧凑特征向量)。在为所述数据库中存储的每个对象的每个特征向量生成紧凑特征向量后，使用索引生成算法从所述紧凑特征向量中生成搜索索引。所述降维算法也可应用于所述查询特征向量，以生成所述查询特征向量的较短版本(例如，紧凑查询特征向量)。然后，可以通过向搜索算法提供所述紧凑查询向量和所述搜索索引以查找与所述查询特征向量最相似的候选数据对象特征向量来执行相似度搜索。

将向量维数较大的特征向量转换为向量维数减少的紧凑特征向量并生成相应的搜索索引的一种方法是应用基于哈希的近似最近邻(approximate nearest neighbor，简称ANN)算法。例如，局部敏感哈希(locality sensitive hashing，简称LSH)可以用于降低高维数据的维数。LSH对输入项进行哈希处理，使得相似项以高概率映射到相同的“桶”中(桶的数量要比可能的输入项的总和少得多)。特别地，可以使用LSH算法对特征向量进行哈希处理，以生成作为所述紧凑特征向量的LSH哈希值。

然而，现有的基于LSH-ANN的索引和搜索算法存在的一个问题是，这些算法可能导致搜索查询过度偏向于紧凑特征向量的最高有效位(most significant bit，简称MSB)之间的相似度。特别地，现有的索引生成方法可使用紧凑特征向量的前几位(或者其它连续位组，例如最后几位)来标识相似的特征向量。然而，这些位可能无法很好地指示相似度，从而导致搜索不准确以及计算资源的使用效率低下。

图1A说明了此类MSB问题的一个示例，其示出了基于LSH的索引与搜索方法100的一个示例。在图1A中的例子中，索引102指向不同的槽或桶104(1)，104(2)，其中，每个槽或桶都以紧凑特征向量K_i的形式包含各自的哈希值集。根据公共前缀最长长度(longestlength of common prefix，简称LLCP)或其它定义的距离测量法，所述紧凑特征向量K_i分组到各自的桶104(1)，104(2)中。如图1A所示，根据欧氏距离，与紧凑特征向量K₃相比，紧凑特征向量K₁与紧凑特征向量K₂更相似。然而，基于所述紧凑特征向量K₁的前两(2)个分量(例如，前两位)与紧凑特征向量K₂和K₃的前(2)两个分量(例如，前两位)之间的比较，图1中的索引生成方法将所述紧凑特征向量K₁和K₂分到不同的桶104(1)和104(2)中，并将所述紧凑特征向量K₁和K₃结合到同一个桶104(2)中。当紧凑查询特征向量q进入，基于前两个分量，所述紧凑查询特征向量q会更接近所述第一桶104(1)，因此紧凑特征向量K₁和K₃作为候选最近邻被返回。其中，理想情况下紧凑特征向量K₁和K₂应作为紧凑查询特征向量q的最近邻被返回。这个错误是因为尽管在选择哈希函数时没有优先选择左边的分量或位，但在分区时优先考虑了该分量或位而导致的。这影响了使用生成的搜索索引进行相似度搜索时的准确性。

在具有多个搜索查询以搜索存储在数字信息存储库中的大量的非结构化数据对象的环境下，可以使用并发搜索查询分区策略对数据索引进行分组。例如，为了方便搜索，可以将索引分区或划分为分区组(其可以包括槽或者桶)，并将据称相似的对象分配到相同的分区组中。与上述MSB问题类似，现有的分区方法使用紧凑特征向量中的固定数量的前导位将紧凑特征向量分区为分区组。在执行查询时，只对一个分区组进行搜索会产生很大错误。图1B示出了传统(不基于内容)的分区方法的一个示例。基于前导2位，将紧凑特征向量K₂和K₃放入分区组11，并将紧凑特征向量K₁和K₄放入分区组01。尽管哈希值K₁和K₂除它们的第一位外几乎相同，但所述传统分区方法把哈希值K₁和K₂放入不同的分区组中。并且，传统分区方法将极为不同的哈希值K₂和K₃放入相同的分区组中。因此，相似的紧凑特征向量很可能被放入不同的子索引(例如，分区组)中，这会影响相似度搜索的准确性和一致性。

因此，本文公开了解决上述分区问题以提高搜索存储在数字信息存储库中的大规模非结构化数据的准确性和效率的方法和系统，包括能够提高搜索时的计算效率和搜索精确度的系统和方法。

发明内容

示例性实施例通过示例在说明书和权利要求书中公开。根据一个示例方面，描述了一种用于生成索引结构以索引多个非结构化数据对象的系统和方法，包括：生成紧凑特征向量集，所述集合包括每个所述数据对象的紧凑特征向量，每个数据对象的紧凑特征向量包括表示所述数据对象的哈希值的序列；并基于所述紧凑特征向量的内容将所述紧凑特征向量索引到分区组中。

根据第一示例方面，描述了一种用于对多个数据对象进行分区的方法，其中，每个数据对象由各自的高维特征向量表示。该方法包括：对每个高维特征向量执行哈希函数，以为由所述高维特征向量表示的数据对象生成各自的低维二进制紧凑特征向量；对每个紧凑特征向量执行另一个哈希函数，以将子索引ID分配给所述紧凑特征向量；将紧凑特征向量分区到各自的分区组中，其中，所述各自的分区组对应于分配给所述紧凑特征向量的子索引ID。

在一些示例性实施例中，对每个高维特征向量执行的所述哈希函数为局部敏感哈希(locality sensitive hashing，简称LSH)函数，对每个紧凑特征向量执行的所述另一个哈希函数也是LSH函数。在一些示例中，所述哈希函数和所述另一个哈希函数为正交角哈希函数。在一些示例中，所述方法包括：为每个所述各自的分区组生成可搜索的子索引结构。

在一些示例中，每个紧凑特征向量仅分区到单个所述分区组。在一些示例中，所述子索引结构作为独立可搜索的结构进行存储，使得所述子索引结构彼此间可以并发搜索。

在一些示例性实施例中，为每个所述各自的分区组生成可搜索的子索引结构包括：对于每个分区组：为所述分区组中的紧凑特征向量生成多个扭曲紧凑特征向量集，其中，每个所述扭曲紧凑特征向量集是通过对所述分区组中的紧凑特征向量应用各自的随机置乱排列生成的；对于每个扭曲紧凑特征向量集，基于所述扭曲紧凑特征向量集中的哈希值的序列，为由所述分区组中的紧凑特征向量表示的数据对象生成索引表；包括为所述分区组的可搜索子索引结构中的每个所述扭曲紧凑特征向量集生成的索引表。

根据第二示例方面，描述了一种用于对数据对象进行分区的系统，其中，每个数据对象由各自的高维特征向量表示。所述系统包括一个或多个处理单元以及与所述处理器系统耦合的系统存储设备。所述系统存储设备存储可执行指令，当所述可，使得所述系统：对每个高维特征向量执行指令由所述一个或多个处理单元执行时执行哈希函数，以为由所述高维特征向量表示的数据对象生成各自的低维二进制紧凑特征向量；对每个紧凑特征向量执行另一个哈希函数，以将子索引ID分配给所述紧凑特征向量；将紧凑特征向量分区到各自的分区组中，其中，所述各自的分区组对应于分配给所述紧凑特征向量的子索引ID。

根据第三示例方面，描述了一种计算机程序产品，包括一种媒介，其上有形地存储可执行指令，当所述可执行指令由数字处理系统执行时，使得所述数字处理系统：对多个高维特征向量中的每个高维特征向量执行哈希函数，以生成各自的低维二进制紧凑特征向量，每个所述高维特征向量表示各自的数据对象；对每个紧凑特征向量执行另一个哈希函数，以将子索引ID分配给所述紧凑特征向量；将紧凑特征向量分区到各自的分区组中，其中，所述各自的分区组对应于分配给所述紧凑特征向量的子索引ID。

根据第四示例方面，描述了一种用于搜索与查询对象相似的数据对象的方法。该方法包括：将所述查询对象转换为d维特征向量；对所述d维特征向量执行哈希函数，以为所述查询对象生成m维二进制紧凑查询向量，其中m<d；对所述查询向量执行另一个哈希函数，以确定所述查询向量的子索引ID；在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，所述子索引结构包括紧凑特征向量的索引，其中，每个紧凑特征向量表示各自的数据对象。

在第四方面的示例性实施例中，对所述d维特征向量执行的所述哈希函数为局部敏感哈希(locality sensitive hashing，简称LSH)函数，对所述紧凑特征查询向量执行的所述另一个哈希函数也是LSH函数。在一些示例中，所述哈希函数和所述另一个哈希函数为正交角哈希函数。

在第四方面的示例性实施例中，所述方法包括：确定另外的子索引ID的集合，其中，所述另外的子索引ID属于所述查询向量的所述子索引ID的相似度阈值范围内；在与所述另外的子索引ID对应的另外的子索引结构中搜索与所述查询向量相似的紧凑特征向量。在一些示例中，所述相似度阈值是指相对于所述查询向量的所述子索引ID的所述另外的子索引ID中不同位值的阈值级别。

在第四方面的一些示例性实施例中，如果在所述另外的子索引ID对应的所有所述子索引结构被搜索之前达到了搜索结果的阈值数，则终止对另外的子索引结构的搜索。

在第四方面的一些示例性实施例中，所述方法包括：在与所述子索引ID对应的子索引结构中进行搜索的同时：在另一个子索引结构中搜索紧凑特征向量，其中，所述紧凑特征向量与确定了另一个子索引ID的另一个查询向量相似。

根据第五示例方面，描述了一种用于搜索与查询对象相似的数据对象的系统。所述系统包括一个或多个处理单元以及与所述一个或多个处理单元中的每个处理单元耦合的系统存储设备。所述系统存储设备有形地存储可执行指令，当所述可执行指令由所述一个或多个处理单元执行时，使得所述系统：将所述查询对象转换为d维特征向量；对所述d维特征向量执行哈希函数，以为所述查询对象生成m维二进制紧凑查询向量，其中m<d；对所述查询向量执行另一个哈希函数，以确定所述查询向量的子索引ID；在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，所述子索引结构包括紧凑特征向量的索引，其中，每个紧凑特征向量表示各自的数据对象。

根据第六示例性实施例，描述了一种计算机程序产品，包括一种媒介，其上有形地存储可执行指令，当所述可执行指令由数字处理系统执行时，使得所述数字处理系统通过以下操作搜索与查询对象相似的数据对象：将所述查询对象转换为d维特征向量；对所述d维特征向量执行哈希函数，以为所述查询对象生成m维二进制紧凑查询向量，其中m<d；对所述查询向量执行另一个哈希函数，以确定所述查询向量的子索引ID；在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，所述子索引结构包括紧凑特征向量的索引，其中，每个紧凑特征向量表示各自的数据对象。

附图说明

现将参考附图对本发明实施例的示例进行更详细地描述。

图1A是基于现有技术的局部敏感哈希(locality sensitive hashing，简称LSH)的索引和搜索方法的示例的示意图。

图1B是现有技术分区方法的示例的示意图。

图2是根据示例性实施例的索引生成和相似度搜索方法的流程示意图。

图3是根据示例性实施例的用于生成哈希值函数的方法的伪代码表达方式。

图4是用于基于由图3中的方法生成的函数生成紧凑特征向量的方法的伪代码表达方式。

图5示出了根据示例性实施例的第一层LSH哈希值表。

图6示出了根据示例性实施例的图2中的索引生成方法的索引结构生成过程。

图7示出了根据示例性实施例的随机哈希值置乱过程的示例。

图8示出了图6中的过程的LSH索引表生成任务的示例。

图9示出了LSH索引表中不同d节点的可变长度缩放。

图10是可用于实现此处所述的方法和系统的数字处理系统的示例。

图11A示出了根据示例性实施例的包括分区的索引生成方法的示例。

图11B示出了根据示例性实施例的包含在图11A中的索引生成方法中的分区方法的示例。

图12是图11A中的包括分区方法的索引生成方法的示意图。

图13是图11B中用于将子索引ID分配给紧凑特征向量的分区方法的伪代码表达方式。

图14是使用分区索引的步进式搜索的流程图。

图15示出了增量步长子索引计算。

具体实施方式

图2是根据示例性实施例的索引生成方法202和相似度搜索方法204的流程示意图。在示例性实施例中，通过在一个或多个数字处理系统上实现的软件执行索引生成方法202和相似度搜索方法204。在示例性实施例中，所述索引生成方法202和相似度搜索方法204会使它们的主机数字处理系统以更高效和精确的方式工作。例如，此处所述的方法和系统可能会在一些应用中使用更少的处理资源以提供比以前可用的相似度搜索方法类似或更准确的搜索结果。

如图2中所示，在示例性实施例中，所述索引生成方法202定期执行，以索引存储在对象数据库206中的非结构化数据对象。例如，当通过添加、修改或删除存储在所述对象数据库206中的对象208使得所述对象数据库206中发生阈值级别变化时，可以执行索引生成方法202。另外，或可替代地，可以根据预先定义的时间表，如每小时、每天或每周执行索引生成方法202。在示例性实施例中，当接收到查询对象时，执行相似度搜索方法204。在一些示例性实施例中，对象数据库206可以是分布式数据库，其包括跨多个数字存储库存储的复杂数据对象，这些数字存储库承载在位于一个或多个位置的不同的真实或虚拟机上。

现在将依据示例性实施例更详细地描述索引生成方法202，其为存储在对象数据库206中的n个对象208生成索引结构219。索引生成方法202开始于特征提取过程210，在此过程中，从对象数据库206中包含的非结构化数据对象中提取信息，以为所述n个对象208中的每个数据对象生成相应的原始特征向量V_i。对象数据库206中包括的非结构化数据对象例如可以是视频数据对象、音频数据对象、图像数据对象、文本数据对象和其它非结构化数据对象中之一。例如，每个图像对象可以由各自的原始特征向量V_i表示，其中，该原始特征向量V_i源自原始图像数据的彩色直方图，每个视频对象可以由各自的原始特征向量V_i表示，其中，该原始特征向量V_i源自原始视频数据的尺度不变特征变换(scale-invariantfeature transform，简称SIFT)或3D-SIFT，或源自区分视频描述符(discriminate videodescriptors，简称DVD)。已知有许多不同的特征向量格式用于表示不同类别的数据对象，这些格式中的任何一种格式都适用于特征提取过程210，以将对象208转换成各自的原始特征向量V₁到V_n。在图2中的示例中，(共n个数据对象)的原始特征向量V₁到V_n存储在主表250中。在主表250中，原始特征向量V₁到V_n中的每个原始特征向量都被存储为objectID和对应的d维特征列表，该d维特征列表中包括d个归一化特征值fv₁到fv_d(例如，V_j＝{fv₁，fv₂，…，fv_d})，其中，特征值fv₁到fv_d中的每个特征值在0到1之间归一化。objectID可以直接或间接地指向对象存储库中的存储位置，该对象存储库中存储着由所述原始特征向量V₁到V_n表示的非结构化数据对象。

然后，对原始特征向量V₁到V_n中的每个原始特征向量执行降维过程214，以将所述高维原始特征向量转换为各自的低维紧凑特征向量K₁到K_n。虽然可以采用不同的约简算法，但是在至少一个示例性实施例中，降维过程214采用了局部敏感哈希(localitysensitivity hashing，简称LSH)算法，该算法使用正交角哈希函数将d维原始特征向量V₁到V_n转换为各自的m维紧凑特征向量K₁到K_n。在这方面，图3示出了用于生成随后在降维过程214中应用以将原始特征向量转换为各自的紧凑特征向量的正交角哈希函数的算法的伪代码表达方式。图3中的算法可以作为配置步骤先于索引生成方法202执行，所得到的哈希函数会被储存为LSH函数表以供未来使用。

图3中的算法提供有预定义的输入，包括：所述哈希函数将应用的原始特征向量V_ji的维数(d)(数据点维数＝d)；每个正交角哈希函数链G_i中将包含的哈希函数的数量(m)；以及总哈希族大小F_s(例如，m个哈希函数选自的哈希函数的总数)。图3中的算法的输出是一组L个正交角哈希函数链G_i，其中，i等于1到L。每个正交角哈希函数链G_i包括m个哈希函数h_j(记作G_i＝(h₁，h₂，…，hm)，其中h₁，h₂，…，h_m是从F_s个哈希函数的族中随机挑选的哈希函数)。如图3所示，随机生成一个L*d的矩阵H，其中矩阵H的元素x独立于正态分布进行采样。然后执行矩阵H的QR分解(其中，H＝QR，且假设d≤F_s)，以确定正交矩阵Q。在QR分解之后，所得到的m*L矩阵Q中的每一列提供m个元素的正交向量(即正交角哈希函数链G_i)。因此，所述矩阵Q中的每一列提供各自的正交角哈希函数链G_i(也称为LSH表)，该正交角哈希函数链G_i包括m个哈希函数h_j，其中，1≤j≤m(G_i＝(h₁，h₂，…，hm))。图3提供了合适的哈希函数生成算法的一个示例，在其它示例性实施例中，不同的已知哈希生成算法可以代替图3中的算法用于生成合适的复合LSH函数链，以用于此处所述的索引生成和搜索过程中。

一旦生成正交角哈希函数链G_i，哈希函数可用于降维过程214，以将每个d维原始特征向量V_ji降为各自的m维紧凑特征向量K_j。在这方面，图4示出了用于生成紧凑特征向量K₁到K_n的哈希值矩阵E的算法的伪代码表达方式。

在示例性实施例中，针对原始特征向量V₁到V_n中的每个原始特征向量的存储在主表250中的特征向量值已经被归一化了。对于每个所述特征向量值，直接计算哈希函数和特征向量值的内积。结果为cos(哈希函数，特征向量值)，称为角距。为了确定特征向量值所在的超平面，对所述结果应用sign()操作，以为特征向量值为-1或1的每个哈希函数提供输出。为了简化数字存储，哈希值-1被视为0。图4中所示的算法是用于获得复合哈希值的一种合适的哈希算法的示例，并且在其它示例性实施例中，可以采用其它将d维向量降为m大小向量的正交哈希算法。

因此，降维过程216应用LSH将每个长度为d的原始特征向量降为如紧凑特征值K_j＝G_i(V_j)＝{h₁(V_j)，h₂(V_j)，…，h_m(V_j)}所表示的长度为m的二进制序列。所述紧凑特征值K_j的二进制序列中的每个二进制值是特征向量V_j的所有特征值fv₁到fv_d与哈希函数链G_i的m个哈希函数(h₁，h₂，…，h_m)中的相应的一个哈希函数的哈希函数结果。例如，紧凑特征向量K_j中的第一个二进制值是哈希函数h₁与原始特征向量V_j的特征值fv₁到fv_d的哈希函数结果。图5示出了所得的紧凑特征向量集502，它以哈希值表的形式示出，其中每一行表示各自的紧凑特征向量K_j。每个紧凑特征向量具有各自的标识(ID)K_j，其中1≤j≤n，还具有m个二进制值的序列。在图5中，m＝32。在示例性实施例中，ID K_j为一个存储器指针，其指向组成紧凑特征向量216的m个二进制哈希值的列表。在示例性实施例中，每个紧凑特征向量K_i都关联或包括一个指针(例如，objectID)，其指向所述紧凑特征向量K_i表示的原始特征向量V_i。

再次参考图2，在生成所述紧凑特征向量集502之后，随机绘制森林(random drawforest，简称RDF)索引结构生成过程218生成相应的索引结构219。在这方面，图6示出了根据示例性实施例的所述RDF索引结构生成过程218中执行的步骤。

为了方便参考，下方的表1总结了与RDF索引结构生成过程218相关的参数。

表1：

如步骤602所示，将随机置乱排列SP(1)到SP(n_s)应用于所述紧凑特征向量集502，以生成n_s个扭曲紧凑特征向量集THV集(1)到THV集(n_s)。步骤602的一个示例在图7中示出。随机生成置乱排列SP(1)到SP(n_s)，然后将其应用于将所述紧凑特征向量集502中的哈希值的列位置打乱到各自的扭曲紧凑特征向量THV集(1)到THV集(n_s)的不同的列位置上。如上所述，每个紧凑特征向量K_j包括m个二进制值。在一个示例性实施例中，所述紧凑特征向量集502中的每个紧凑特征向量K_j的s位的第一子集用作segmentID，并且只有每个紧凑特征向量K_j的(m-s)位在步骤602中被打乱。因此，在示例性实例中，置乱排列SP(1)到SP(n_s)中的每个置乱排列规定了所述紧凑特征向量的随机再打乱顺序。举例来说，在图7中，所述置乱排列SP(1)到SP(n_s)中的每个位置对应所述对应扭曲紧凑特征向量集THV集(1)到THV集(n_s)中的一个位位置列，该位置上的值是指所述紧凑特征向量集502中的位位置列c+s，用作填充所述扭曲紧凑特征向量集THV集(i)中的列的源二进制值。

例如，在图7中，m＝32且s＝4。置乱排列SP(1)的第一个位置上的第一个值为15，意味着紧凑特征向量集502中的紧凑特征向量K₁的第19(15+s)个哈希值位(其为“1”)将被重新定位到THV集(1)中的紧凑特征向量K₁的第一个置乱哈希值位位置，如线702所示。因此，随机置乱排列步骤602生成所述紧凑特征向量K₁到K_n的n_s个扭曲哈希值版本。在每个扭曲哈希值版本中，哈希值位顺序是相对于所述紧凑特征向量集502的顺序随机打乱的。然而，在每个THV集中，所有紧凑特征向量K₁到K_n的随机置乱顺序是相同的，如此，在所述置乱过程中保持了列的相似度。通过生成所述紧凑特征向量集502的n_s个扭曲版本，由于不再对任何特定的哈希值位顺序分组有任何偏见，上述MSB问题可以得到缓解。如图7中的THV集所示，在示例性实施例中，segmentID的s位被前置在每个所述THV集合中的每个所述紧凑特征向量K_j的(m-s)个置乱位的前面。通过将所述紧凑特征向量K_j的前s位用作segmentID，来支持下述索引的并行性—特别是，可能的segmentID的数量为2^s。

再次参考图6，RDF索引结构生成过程218的下一个任务(604)是为所述扭曲紧凑特征向量集THV集(1)到THV集(n_s)中的每个扭曲紧凑特征向量集生成各自的LSH索引表T(1)到T(n_s)。为所述扭曲紧凑特征向量集THV集(1)到THV集(n_s)中的每个扭曲紧凑特征向量集重复执行一次如图6中的步骤610到步骤622所示的LSH索引表生成任务604，以得到n_s个LSH索引表。

现在将在扭曲紧凑特征向量集THV集(y)(其中1≤y≤n_s)的情况下，结合图8对LSH索引表生成任务604进行描述，其中，图8以图形方式示出了对紧凑特征向量集THV集(y)执行LSH索引表生成任务604以生成相应的LSH索引表T(y)的步骤。图8示出了所述LSH索引表T(y)生成时的阶段801A、801B、801C和801D。表802是在LSH索引表T(y)中索引的所述紧凑特征向量集THV集(y)的十进制表达方式。特别地，在表802中，列“段”是各个扭曲紧凑特征向量K_i的前四位(例如，segmentID)的十进制值，列“级别1”是接下来7位(例如，前7个置乱位)的十进制值，列“级别2”是再接下来7位的十进制值，列“级别3”为再接下来7位的十进制值，列“级别4”是再接下来7位的十进制值。因此，在图8的示例中，m＝32，s＝4，每个扭曲紧凑特征向量K_j的置乱位数为m-s＝28，7位级别的数量为4。在图8的示例中，segmentID位是“1001”，提供的十进制segmentID＝9。

如图8所示，LSH索引表T(y)为包括两种节点的节点树结构，其中，两种节点表示为k节点和d节点。如图8底部所示的LSH索引表T(y)包括两种级别的d节点(第一级别或根d节点(d节点(1))和第二级别d节点(d节点(2)))，以及五种级别的k节点(k节点(1)到k节点(5))。k节点(1)到(5)中的每个k节点对应紧凑特征向量集THV集(y)的各自的紧凑特征向量K₁到K₅。在示例性实施例中。每个LSH索引表T(y)包括n个k节点，其中，n为紧凑特征向量K_j的数量。

每个d节点(i)是l_i个槽(在图中记为槽()，在图8中编号为槽(0)到槽(127)，其中，l_i＝128)的整数数组，其中，l_i小于或等于预定义的槽最大值l。每d节点级别的槽数l_i是可变的。每个d节点槽()对应一桶紧凑特征向量K，该紧凑特征向量K被标识为彼此满足相似度阈值。每个k节点包含两个域，即KEY 804和POINT 806。KEY 804是指向原始特征向量的objectID(例如，K₁指向V₁)，POINT 806存储同一个槽中下一个k节点的偏移量(如果有)。d节点槽用于存储指向与所述槽关联的第一k节点(假设与所述槽关联的k节点数量不超过阈值Th)，或另一个d节点级别(如果与所述槽关联的k节点数量超过所述阈值Th)的指针。

如图6中的步骤610所示，LSH索引表生成任务604开始于将作为第一级别或根d节点(1)的长度为l的d节点进行初始化。如上所述，为了支持并行性，每个紧凑特征向量K的前s位被视为segmentID，允许2s段。对于每个扭曲紧凑特征向量集THV集(y)来说，这是个足以最大化并行性的数目。在示例性实施例中，每个扭曲紧凑特征向量K_j中用于将相应的数据对象分类或定位到各自的d节点槽中的哈希值位数为log₂(l)，d节点级别的最大数目为(m-s)/log(l)。如下所述，任务604根据连续扭曲哈希位的长度为log₂(l)的分组间的相似度将扭曲紧凑特征向量K_j分类到各自的d节点槽中。在这方面，log₂(l)个位的集合充当相似度阈值。

在示例性实施例中，所述阈值Th表示不进行进一步的子分类的情况下可以被分类到单个槽中的数据对象的数量。当超过阈值Th时，需要进行进一步的分类或排序，其通过添加另一个d节点级别完成。然后，所述扭曲紧凑特征向量就可以根据另一个log₂(l)个位的集合进行进一步分类。因此，可以使用紧凑特征向量的哈希值中的逐渐增加的更多位来提供更多的d节点索引级别。当同一个槽下有超过Th个k节点时，它们将重新分配到LSH索引表(y)的哈希树结构的下一个d节点级别。

在图8所示的示例中，l＝128；Th＝3；s＝4；m＝32；m-s＝28；log₂(l)＝7；置乱排列SP(y)的28个值为{15，7，3，4，21，6，20，14，16，26，19，28，25，18，24，13，22，9，17，27，5，2，1，11，8，10，23，12}；得到的THV集(y)的第一个扭曲紧凑特征向量的32位二进制序列为：

扭曲紧凑特征向量K₁＝10010011010000100011011010000101

(包括4位segmentID，后面跟着28个置乱位)。(请注意，图8中的K_j的示例与图5到图7所示的示例不是相同的二进制序列)。

因此，在步骤610中，将第一级别或根d节点(1)初始化为具有l＝128个槽的长度(如图8中的阶段801A所示)。如图6中的步骤612所示，为所述扭曲紧凑向量THV集(y)获得下一个可用的紧凑特征向量K_j。首先对扭曲紧凑特征向量集执行步骤612，下一个可用的紧凑特征向量将为THV集(y)中的第一个紧凑特征向量，即K₁。值得注意的是，步骤602和612可以结合在一起，特定的紧凑特征向量K_j的扭曲哈希值则可以确定为步骤612的一部分，而不是在步骤602中预先计算。

如步骤613中所示，为所述紧凑特征向量K_j初始化各自的k节点(i)。如上所述，所述k节点包含两个域，即KEY 804和POINT 806。因此，在扭曲紧凑向量K₁的示例中，将k节点(1)的KEY 804设置为指向对应的原始特征向量V₁。当新的k节点被初始化时，其POINT 806域最初设置为空。

如步骤614所示，然后从所述扭曲紧凑特征向量K_j中提取segmentID和SlotID。在扭曲紧凑特征向量K₁的所示示例中，前四位提供SegmentID＝(1001)_b＝9。K₁的下一个log₂(l)＝7位为(0011010)_b＝26，提供级别1的d节点(1)SlotID为26。

如步骤616中所示，确定所标识的d节点槽(SlotID)是否为空。如果所述槽没有被占用，如步骤618和图8中的阶段801A所示，将根d节点(1)的对应槽(例如，槽(26))中的值更新为指向系统存储(例如，下述的系统存储设备1408)中相应的k节点位置(例如，k节点(1))的地址，(如上所述，k节点(j)自身指向对应的原始特征向量V_i的地址)。

在更新了各自的d节点槽之后，如步骤619中所示，确定所述扭曲紧凑特征向量集THV(y)中的所有n个紧凑特征向量是否都被分类到所述TSH索引表T(y)中。如果是，则所述LSH索引表T(y)已经完成，并终止所述THV集(y)的任务604。如果否，重复任务604。如步骤612中所示，从所述THV集(y)中检索下一个紧凑特征向量K_j。在图8的示例中，所述下一个紧凑特征向量是K₂。如图8中的阶段801B和图6中的步骤613和步骤614所示，针对所述紧凑特征向量K₂初始化第二k节点(2)，并提取segmentID和级别1的SlotID(如表802中所示，在所示示例中，和K₁相同，K₂的segmentID＝9，级别1的SlotID＝26。)。对于紧凑特征向量K₂，在步骤616中确定d节点槽(SlotID)(例如，槽(26))是否被占用。因此，如步骤620所示，然后确定没有中间d节点层的情况下，分配给所述槽(SlotID)的k节点数目是否超过阈值Th。如果d节点槽(SlotID)下的k节点数目等于或小于Th，则可以将新的k节点包含在所述LSH索引表T(y)的哈希树中的这个槽里。特别地，如步骤622所示，所述槽(SlotID)中的值被设置为指向当前k节点(i)，所述当前k节点(j)的POINT域则被设置为指向先前所述槽(SlotID)所参考的k节点的地址。

在图8中，步骤622中的一个示例在阶段801B中示出，该801B显示了更新为指向k节点(2)的槽(26)的值。进而，k节点(2)的POINT 806域被设置为指向k节点(1)(之前在槽(26)中标识过)。

在图8的示例中，为扭曲紧凑特征向量K₃创建的k节点(3)也具有segmentID＝9和级别1的slotID＝26。如图8的阶段801C所示，当处理了扭曲紧凑特征向量K₃之后，将k节点(3)初始化为其KEY 804域指向原始特征向量V₃的objectID(按照步骤613)。按照步骤622，将d节点(1)槽(26)的值更新为指向k节点(3)，并且k节点(3)的POINT 806域被设置为指向k节点(3)。

在图8的示例中，为扭曲紧凑特征向量K₄创建的k节点(4)具有等于9的segmentID和等于1的级别1SlotID(与K₁到K₃的值不同)。因此，如图8中的阶段801D所示，在步骤616中确定槽(1)为空，在步骤618中更新d节点(1)槽(1)的值，使其指向k节点(4)。

在图8的示例中，为扭曲紧凑特征向量K₅创建的k节点(5)具有segmentID＝9和级别1的d节点slotID＝26(仍与K₁到K₃的segmentID和级别1的d节点slotID相同)。这种情况下，在步骤620中，确定所述级别1的d节点槽(26)下的k节点数量是否超过了所述阈值Th。如步骤624和图8底部的LSH索引表T(1)的最终版本所示，将k节点(5)插入所述LSH索引表中需要生成另外的d节点级别(例如，第二级别d节点(2))，并将该较高级别d节点槽下的k节点重新分配到该较低级别d节点槽中。如上所述，使用多个d节点级别有效地让足够相似的对象分类到单个d节点级别槽(如由匹配的一组扭曲哈希值位值确定)中，再分到不同的子桶中。

在图8中的k节点(5)的示例中，通过将第二级别d节点(2)初始化为具有l＝128个槽的长度来实施步骤624。第一级别d节点(1)槽(26)中的值被设置为指向d节点(2)的系统存储地址(而不是直接指向k节点)。将k节点(1)、(2)、(3)和(5)分配到第二级别d节点(2)的槽中的过程类似于上述有关分配到所述第一级别的过程。然而，所述扭曲紧凑特征向量中不同组的扭曲哈希位用于确定第二级别SlotID而不是第一级别SlotID。特别地，使用了所述扭曲紧凑特征向量K₁、K₂、K₃和K₅中的每个扭曲紧凑特征向量中的下一组log₂(l)个哈希位。因此，在K₁＝10010011010000100011011010000101的示例中，前四位提供SegmentID＝(1001)_b＝9；下一个log₂(l)＝7位(0011010)_b＝26，提供级别1的d节点(1)SlotID为26；下一个log₂(l)＝7位(0001000)_b＝8，提供级别2的d节点(2)SlotID为8。在图8的示例中，k节点(1)、(2)和(3)都具有相同的第二级别SlotID为9(如表802中所示)，因此将它们都分配到第二级别d节点(2)槽(9)中。特别地，d节点(2)槽(9)指向k节点(3)，该k节点(3)进而指向k节点(2)，该k节点(2)进而指向k节点(1)。然而，K₅的哈希位12到18标识第二层d节点SlotID为4，因此将k节点(5)分配到第二层d节点槽(4)。

重复LSH索引生成任务604的步骤610到步骤622，直到扭曲紧凑向量集THV集(y)中的所有紧凑特征向量K₁到K_n都被索引到各自的LSH索引表T(y)中。如表802中的4列级别1到级别4所示，在图8的示例中，d节点的最大级别(maximum level，简称Dmax)为4。在一些示例性实施例中，当达到了LSH索引表T的槽中的d节点的最大级别(maximum level，简称Dmax)时，忽视所述阈值Th并且不限制Dmax d节点级别的k节点链的长度。

为所有n_s个扭曲紧凑向量集THV集(1)到THV集(n_s)重复LSH索引生成任务604，以生成n_s个各自的LSH索引表T(1)到T(n_s)，这些索引表作为索引结构219被共同存储在系统存储中。

在示例性实施例中，上述索引生成方法202可以由以下一般步骤总结，这些步骤遵循特征提取过程210。步骤1：计算输入原始特征向量V_i的LSH哈希值，以生成相应的紧凑特征向量K_j。紧凑特征向量K_j的前s位用作segmentID。然后，由随机置乱排列打乱的所述紧凑特征向量K_j的segmentID后的下一个log₂(l)位用于生成一个0到l的整数范围，作为索引表(例如，LSH索引表T(y))中的第一级别(例如，d节点(1))槽的SlotID。步骤2：如果该槽没有被占用，将该槽更新为指向原始特征向量V_i的地址。步骤3：如果该槽被占用了，而且该槽下的对象数量等于或小于Th，那么在该槽下增加一个k节点。如果该槽下的对象数量大于Th，那么在该槽下增加一个新的d节点级别，随后是步骤4：所述置乱排列的下一个log2(l)项用于提供紧凑特征向量K_j对应的log2(l)位作为所述新d节点的SlotID，所述k节点会被重新分配到该新d节点中。

在示例性实施例中，在LSH索引表T(y)中，每个d节点级别的槽数li可以设置为不同的值，如图9所示。所述可变的li控制位数，以定位由LSH索引表T(y)定义的哈希树中的不同d节点级别中的对象。例如，在一个示例中，l＝32，log₂(l)＝5，所述紧凑特征向量的5位用于确定所有d节点级别的槽。通过这个计划，每个d节点级别都以相同的分辨率处理。或者，不同的分辨率可以用于不同的级别。例如，对于第一级别d节点(1)，可以使用较短的l₁，这使得具有少量相似对象的数据集能够获得足够的有效候选。在较低的级别中，位数可以逐渐增加，其中，l₁<l₂<l₃。对象深入的唯一条件是相同槽下的“相似”对象数量等于或大于Th。因此，对于第二级别，为了使这些“相似”对象分到相似度更高的不同“相似”组中，应当提高分辨率。

因此，在示例性实施例中，RDF索引结构生成过程218实现了随机绘制，该随机绘制产生了随机绘制森林(random draw forest，简称RDF)索引结构219，其中，每个LSH索引表T(y)代表所述RDF索引结构219中各自的树。在RDF索引结构生成过程218中执行的所述随机绘制是随机生成的置乱排列(shuffling permutation，简称SP)的函数。

再次参考图2，现在将描述相似度搜索方法204。接收查询对象220。在示例性实施例中，所述查询对象220为非结构化对象数据，例如图像文件、视频样本、音频样本或文本字符串。如特征提取过程222所示，采用与特征提取过程210中将对象208转换为原始特征向量相同的方法将查询对象220转换为原始查询特征向量Qv。然后，使用相同的过程和上述关于降维过程214的之前生成的哈希函数，在LSH降维过程226中将得到的所述原始查询特征向量Qv转换为长度为m的二进制序列紧凑查询向量Qk。

然后，结合用于搜索过程230的所述索引结构219处理所述紧凑查询向量Qk。在示例性实施例中，通过对所述紧凑查询向量Qk应用上述置乱排列SP(1)到SP(n_s)中的每个置乱排列，生成所述紧凑查询向量Qk的n_s个置乱版本Qks(1)到Qks(n_s)。所述n_s个置乱版本Qks(1)到Qks(n_s)中的每个置乱版本用于搜索LSH索引表T(1)到T(n_s)中的相应的一个LSH索引表。例如，根据置乱排列SP(y)打乱的紧凑查询向量Qks(y)用于搜索对应的LSH索引表T(y)。特别地，紧凑查询向量Qks(y)的第一组log₂(l₁)位(不包括用于segmentID的s位)用于确定LSH索引表T(y)的根(例如，第一级别)d节点(1)的SlotID。如果第一级别d节点(1)的匹配槽指向k节点，那么在该槽下的k节点中寻址的所有对象208会作为候选结果232被返回。如果第一级别d节点(1)的匹配槽指向第二级别d节点，那么紧凑查询向量Qks(y)的下一组log₂(l₂)位用于确定LSH索引表T(y)的第二级别d节点(2)的SlotID。并且，在没有中间d节点的情况下，任何直接在所述匹配d节点(2)下的k节点中寻址的对象208会作为候选结果232被返回。如果所述匹配的d节点(2)槽指向另一个第三级别d节点(3)，重复从所述紧凑查询向量Qks(y)的连续位中确定另外的较低级别的SlotID的过程，直到任何匹配槽下的所有k节点都被处理完，并且所有候选结果232都被返回。

因此，在完成搜索过程230时，所述候选结果232包含对象208，它们对应于在各自的LSH索引表T(1)到T(ns)中标识的置乱查询向量Qks(1)到Qks(ns)中的每个置乱查询向量。如图2中的232到240所示，然后可以使用滤波过程234滤波所述候选结果232，以生成滤波结果236，其中，可以采用排序过程238对该滤波结果236进行排序，以得到排序后的对象列表作为最终结果240。在滤波过程235和排序过程238中使用的方法例如可以与那些用在现有相似度搜索过程中的方法相似。

如上所述，所述索引生成方法202和相似度搜索方法204使用克服所述MSB问题的随机绘制森林(random draw forest，简称RDF)索引结构。将上述RDF索引结构219用于相似度搜索可以在至少一些应用中得到比之前的方法更快、更准确的相似度搜索。通过改进候选结果中包括的高质量候选，当索引结构219用于相似度搜索时，可以在至少一些应用中实现比之前的方法更好的近似最近邻性能(结果的质量和精确度)，还会比之前至少一些方法具有更好的时间性能。

在示例性实施例中，基于上述RDF(随机绘制森林，简称RDF)的相似度搜索的索引生成方法包括：步骤1：根据所述输入原始特征向量，使用局部敏感哈希生成哈希值；步骤2：基于所述哈希值，通过使用随机绘制生成扭曲哈希值；步骤3：基于所述扭曲哈希值，通过遵循自适应哈希树建立步骤，生成随机绘制森林(多个哈希树)；步骤4：基于所述查询对象的原始特征，通过使用局部敏感哈希生成所述查询对象的哈希值；步骤5：将所述查询对象的哈希值和随机绘制森林结合为输入信息，通过遵循相似度搜索策略，从数据集生成所述查询对象的相似对象。

如上所述，在示例性实施例中，索引生成方法202和相似度搜索方法204通过在一个或多个数字处理系统上实现的软件(可以包括一个或多个软件模块)执行。在一些示例中，索引生成方法202或相似度搜索方法204的示例可以在通过一个或多个物理计算系统作为虚拟机实现的一个或多个数字处理系统上实现。

图10示出了数字处理系统1410的一个示例，该数字处理系统1410可用于实现索引生成方法202和相似度搜索方法204之一或两者。如图10所示，所述数字处理系统1410包括至少一个处理单元1400。所述处理单元1400实现所述数字处理系统1410的各种处理操作。例如，所述处理单元1400可以执行数据处理、电源控制、输入/输出处理或使所述数字处理系统1410能够运行的任何其它功能。所述处理单元1400还可用于实现上文更详尽地描述的部分或全部功能和/或实施例。每个处理单元1400包括用于执行一个或多个操作的任何合适的处理或计算设备。例如，每个处理单元1400可以包括微处理器、微控制器、数字信号处理器、现场可编程门阵列或专用集成电路或其组合。

所述数字处理系统1410还包括一个或多个输入/输出设备1406或接口(例如，到互联网或其它网络的有线或无线接口)。所述输入/输出设备1406允许与网络中的用户或其它设备进行交互。每个输入/输出设备1406包括任何合适的结构，例如，扬声器、麦克风、小键盘、键盘、显示器或触摸屏，其中，该结构用于向用户提供信息或从用户接收信息，包括进行用于接收查询对象和传输搜索结果的网络接口通信。

此外，所述数字处理系统1410包括至少一个系统存储设备1408。所述系统存储设备1408存储所述数字处理系统1410所使用、生成或收集的指令和数据。例如，所述系统存储设备1408可以存储由所述处理单元1400执行的、用于实现上述部分或全部功能和/或实施例的软件指令或模块。系统存储设备1408还可以存储一个或多个对象数据库206、主表250、紧凑特征向量集502和索引结构219。系统存储设备1408可以包括任何合适的易失性和/或非易失性存储和检索设备。可以使用任何合适类型的存储器，例如，随机存取存储器(random access memory，简称RAM)、只读存储器(read-only memory，简称ROM)、硬盘、固态硬盘、光盘、用户识别模块(subscriber identity module，简称SIM)卡、记忆棒和安全数码(secure digital，简称SD)存储卡等。

在上述示例中，索引生成方法202为紧凑特征向量集502生成RDF索引结构219，其中，所述紧凑特征向量集502表示存储在对象数据库206中的n个对象208。在上述示例中，所述紧凑特征向量集502被视为单个分区组，并使用单个RDF索引结构219索引。然而，在一些示例中，需要索引的数据对象的量太过庞大，以至于在单个索引结构中表示对应的紧凑特征向量集会造成系统延迟和效率低下，尤其是在并发搜索查询处理的情况下。如上面在背景技术中所述，分区可用于将数据对象组拆分成更小的相似数据对象组，以便进行索引和搜索。

同样如上所述，除了在索引紧凑特征向量时可能会发生的MSB问题之外，子索引分区问题也可能会引起错误。分区是基于哈希的索引生成方法的一个重要部分，如背景技术中所述，现有的分区方法使用固定数量的头位来划分哈希值(例如，将哈希值放到不同的分区组中)。这些现有的方法也许会把非常相似的特征向量分到不同的分区中，或者把极为不同的哈希值放到相同的分区中，仅仅因为它们依赖于有限数量的位。将哈希值分到错误的子索引(例如，分区)中会影响相似度搜索的准确性和一致性。以下描述了改进后的分区方法，以缓解传统分区方法的问题。在当前描述的实施例中，分区方法用于生成分区组，其中，每个分区组后续通过上述RDF索引结构生成过程218分别进行索引。然而，此处描述的分区方法不仅仅局限于与所述RDF索引结构生成过程结合使用，而是在其它示例性实施例中，可以用来生成分区组，其中，这些分区组可以通过已知的或合适的索引方法分别进行索引。

此处描述的分区方法采用使用正交角哈希函数的多层LSH，并与上面结合图2到图9所述的索引生成和搜索方法结合使用。在下面将要描述的示例性实施例中，在进行索引生成方法期间，在索引之前将紧凑特征向量集502划分为多个分区组。然后，为每个分区组创建对应的子索引结构。在这方面，图11A示出了索引生成方法202A，该索引生成方法202A与上述索引生成方法202类似，只是该索引生成方法202A包括一个用于将紧凑特征向量集502总共分成2^M个分区组1到2^M的额外流程(图11A中的分区过程1100)。然后，分别对所述分区组1到2^M进行各自的RDF索引结构生成过程218(1)到218(2^M)，以生成各自的子索引结构219(1)到219(2^M)。

如下面将更详细说明的，所述分区方法使用能够实现索引和搜索方法的并行性的分布式分层LSH方法。它是基于内容的分区策略，使每个搜索查询能够只映射到一个分区组。正交哈希族用于更准确地对(如由紧凑特征向量表示的)对象进行分区。下面描述一种步进式搜索，以提供一种精确的搜索方式来搜索与各个分区组对应的子索引。

现在参考图11A将更详细地说明索引生成方法202A，其中，图11A提供了整个索引生成方法202A的概览。图11B则更详细地展示了分区过程1100。还将参考图12，图12示意性地示出了当子索引分区组的数量为4(即2^M＝4，M＝2)时在m＝6的具体示例下的索引生成方法202A的部分内容。

如图11A中所示，索引生成方法202A包括与上述索引生成方法202相同的初步操作，即特征提取过程210和降维过程214。特别地，特征提取过程210处理n个非结构化数据对象，以生成例如存储在主表250中的n个对应的代表性d维原始特征向量V₁到V_n。其中，该主表250包括具有指向它们各自的非结构化数据对象的指针(例如，objectID)的原始特征向量V₁到V_n。

降维过程214应用第一层LSH来处理所述n个d维原始特征向量V₁到V_n，并生成例如存储为紧凑特征向量集502的n个对应的m维紧凑特征向量K₁到K_n，其中，该紧凑特征向量集502包括具有指向它们各自的原始特征向量V₁到V_n和非结构化数据对象之一或两者的指针(例如，objectID)的紧凑特征向量K₁到K_n。

在示例性实施例中，索引生成方法202A的基于LSH的降维过程214使用上面针对所述索引生成方法202描述的正交角哈希函数h，其性能优于原始角哈希函数。如上所述，使用归并的正交哈希函数，为与对象关联的原始特征向量V₁到V_n中的每个原始特征向量生成来自紧凑特征向量K₁到K_n的哈希值。每个紧凑特征向量K_j是由0和1组成的长度为m的序列。通过示例，图12中所示的降维过程214(其中，m＝6)说明了采用长度为m的哈希函数链G_i＝{h₁，h₂，…，h_m}对原始特征向量V₁＝{fv₁，fv₂，…，fv_d}进行哈希处理，以生成长度为m的二进制序列紧凑特征向量K₁＝G_i(V₁)＝{h₁(V₁)，h₂(V₁)，h₃(V₁)，h₄(V₁)，h₅(V₁)，h₆(V₁)}＝{0，0，1，0，1，0}。

遵循第一层LSH降维过程214，然后通过分区过程1100将紧凑特征向量集502的复合哈希值(例如，紧凑特征向量K₁到K_n)分区到子索引分区组中，其中，该分区过程1100将在图11B中详细描述。所述分区过程1100用于将足够相似的紧凑特征向量K_j分配到各自的分区组中。

为了将相似对象(每个对象由各自的紧凑特征向量K_j表示)分到各自的分区组中，引入了新的LSH索引层，称为分区层LSH索引。所述分区层LSH索引的原理是：在执行过第一层LSH后，(如由原始特征向量表示的)相似对象有很大可能性p1具有相似的哈希值；在执行过第二分区层LSH后，相似的紧凑特征向量有很大可能性p2具有相似的的哈希值。因此，在两层LSH后，相似对象有p1*p2的可能性具有相似的紧凑特征向量。该原理是定义分区组和为每个分区组生成子索引ID(SubID)的基础，如图11A和图12所示。在至少一些示例中，每个紧凑特征向量K_j仅包含在一个分区组中。因此，在搜索时，每个搜索查询只需要访问单个分区组的子索引结构，这提高了相似度搜索的速度。此外，为了处理并发性，所述分区方法的稳健性可以很容易地由单个参数M控制，其中，M是指用于分区到分区组的位数。

如图11B所示，为包含在所述紧凑特征向量集502中的n个紧凑特征向量K_j中的每个紧凑特征向量重复所述分区过程1100，在完成所述分区过程1100时，将n个紧凑特征向量K_j中的每个紧凑特征向量分配到相似紧凑特征向量K_j的分区组1到2^M中的相应的一个分区组中，其中相似度是分区层LSH过程框1104的函数。分区组的数量为2^M，每个分区组以及其各自的子索引结构219(SubID)被映射到唯一的M位子索引ID(SubID)。

如过程框1102所示，每次重复分区过程1100都开始于从所述紧凑特征向量集502中得到下一个紧凑特征向量K_j。如过程框1104所示，然后对所述紧凑特征向量K_j执行分区层LSH，以生成子索引ID(SubID)，从而将所述紧凑特征向量K_j分配到分区组1到2^M中的相应的一个分区组中。在示例性实施例中，应用分区层LSH包括采用包括M个基于正交角局部敏感的哈希函数的哈希函数链G’(例如，K_j＝G’(K_j)＝{h₁(K_j)，h₂(K_j)，…，h_M(K_j)}的SubID)对所述紧凑特征向量K_j进行哈希处理。图13为分区过程1100中的过程框1102和过程框1104的伪代码表达方式，其中，每个紧凑特征向量K_j(在图13中识别和表示为“哈希值矩阵E[j，i]”)被分配各自的的子索引ID(SubID)。图12示出了在过程框1104中应用于6位紧凑特征向量K₁＝{0，0，1，0，1，0}的LSH分区处理的示例。采用函数链G’＝{h₁，h₂}(M＝2)对所述m＝6位的紧凑特征向量K₁进行哈希处理，以输出2位子索引ID(SubID)＝G’(K₁)＝{h₁(K₁)，h₂(K₁)}＝{1，0}。子索引ID的第一二进制值为6位紧凑特征向量K₁＝{0，0，1，0，1，0}和正交哈希函数h₁的哈希输出，子索引ID的第二二进制值为6位紧凑特征向量K₁＝{0，0，1，0，1，0}和正交哈希函数h₁的哈希输出。

如图11B中的过程框1108所示，一旦紧凑特征向量K_j的子索引ID确定，则将所述紧凑特征向量K_j添加到对应的分区组1到2^M中。在图12的示例中，将所述6位紧凑特征向量K₁＝{0，0，1，0，1，0}添加到分区组3中，如由其二进制子索引ID，SubID＝10_b标识。因此，每个紧凑特征向量K_i(及其对应的原始特征向量V_i和非结构化数据对象)是被单独分配到相似向量的子索引分区组中的。

在完成分区过程1100时，将紧凑特征向量集502中的紧凑特征向量K_i到K_n分布到M个分区组中，其中，每个分区组是紧凑特征向量K_i到K_n的子集。如图11A和12中所示，之后会使用各自的RDF索引结构生成过程128(1)到218(2^M)来分别处理M个分区组，以生成各自的RDF子索引结构219(1)到219(2^M)。采用与以上结合图6到图9针对由RDF索引结构生成过程218进行的紧凑特征向量集502的处理描述的方式相同的方式，RDF索引结构生成过程218(1)到218(2^M)中的每个索引结构生成过程处理其各自的子索引分区组。所述各自的RDF子索引结构219(1)到219(2^M)中的每个RDF子索引结构包括各自的LHS索引表T(1)到T(ns)，其中可以为所述RDF子索引结构219(1)到219(2^M)中的每个子索引结构单独选择n_s。

如图11A中虚线框标记的“机器(1)”到“机器(2^M)”所示，在至少一些示例性实施例中，所述RDF子索引结构219(1)到219(2^M)中的每个子索引结构承载在或存储在不同的数字处理系统上，以支持并发查询。在一些示例中，多个不同的数字处理系统可以包括在公共数字处理系统(例如，数字处理系统1410)上或在物理上不同的机器(例如，多个数字处理系统1410)上实现的多个虚拟机。M的大小决定子索引分区组的数量，其影响支持并发查询请求的能力。M越大，处理并发搜索的能力越高。因此，在示例性实施例中，所述子索引结构219(1)到219(2^M)中的每个子索引结构作为独立可搜索的结构存储，使得子索引结构的并发搜索能够实现。

现在将参考图14描述对RDF子索引结构219(1)到219(2^M)的搜索，其中，图14示出了根据示例性实施例的相似度搜索方法204A。相似度搜索方法204A与上面结合图2描述的相似度搜索方法204相似，除了相似度搜索方法204A包括为紧凑特征查询向量Qk生成子索引ID的附加过程(过程1450)以及在至少一些示例性实施例中，使用与所述紧凑特征查询向量Qk的子索引ID类似的子索引ID执行步进式搜索索引结构的附加过程(过程框1454)。如图14所示，所述相似度搜索方法204A包括：特征提取过程222，用于将查询对象转换为d维原始特征查询向量Qv；以及LSH降维过程226，用于将d维原始特征查询向量Qv降为m维紧凑特征查询向量Qk＝G_i(Qv)＝{h₁(Qv)，h₂(Qv)，…，h_m(Qv)}。

在过程1450中应用另一个LSH级别，以确定用于搜索与所述紧凑特征查询向量Qk相似的紧凑特征向量K_i的合适的RDF子索引结构219(SubID)。特别地，将上面针对过程框1104描述的应用第二LSH层的相同操作应用于所述查询向量Qk。特别地，如下通过应用正交角哈希函数G’确定所述查询向量Qk的子索引ID(SubID)：

查询向量Qk的SubID＝G’(Qk)＝{h₁(Qk)，h₂(Qk)，…，h_M(Qk)}。

如图14中的过程1452所示，所述紧凑特征查询向量Qk的SubID用于标识子索引分区的RDF子索引结构219(SubID)，该子索引分区最有可能包括与所述搜索查询对象相似的对象。然后，将上面结合图2所述的相同搜索过程230应用于标识所述RDF子索引结构219(SubID)中的候选结果232。

理想情况下，分区方法力求将所有相似对象划分到一个子索引分区组中。然而，由于应用分区层LSH来分配分区组子索引ID的近似性质，在至少一些应用中，相似对象有可能仍会被划分到不同的分区组中，这会影响使用生成的子索引结构进行的相似度搜索的准确性和一致性。因此，为了提高搜索准确性，在示例性实施例中，基于其它LSH属性实现步进式搜索方法。在图14中的过程框1454(“对具有相似子索引ID的索引结构进行步进式搜索”)和图15中所示的步进式搜索示意图中说明了实现步进式方法所需的其它步骤的示例。

所述步进式搜索方法基于如下假设：彼此相距一步长的子索引结构比彼此相距两步长的子索引更可能包含与搜索查询的紧凑特征向量接近的紧凑特征向量。由于紧凑特征向量的每个位只有两个可能的值0/1，两个紧凑特征向量之间的汉明间距可以记为增量步长，最大增量步长数量为M个步长。

在示例性实施例中，如过程1452所示，最初，搜索对应于为所述紧凑特征查询向量Qk生成的子索引ID的子索引结构219(SubID)。然而，为了提高准确性，还要搜索1步长子索引结构，随着搜索的子索引的数量的增加，时间效率逐渐降低。在一些示例性实施例中，用于搜索的1步长子索引结构的数量被设置为M(即与用于子索引ID的位数相同)。使用该方法，可以在某些情况下通过在合理数量的子索引结构中进行搜索来实现更高的准确性。

为了标识特定的SubID的Δ步长子索引结构，对原始子索引ID中的Δ位应用+1(用于位＝0)或者-1(用于位＝1)。例如，如果Q_k的原始子索引ID为SubID＝G’(Q_k)＝{h₁(Q_k)，h₂(Q_k)，…，h_M(Q_k)}，那么通过在G’(Qk)中的一个随机位上应用+1/-1操作确定1步长子索引ID，通过在SubID＝G’(Qk)中的两个随机位上应用+1/-1操作确定2步长子索引ID，以此类推。例如，从图15中可以看出，如果M＝3，原始子索引ID为010，1步长子索引ID为110、000和011，2步长子索引ID为100、111和001，3步长子索引为101。

因此，在示例性实施例中，所述过程框1454(对具有相似子索引ID的索引结构进行步进式搜索)包括：如过程框1456所示，确定所有子索引结构219(SubID)的子索引ID，这些ID属于“原始”或“0步长”子索引ID的阈值相似度范围内(其中，“原始”或“0步长”子索引ID为所述紧凑查询函数向量Q_k的SubID)。在示例性实施例中，阈值为属于最大步长数(例如M)范围内的SubID范围内的最大步长(例如，位变化)数。因此，在图15的示例中，M＝3，原始SubID＝{0，1，0}，然后将存在与原始SubID有一位不同的3个“1步长”SubID，即：{1，1，0}、{0，0，0}和{0，1，1}，与原始SubID有两位不同的3个“2步长”SubID，即：{0，0，1}、{1，1，1}和{1，0，0}，以及与原始SubID有三位不同的1个“3步长”SubID，即：{1，0，1}。

如过程框1458中所述，然后对被标识为落在最大步长范围内的各个子索引结构219(SubID)分别进行搜索，以识别与所述紧凑查询函数向量Q_k相似的任何紧凑向量K_i。在示例性实施例中，这样的搜索通过上述搜索过程230来执行，并对每个搜索的子索引结构219(SubID)返回一组候选结果232。在示例性实施例中，所述候选搜索结果可能会被滤波并排序。

在至少一些示例中，可以由数字处理系统1410基于预先确定的搜索结果阈值针对每个紧凑查询函数向量Q_k分别确定执行步进式搜索以及这种搜索的扩展。例如，如果在搜索了对应于所述原始子索引ID的子索引结构之后，达到了候选搜索结果的阈值数，则不需要执行额外的步进式搜索(即过程框1454)。类似地，如果执行了额外的步进式搜索，那么如果在完成最大数量的步进式搜索之前达到了候选搜索结果的阈值数，则可以终止额外的子索引结构的步进式搜索。

如上所述，在至少一些示例性实施例中，RDF子索引结构219(1)到219(2M)中的每个子索引结构承载在或存储在不同的数字处理系统上以支持并行查询。这些系统可以基于不同的对象查询来支持并行查询，或基于相同的对象查询支持并行步进式查询。

在至少一些示例性实施例中，上述方法和系统可以解决现有大数量非结构化数据存储系统、索引系统和搜索系统中一些固有的时间和处理效率低下的问题，从而提高搜索准确性、搜索速度以及包括处理器时间和功耗的系统资源的利用率中的一项或多项。

提供一些实施例的以上描述是为了确保任何本领域技术人员能够构造或使用根据本发明的装置、方法或计算机可读介质。

对于本领域技术人员来说，对此处所述实施例进行的各种修改可能是显而易见的，并且此处所述方法和设备的一般原则可以应用于其它实施例。因此，本发明并非旨在限于此处示出的实施例，而是在最广泛的范围内与此处所公开的原理和新颖特征一致。

例如，尽管实施例主要参考位进行描述，但其它实施例可以涉及非二进制和/或多位符号。

Claims (24)

1.一种用于对多个数据对象进行分区的方法，其特征在于，每个数据对象由各自的高维特征向量表示，包括：

对每个高维特征向量执行哈希函数，以为由所述高维特征向量表示的数据对象生成各自的低维二进制紧凑特征向量；

对每个紧凑特征向量执行另一个哈希函数，以将子索引ID分配给所述紧凑特征向量；

将紧凑特征向量分区到各自的分区组中，其中，所述各自的分区组对应于分配给所述紧凑特征向量的子索引ID；

为每个所述各自的分区组生成可搜索的子索引结构；

将所述子索引结构作为独立可搜索的结构存储，使得所述子索引结构彼此间可以并发搜索；其中，所述为每个所述各自的分区组生成可搜索的子索引结构包括：对于每个分区组：

为所述分区组中的紧凑特征向量生成多个扭曲紧凑特征向量集，其中，每个所述扭曲紧凑特征向量集是通过对所述分区组中的紧凑特征向量应用各自的随机置乱排列生成的；

对于每个扭曲紧凑特征向量集，基于所述扭曲紧凑特征向量集中的哈希值的序列，为由所述分区组中的紧凑特征向量表示的数据对象生成索引表；

包括为所述分区组的可搜索子索引结构中的每个所述扭曲紧凑特征向量集生成的索引表。

2.根据权利要求1所述的方法，其特征在于，对每个高维特征向量执行的所述哈希函数为局部敏感哈希(locality sensitive hashing，简称LSH)函数，对每个紧凑特征向量执行的所述另一个哈希函数也是LSH函数。

3.根据权利要求2所述的方法，其特征在于，所述哈希函数和所述另一个哈希函数为正交角哈希函数。

4.根据权利要求3所述的方法，其特征在于，每个紧凑特征向量仅分区到单个所述分区组。

5.一种用于对数据对象进行分区的系统，其特征在于，每个数据对象由各自的高维特征向量表示，包括：

一个或多个处理单元；

系统存储设备，与每个所述处理单元耦合，所述系统存储设备上有形地存储可执行指令，当所述可执行指令由所述一个或多个处理单元执行时，使得所述系统：

对每个高维特征向量执行哈希函数，以为由所述高维特征向量表示的数据对象生成各自的低维二进制紧凑特征向量；

对每个紧凑特征向量执行另一个哈希函数，以将子索引ID分配给所述紧凑特征向量；

将紧凑特征向量分区到各自的分区组中，其中，所述各自的分区组对应于分配给所述紧凑特征向量的子索引ID；

为每个所述各自的分区组生成可搜索的子索引结构；

当所述可执行指令由所述一个或多个处理单元执行时，使得所述系统将所述子索引结构作为独立可搜索的结构存储在一个或多个存储器中，使得所述子索引结构彼此间可以并发搜索；其中，当所述可执行指令由所述一个或多个处理单元执行时，使得所述系统通过以下操作为每个所述各自的分区组生成所述可搜索子索引结构：

为所述分区组中的紧凑特征向量生成多个扭曲紧凑特征向量集，其中，每个所述扭曲紧凑特征向量集是通过对所述分区组中的紧凑特征向量应用各自的随机置乱排列生成的；

对于每个扭曲紧凑特征向量集，基于所述扭曲紧凑特征向量集中的哈希值的序列，为由所述分区组中的紧凑特征向量表示的数据对象生成索引表；

包括为所述分区组的可搜索子索引结构中的每个所述扭曲紧凑特征向量集生成的索引表。

6.根据权利要求5所述的系统，其特征在于，对每个高维特征向量执行的所述哈希函数为局部敏感哈希(locality sensitive hashing，简称LSH)函数，对每个紧凑特征向量执行的所述另一个哈希函数也是LSH函数。

7.根据权利要求6所述的系统，其特征在于，所述哈希函数和所述另一个哈希函数为正交角哈希函数。

8.根据权利要求7所述的系统，其特征在于，包括：每个紧凑特征向量仅分区到单个所述分区组。

9.一种计算机程序产品，其特征在于，包括一种媒介，其上有形地存储可执行指令，当所述可执行指令由数字处理系统执行时，使得所述数字处理系统：

对多个高维特征向量中的每个高维特征向量执行哈希函数，以生成各自的低维二进制紧凑特征向量，每个所述高维特征向量表示各自的数据对象；

对每个紧凑特征向量执行另一个哈希函数，以将子索引ID分配给所述紧凑特征向量；

将紧凑特征向量分区到各自的分区组中，其中，所述各自的分区组对应于分配给所述紧凑特征向量的子索引ID；

为每个所述各自的分区组生成可搜索的子索引结构；

将所述子索引结构作为独立可搜索的结构存储，使得所述子索引结构彼此间可以并发搜索；其中，所述为每个所述各自的分区组生成可搜索的子索引结构包括：对于每个分区组：

为所述分区组中的紧凑特征向量生成多个扭曲紧凑特征向量集，其中，每个所述扭曲紧凑特征向量集是通过对所述分区组中的紧凑特征向量应用各自的随机置乱排列生成的；

对于每个扭曲紧凑特征向量集，基于所述扭曲紧凑特征向量集中的哈希值的序列，为由所述分区组中的紧凑特征向量表示的数据对象生成索引表；

包括为所述分区组的可搜索子索引结构中的每个所述扭曲紧凑特征向量集生成的索引表。

10.一种用于搜索与查询对象相似的数据对象的方法，其特征在于，包括：

将所述查询对象转换为d维特征向量；

对所述d维特征向量执行哈希函数，以为所述查询对象生成m维二进制查询向量，其中m<d；

对所述查询向量执行另一个哈希函数，以确定所述查询向量的子索引ID；

在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，所述子索引结构包括紧凑特征向量的索引，其中，每个紧凑特征向量表示各自的数据对象，所述子索引结构为独立可搜索的结构，使得所述子索引结构彼此间可以并发搜索；

其中，在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，包括：

为所述查询向量生成多个扭曲查询向量，其中所述多个扭曲查询向量是通过应用各自的随机置乱排列生成的；

在与所述子索引ID对应的子索引结构中根据所述扭曲查询向量进行搜索，以搜索与所述查询向量相似的紧凑特征向量。

11.根据权利要求10所述的方法，其特征在于，对所述d维特征向量执行的所述哈希函数为局部敏感哈希(locality sensitive hashing，简称LSH)函数，对所述查询向量执行的所述另一个哈希函数也是LSH函数。

12.根据权利要求11所述的方法，其特征在于，所述哈希函数和所述另一个哈希函数为正交角哈希函数。

13.根据权利要求10至12中任一项所述的方法，其特征在于，还包括：

确定另外的子索引ID的集合，其中，所述另外的子索引ID属于所述查询向量的所述子索引ID的相似度阈值范围内；

在与所述另外的子索引ID对应的另外的子索引结构中搜索与所述查询向量相似的紧凑特征向量。

14.根据权利要求13所述的方法，其特征在于，所述相似度阈值是指相对于所述查询向量的所述子索引ID的所述另外的子索引ID中不同位值的阈值级别。

15.根据权利要求13所述的方法，其特征在于，如果在所述另外的子索引ID对应的所有所述子索引结构被搜索之前达到了搜索结果的阈值数，则终止对另外的子索引结构的搜索。

16.根据权利要求10至12中任一项所述的方法，其特征在于，包括：在与所述子索引ID对应的子索引结构中进行搜索的同时：在另一个子索引结构中搜索紧凑特征向量，其中，所述紧凑特征向量与确定了另一个子索引ID的另一个查询向量相似。

17.一种用于搜索与查询对象相似的数据对象的系统，其特征在于，包括：

一个或多个处理单元；

系统存储设备，与所述一个或多个处理单元中的每个处理单元耦合，所述系统存储设备上有形地存储可执行指令，当所述可执行指令由所述一个或多个处理单元执行时，使得所述系统：

将所述查询对象转换为d维特征向量；

对所述d维特征向量执行哈希函数，以为所述查询对象生成m维二进制查询向量，其中m<d；

对所述查询向量执行另一个哈希函数，以确定所述查询向量的子索引ID；

在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，所述子索引结构包括紧凑特征向量的索引，其中，每个紧凑特征向量表示各自的数据对象，所述子索引结构为独立可搜索的结构，使得所述子索引结构彼此间可以并发搜索；

其中，在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，包括：

为所述查询向量生成多个扭曲查询向量，其中所述多个扭曲查询向量是通过应用各自的随机置乱排列生成的；

在与所述子索引ID对应的子索引结构中根据所述扭曲查询向量进行搜索，以搜索与所述查询向量相似的紧凑特征向量。

18.根据权利要求17所述的系统，其特征在于，对所述d维特征向量执行的所述哈希函数为局部敏感哈希(locality sensitive hashing，简称LSH)函数，对所述查询向量执行的所述另一个哈希函数也是LSH函数。

19.根据权利要求18所述的系统，其特征在于，所述哈希函数和所述另一个哈希函数为正交角哈希函数。

20.根据权利要求17至19中任一项所述的系统，其特征在于，所述可执行指令还使得系统：

确定另外的子索引ID的集合，其中，所述另外的子索引ID属于所述查询向量的所述子索引ID的相似度阈值范围内；

在与所述另外的子索引ID对应的另外的子索引结构中搜索与所述查询向量相似的紧凑特征向量。

21.根据权利要求20所述的系统，其特征在于，所述相似度阈值是指相对于所述查询向量的所述子索引ID的所述另外的子索引ID中不同位值的阈值级别。

22.根据权利要求20所述的系统，其特征在于，如果在所述另外的子索引ID对应的所有所述子索引结构被搜索之前达到了搜索结果的阈值数，则终止对另外的子索引结构的搜索。

23.根据权利要求17至19中任一项所述的系统，其特征在于，所述可执行指令还使得系统在与所述子索引ID对应的子索引结构中进行搜索的同时：在另一个子索引结构中搜索紧凑特征向量，其中，所述紧凑特征向量与确定了另一个子索引ID的另一个查询向量相似。

24.一种计算机程序产品，其特征在于，包括一种媒介，其上有形地存储可执行指令，当所述可执行指令由数字处理系统执行时，使得所述数字处理系统通过以下操作搜索与查询对象相似的数据对象：

将所述查询对象转换为d维特征向量；

对所述d维特征向量执行哈希函数，以为所述查询对象生成m维二进制查询向量，其中m<d；

对所述查询向量执行另一个哈希函数，以确定所述查询向量的子索引ID；

在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，所述子索引结构包括紧凑特征向量的索引，其中，每个紧凑特征向量表示各自的数据对象，所述子索引结构为独立可搜索的结构，使得所述子索引结构彼此间可以并发搜索；

其中，在与所述子索引ID对应的子索引结构中搜索与所述查询向量相似的紧凑特征向量，包括：

为所述查询向量生成多个扭曲查询向量，其中所述多个扭曲查询向量是通过应用各自的随机置乱排列生成的；

在与所述子索引ID对应的子索引结构中根据所述扭曲查询向量进行搜索，以搜索与所述查询向量相似的紧凑特征向量。