对大规模高维数据集进行快速的基于相似性的查询、自连接以及连接的方法和设备

摘要

一种利用相似性索引(400)对大规模高维数据集进行快速的、基于相似性的查询、自连接和连接的方法和设备。

说明书

相关申请

本专利申请要求2006年6月27日提交的题为“Method and Apparatus for fast Similarity-based query，self-join，and join for massive，high-dimension datasets”的美国临时申请序号60/805,926的优先权，其与本申请是同一发 明人，并因此在这里通过引用并入。本专利申请要求2007年6月24日提 交的题为“Method and Apparatus for fast Similarity-based query，self-join，and join for massive，high-dimension datasets”的美国申请序号11/767,521的优 先权，其与本申请是同一发明人，并因此在这里通过引用并入。

发明领域

本发明涉及数据集。更具体地，本发明涉及对大规模高维数据集进行 快速的基于相似性的查询、自连接(self-join)以及连接的方法和设备。

发明背景

基于相似性(Similarity)的大规模数据集的连接是许多重要问题的核 心。例如，在信息检索领域内的一个重要的问题是数据挖掘，数据挖掘寻 找在例如文档、图像或其它非结构化(unstructured)的内容的项(item)的集合 之间识别模式。一般地，有某种准则来衡量在数据成员之间的相似性，其 可作为数学公式表达。一般地，我们有两个大规模数据集，并且我们想“连 接”数据集以识别对(pair)或集群(cluster)，其中每个数据集至少有一个成 员与来自其他数据集的另一个成员相似。一个重要的特殊情形是“自连 接”，识别在单个数据集内的副本、近副本或非常相似的项。一个重要应 用是内容可寻址存储和智能文件存储的出现区域，其中，或者相对于参考 集合，或者相对于其自身，连接目标数据集，以识别副本和近副本。虽然 计算机变得更迅速，存储变得更广泛，且内容变得更多样，但是对大规模 数据集进行有效判断(effective sense)的能力并没有跟上。这就出现了问 题。

附图简述

通过实施例的方式说明本发明，并不限于附图的图形，其中：

图1说明了其中可实现本发明的方法和设备的网络环境；

图2是其中可实现本发明的一些实施方式以及可使用本发明的一些实 施方式的计算机系统的结构图；

图3说明了显示建立大量相似性索引(bulk similarity index)的本发明 的一种实施方式；

图4说明了显示相似性索引树的实施例的本发明的一种实施方式；

图5说明了显示查询的本发明的一种实施方式；

图6说明了显示自连接的本发明的一种实施方式；

图7说明了本发明的一种实施方式，显示自连接树的实施例；以及

图8说明了显示常规连接(general join)的本发明的实施方式。

详细描述

介绍

为了描述本发明，下述内容可帮助读者。非结构化的内容项是信息的 单元(unit)，例如文本、图像、音频、视频、基因组(genomic)序列或能由计 算机存储器中的比特表示的任何实体。数据集是非结构化的内容项的集 合。一般地，数据集里的项不是具有就是被认为具有某种关联。例如，它 们可以是来自照片集合的静止图像，或在数据集里的项可以是来自法律文 档或来自小说的段落。作为附带说明，我们指出，想探究项是否有关联时， 可在数据集里插入项，例如当我们组合来自各种各样不同物种的DNA序 列的片段，或组合来自监视视频的帧时。

将非结构化的内容表示为向量

形式上，我们将内容项x指示为来自内积空间的元素，我们也将内积 空间称为向量空间。此外，我们将有时将内容项称为来自这个向量空间的 向量。作为快速回顾，内积空间S所具有的属性列在附录1。我们使用在 之前的申请【参考R.Nakano的日期为2005年2月的美国专利申请第 11/361166号的“Method and apparatus for efficient indexed storage for unstructured content”】里的内积空间的属性。

内积空间具有距离函数D(x，y)，其表示在空间里两个元素之间距离 的实数。这对我们非常重要，因为我们感兴趣的是两个内容项是如何相似 或相异的。例如，我们可能对两个网页的内部结构的相似性感兴趣，以最 有效率地表示逻辑，从而从大集合的网页提取内容。或者我们想在企业政 策报告的资料库里或法律条款的系统信息中心库(repository)里识别副本和 近副本文本项。

在我们挑选的内积空间里，我们把内容项和它的具体表示区分开。例 如，在文本应用中，我们选定把在特定序列的每个词分配给记号(token)的 文本的表示。一种提取符号策略(tokenization strategy)是“断词(stem)”， 以便将复数的词尾和其它不同词尾分配给相同的记号。或者，我们可决定 数量映射到相同的记号，以便“3bears”和“100bears”是等价的，也就 是一个数量跟着是记号“bear”。在向量表示方面，两个向量可能相等，但 是所隐含的内容项可不同。另外的实施例衡量文档相似性，其包括由出现 在文档内的关键词和每个关键词出现的数量来对文档进行表示。这是术语 (term)文档向量。用这种表示形式，例如“like an arrow”和“an arrow like” 的文本序列包含每个关键词“arrow”和“like”的一次出现。它们的向量 是相等的，且因此在向量空间意义里它们是相等的。但是所隐含的内容项 是不同的。我们引入这个特性，是因为我们使用数据集成员的向量空间表 示，但是我们允许内容项维持它们隐含的特征。事实上，我们可对单个项 选择引入多种向量表示。

内积、距离、相似性

为了我们的目的，假定我们已经选定了表示形式，其将内容项映射到 向量。明确的，给定内容项的集合，我们选定一种表示形式，其将每个项 分配到在内积空间S里的向量x。给定S内的两个元素x、y，我们将内积 记为<x，y>。附录1总结了内积空间的属性。

距离(Distance)d(x，y)＝sqrt(<x-y，x-y>)。

从这个定义，我们看出如果两个向量x和y相等，那么在它们之间的距离 也是零。记住，我们允许两个向量相等，但是相应的内容项可以不同。

具有内积是方便的，因为它给我们提供了对数据集里两个项的相似性 进行表示的方式。当我们具有其对应向量表示非零的两个内容项时，我们 引入相似性的概念：

相似性(Similarity)(x，y)＝<x，y>/sqrt(<x，x>*<y，y>)。

相似性是有用的概念，因为相似性是在0和1之间的数字。当在它们之间 的距离为零时，两个向量具有一的相似性或100％相似性。

相似性是吸引人的，因为它理解简单。给定数据目标的族，可以有表 达相似性的数学方式，其容易掌握、计算直接，且最重要的是，与人们关 于两个目标相似程度的直觉一致。

然而，在实践中，将相似性应用到大型数据集变得有问题。假设数据 集包含N个项，且我们想在数据集里寻找相似的项。

当向量空间S的维数小时，例如，在一维的情形，向量空间减小到严 格有序的集合，且我们能够在O(n*log(n))时间里对数据集分类，并简单 计算在有序集里的邻近项的受限集的相似性，。

对于最感兴趣的非结构化的内容数据集，维度为高。例如，在术语文 档表示里，向量空间的维度与可能的关键词的数量相等，其能容易排列到 数百或更多。除了简单关键词的方法，更复杂的表示可使用在文档内的词 序列。在这些情况，向量空间的维数与邻近的词的不同的n元文法(n-gram) 的数量成比例，并且维度扩展到好几万。

对于基因组序列数据集，一般考虑16连续核苷酸的n元文法，其中， 在n元文法内的每个位置有4个可能的选择。一般地，如果数据集由长度 为k的核苷酸序列组成，则向量空间的理论维数大概是k^Λ4^Λ16，或者k升 高到四十亿幂。考虑到几百核苷酸的序列被认为是短的，我们正在处理巨 大维数的问题。

定义

为了描述本发明的目的，术语的下述定义(在括号里)可帮助读者。

(一致的)我们说当它们的向量表示是向量空间S的成员，且存在空 间S的内积时，项x.i的集合和集x.i是一致的。

例如，假设我们有两个数据集，都由静止图像组成。此外，我们已经 选定在两个数据集上应用相同的变换，特定地为亮度、对比度、比例和方 位来对像素值进行规范化，为每个图像产生高维度向量。我们想知道，比 如说在一对图像里是否有相似的图像，或者是否有彼此相似图像的集群。 通过这种构造(construction)，我们说数据集是一致的。

(s-集群)我们说，当对于在集合里的任何项x，对集合里的项具有大 于或等于s的相似性时，一致的项集合形成s-集群。

(自连接)给定数据集D，在D里识别s-集群，s是在0和1之间的 相似性阈值。

(查询)给定项q、数据集D和在0和1之间的相似性阈值s，其中q 与D一致。考虑q和D的联合(union)，在包括q的那个联合里识别任何 s-集群。

(s-连接集群)给定在数据集D.1里的向量x.i和在数据集D.2里的向 量y.i，其中D.1和D.1是一致的。s-连接集群是至少一个成员来自D.1且 一个成员来自D.2的s-集群。

(常规连接)给定在数据集D.1里的向量x.i和在数据集D.2里的向量 y.i，其中D.1和D.1是一致的。识别所有s-连接集群。

实施方式

我们将以下面的顺序继续讨论本发明的不同实施方式。

首先，我们说明如何建立相似性索引。

第二、我们说明如何相对于相似性索引来执行基于相似性的查询。

第三，我们说明执行自连接的快速技术。因为我们方法的计算复杂性 按O(n*log(n))增长，所以认为该算法是快速的。作为对比，强力(brute force) 方法在考虑数据集里的所有可能时，要求n*(n-1)/2次相似性计算或O(nA2) 次运算。

第四，我们说明在两个数据集上如何执行常规连接。这个程序使用自 连接技术作为子程序，并且它还具有O(n1*log(n1+n2*log(n2))次运算的计 算复杂性，其中n1和n2是两个数据集的大小。我们注意到，我们将要描 述的程序比构造这两个数据集的联合要好，其为在结合的数据集上执行自 连接。我们证明用于常规连接的程序的正确性。

建立相似性索引

之前的描述集中在递增树建立的一般情形。【参考R.Nakano的日期为 2005年2月的美国专利申请第11/361166号“Method and apparatus for efficient indexed storage for unstructured content”】。这里为了我们的目的， 我们引入大量(bulk)建立二进制相似索引树的程序，其比更早的递增程 序更简单且更快速。数据集的初始加载是十分普通的操作，它使对那种情 况的优化有意义。

图3一般用300举例说明了显示建立大量相似性索引的本发明的一种 实施方式。在302我们指定叶节点的上限为G项。在302我们输入内容项， 让n代表项的数量，并称所述项为当前集合。在306我们核对以查看是否 n>G。如果不是n>G，那么我们进行308，在308建立叶节点，用n个内 容项将其填充，并从父辈(parent)接通链接，以及然后进行310完成。如果 n>G为真，那么我们进行312，在312，，对当前集合里的所有项计算下述 向量和：vsplit＝sum(i；x.i)/n。我们然后进行314，在314，我们为当前集 合里的每一项计算向量差：d.i＝x.i-vsplit。我们接下来进行316，在316， 我们为当前集合里的每一项计算下述标量值：p.i＝<d.i，vsplit>，以及获得 这些值的集合。接下来在318，我们核对以查看p.i的数量是否小于3。如 果p.i的数量不小于3，那么在320我们从集合移除最大和最小的p.i，并 然后返回316。如果p.i的数量小于3，那么在322，我们核对以查看我们 是否具有剩余的1或2个值。如果我们具有1个剩余值，那么在324，我 们让p.split成为最后的剩余值，并然后进行328。如果我们具有2个剩余 值，那么在326，我们让p.split成为最后两个剩余值的平均值，并然后进 行328。在328，我们定义“分离器(splitter)”，其由较早(在312的vsplit， 和在324或326的p.split)计算的(vsplit，p.split)组成。在330，对于在 当前集合里的每个内容项，如果p.i>p.split，那么指明其为“上部”，否则 指明其为“下部”。接下来在332，我们建立由来自之前步骤的分离器组成 的内部节点，并定义到待被建立的“下部”和“上部”节点的链接。接下 来取决于作为“下部”或“上部”分类，我们分别行进到334或336。在 334，对于“下部”集合，我们称其为当前集合，我们让n作为项的数量， 并且通过行进到306我们再次调用这个整个程序。在336，对于“上部” 集合，我们称其为当前集合，我们让n作为项的数量，并且通过行进到306 我们再次调用这个整个程序。因此图3一般举例说明了显示大量建立相似 性索引的方法的本发明的一种实施方式，其中输入是内容项的集合且输出 是有项在叶节点的二进制树。

图4一般在400举例说明了显示相似性索引树的实施例的本发明的一 种实施方式。每个内部节点(例如402、404、410)持有一个分离器，其 由“平均”向量和标量分离值(split value)组成。分离器的工作是捕获任 何输入向量，并决定那个向量是否被引导到“下部的”或“上部的”子树。 每个叶节点(例如406、408、412、414)持有内容项向量。

查询

相似性索引树能被用来执行如下的查询：

1、我们给定查询向量q、相似性索引树和相似性阈值s。

2、设置当前节点作为索引树的根。

3、如果根节点是叶节点，那么计算在q和叶节点里每个项之间的相 似性。返回具有大于s的相似性的项。完成。

4、否则，如果根节点是内部节点，则分离器由向量“vsplit”和标量 值“p.split”组成。计算表达式，

r＝<q-vsplit，vsplit>

5、计算delta＝(r-p.split)。

6、如果delta大于零，那么设置当前节点为上部子节点。否则，设置 当前节点为下部子节点。

7、行进到步骤3。

图5一般在500举例说明了显示查询的本发明的一种实施方式。在 502，我们给定已经建立相似性索引的数据集，给定查询q并给定期望的 相似性阈值s。在504，我们将当前节点设置到相似性索引的根。在506， 我们确定当前节点是叶节点还是内部节点。如果当前节点是叶节点，那么 在508我们计算在q和在叶节点里的每个项之间的相似性，然后我们进行 到510，在510我们返回满足相似阈值准则s的项，并然后进行到512，在 512完成。如果当前节点是内部节点，那么在514我们从内部节点获得分 离器(vsplit，p.split)并计算r＝<q-vsplit，vsplit>。接下来在516，我们确定 是否r-p.split>0。如果r-p.split大于零，那么在518我们将当前节点设 置为“上部”子节点，并进行到506。如果r-p.split不大于零，那么在520， 我们将当前节点设置为“下部”子节点并进行到506。因此图5一般举例 说明了显示查询的方法的本发明的一种实施方式，输入是查询q、相似索 引、阈值s，以及输出是使查询至少与阈值s匹配的项。

自连接

执行自连接利用了建立相似性索引的重复调用。例如，见图6中的流 程图。

程序

假设数据集D由项x.i组成，其中i＝0，.，n-1。我们定义自连接程序， 其输出s-集群的分层级分组。

给定s在(0，1)中的值，在D中的每一项x属于具有下面属性的集群 C(x)：

a、对于在C(x)中的所有y，相似性(x，y)>s。

b、至少有一个C(x)的成员，称其为锚(anchor)a，使得最接近a的 成员数量大于或等于最靠近C(x)的任何其它成员的成员数量。(如何对此 说明以包含C(x)是有限的、无穷的但是可数的、和无穷但是不可数的情 形？)。

c、D中的每个x属于某个集群C(x)。

d、在D中x的集群C(x)的集是有限的互为唯一的。

我们注意到对于s的给定值，可有不止一种方式定义满足上述属性的 集群。换而言之，用自连接技术输出的集群的集可能不是唯一的，并可有 对同样满足期望的条件来对项进行分组的其它方式。

图6一般在600举例说明了显示自连接的本发明的一种实施方式。如 上指出的，执行自连接利用了建立相似性索引的重复调用。在602我们指 定最大集群大小为G，以及最小集群相似性为s。在604我们输入n个内 容项。在606，我们大量建立相似性索引，这产生具有叶节点的树，且每 个叶节点有G个或更少的项。在608，对于每个叶节点，我们计算各项间 的两两(pairwise)(也称为pair-wise)相似性。在610，我们核对以查看 是否至少有一对项的相似性超过s。如果没有至少一对项的相似性超过s， 那么在612我们定义“一次性(oneoff)”(也称为one-off)集群，并将项 放在其中，并然后进行到622。如果有相似性超过s的至少一对项，那么 在614我们计算最高的两两相似性，并指明一个项作为集群的“锚”。接 下来在616，我们定义“好”集群。在618，对于在当前节点的每一项， 如果其与锚的相似性超过s，那么将其放在好集群里，否则，如果其与锚 的相似性没超过s，那么在620，如果有剩余项，指明剩余项作为“残留 (residual)”并分别收集它们。在622，我们确定我们是否已处理所有的叶 节点。如果我们没有处理所有的叶节点，那么我们在608重新开始。如果 我们已经处理所有的叶节点，那么在624我们核对以查看在这个点我们是 否有任何收集的残留。如果在这个点我们没有任何收集的残留，那么我们 进行到626，完成。如果在这个点我们具有任何收集的残留，那么我们进 行到628，在628我们聚集较早收集的残留，且我们然后进行到606。于 是图6一般举例说明了显示自连接方法的本发明的一种实施方式，其中输 入是内容项的集合，且输出是项的“好”和“一次性”集群。

图7一般在700举例说明了显示自连接树的实施例的本发明的一种实 施方式。显示各种各样的等级，等级0(702)、等级1(704)和等级2(706)。 显示了顶端的集(708、720和728)。在顶端708和“好”群712之间显 示指向“锚”710的指针。同样在714和716显示“好”群。在718是没 有锚的“一次性”群。同样在722和724显示“好”群。726显示“一次 性”群，其中没有一项与该群中的另一项的相似性满足相似性阈值s。

常规连接

给定两个一致的数据集D.1和D.2以及相似性阈值s^*，这个程序识别 集合s^*-连接集群。每个s^*-连接集群显示关于两个数据集的重要信息，因 为它识别在一个数据集中的哪一项具有其他数据集中的相似的对应部分。 而且，由于我们可以设置s^*参数，因此我们能够确定，匹配条件(match) 是否滤除了几乎全部项，而只留下了那些非常接近匹配条件的项(s^*非常 接近1)，或者我们是否乐于找出非常宽泛的匹配条件但是仍然筛选出完全 不匹配的项(例如，使用s^*的70％)。

方法

如我们早前所提到的，大规模数据集的一个主要挑战是尽可能避免 n^Λ2两两相似性计算阶段。例如，在自连接程序期间，仅当我们到每个包 含G个项的叶节点时，我们采取两两相似性计算。因为我们能控制叶节点 G的大小，所以我们在G^Λ2/2的两两计算(pairwise computation)上设置 边界(bound)。

在常规连接背后的想法是尽可能地平衡自连接程序产生的局部层级。 当在数据集内有高度的内部相似性时，会有许多“好”群。参考图7。每 个好群从它的中间选定“锚”项，以表示该群在群层级之上。由于每个锚 代表G个其他群成员，因为外部项相对于锚的相异性(Dissimilarity)等于 知道相同的项将也与群的每个成员相异，这导致在计算成本中巨大的节 约。

然而，使用此代理表示方案(proxy representation scheme)用于相似 性是有代价的，并且这种表示方案不得不接收这一事实：锚仅是每个群成 员的不完美的代替物。为了对此进行补偿，我们必须加强(tighten)好群 层级的等级之间的相似性阈值，以维持我们对总体s*相似性准则的遵守。 换言之，因为在自连接分组层级里的每个等级失去一些相似性精确度，所 以我们调整自连接中所使用的阈值来补偿。我们通过得到用于相似性的 “链规则(chain rule)”来计算在每个等级我们能够允许多少相似性预算， 列举如下。

假设我们在两个项x和z之间有一距离，且我们想引入中间项y：

‖x-z‖^Λ2

＝‖(x-y)-(y-z)‖^Λ2

<＝‖(x-y)‖^Λ2+‖(y-z)‖^Λ2(三角不等式)

如果我们假设x、y和z被规范化以具有单位标准，或者<x，x>＝<y，y> ＝<z，z>＝1，我们能够使用论据：相似性(x，y)＝<x，y>/sqrt(<x，x>*<y，y>)＝ <x，y>。

使用定义‖x-y‖^Λ2＝<x-y，x-y>，并使用内积的属性展开第二项 (second term)，我们获得相似性的链规则：

1-相似性(x，z)<＝(1-相似性(x，y))+(1-相似性(y，z))    (*)

顺便说一句，这能够根据相异性用更值得储存的术语表示。

相异性(x，z)<＝相异性(x，y)+相异性(y，z)，

其中相异性(x，y)＝1-相似性(x，y).

改写上述的等式(*)，我们得到等价链规则：

相似性(x，z)<＝相似性(x，y)+相似性(y，z)-1.

这能扩展到两个中间项：

相似性(x，z)<＝相似性(x，y1)

+相似性(y1，y2)

+相似性(y2，z)

-2。

这能扩展到多个中间项，y.i，其中i＝1，k。

相似性(x，z)<＝相似性(x，y.1)

+sum(i＝1，k-1；相似性(y.i，y.i+1))

+相似性(y.k，z)

-k。

这个表达式能解释为意味着每次我们在x和z之间插入附加的中间项， 在这两个端点间的相似性的下边界被在每个附加的中间项之间的相似性 降低。

我们将使用这个链规则确定我们需要在每个自连接上使用什么样的 相似性阈值，使得当我们试图推断从在树里的叶节点向上传播到锚和一次 性节点的相似性时，我们能够控制因树中的多个等级而给解决方案引入的 精确度损失。在此情况下，我们将总体相似性预算均匀地分配在各等级间。

为了给出在操作中的链规则的实施例，下面的表格显示出，如果需要 要求当两个叶项(leafitems)通过某个锚项(anchor item)而彼此相关时， 在最坏的情形下，我们能够断言两个项满足85％的相似性阈值，则必要的 “内部”相似性阈值是必需的。如表格指示的，随着树变得更高，为了维 持对总体相似性的保障，我们必须在等级间强制更大程度的相似性。

 

在自连接树中的等级获得总体85％相似性 所需的内部相似性  185.00％295.00％397.00％497.86％598.33％698.64％

解决方案准则

常规连接程序可达到的明确的条件是，每个s^*-连接集群具有集群的每 个成员与另一数据集的某个成员至少在s^*相似性阈值内的这个属性。而 且，如果连接集群的任何成员是锚，那么可通过所述锚直接或间接可达到 的所述成员的数据集中的所有成员与另一数据集的某个成员至少在s^*相 似性阈值内。另外，如果能够从连接集群建立一个连接对，对的每个成员 是锚，那么每个锚的两个整体分组子树是满足s^*阈值的备选。相反的，如 果有来自D.1的x.1和来自D.2的x.2，且相似性(x.1，x.2)>s^*，那么来自 常规连接的解决方案包含s^*-连接集群，在该s^*-连接集群中，或者a)x.1 和x.2都是成员，或者b)有是s^*-连接集群的成员的锚，其中通过那个锚， x.1和/或x.2可直接或间接获得。

程序

1、给定相似性阈值s^*。

2、假设数据集1和数据集2的大小分别为N1和N2。

3、挑选分组大小G1>0。(我们希望G足够大，使得分层级的自连接 树的预期的大小可管理，但是同时，G足够小，使得G1^Λ2/2两两相似性计 算保持有界。我们计算最优分组大小，其最小化计算两两相似性的全部计 算开销，加上计算建立自连接二进制树所需的上部/下部分离的开销。)根 据高度h1＝ceiling(log2(N1/G1))，分组大小G1的选择确定二进制树的高度。

4、按以下方式为数据集1挑选相似性阈值s1。使用自连接树h1的预 期高度，计算“内部”相似性s1为

s1＝1-(1-s^*)/(2*h1-1)

这是当在数据集1上建立自连接树时我们所需要使用的相似性，以确 保考虑了树的完整高度，以使每个锚对它的群的相似性足够接近，以保存 的所有备选连接对。

5、对数据集2实施相同操作。即，挑选分组大小G2、高度h2和内部 相似性阈值s2。

6、使用较早确定的分组大小和内部相似性阈值，为每个数据集计算 自连接。

7、识别每个数据集的自连接树的顶端元素，其由根集群的锚加上所 有一次性群的成员组成。

8、将来自数据集1和数据集2的自连接树的顶端元素结合到单个集 合里，并使用s^*的相似性阈值和对应于在这个集合里的项的数量的最优分 组大小来计算这个集合上的自连接。

9、检查由自连接产生的集群，并对s^*的相似性阈值挑选所有的连接 集群。将每个挑选出的连接集群加到结果集。

10、按以下方式对连接的结果进行解释。根据对s^*-连接集群的定义， 每个这样的集群包含来自数据集1和数据集2的至少一个成员。集群的成 员满足s^*相似性阈值条件。此外，集群的一些成员是在上述步骤6中在其 自身的数据集上执行的自连接中的锚。在那种情形，我们说，通过该锚直 接或间接可达到的它的数据集的成员是连接集的一部分。特别地，如果连 接集群包含分别来自数据集1和数据集2的锚a1和锚a2，那么从锚a1可 达到的数据集1的成员显示为被连接到从锚a2可达到的数据集2的成员。

参考图8中的流程图。

图8一般在800举例说明了显示常规连接的本发明的一种实施方式。 在802，给定有阈值s^*的数据集1和数据集2。在804，我们能够挑选预先 确定的固定的“分组”大小G.i，或任选地，为每个数据集确定将建立相似 性索引的总体计算时间减到虽小的“分组”大小G.i。接下来在806，给定 数据集1和数据集2的大小，我们计算树的预期高度h.i＝ ceiling(log2(N.i/G.i))。在808，对于数据集1和数据集2，我们使用相似性 阈值s.i＝1-[(1-s^*)/(2*h.i-1)]建立自连接树。接下来在810，每个自连接产 生好群和一次性群的树，且我们指明“顶端”集为根好群(root good group) 的锚连同一次性群的成员。在812，我们从之前步骤(810)中识别的“顶 端”集形成数据集。接下来在814，使用s^*作为相似性阈值，我们在之前 步骤(812)中形成的数据集上执行自连接。现在，在816，根据在之前步 骤(814)中的自连接，我们输出具有来自数据集1的至少一个成员和来 自数据集2的至少一个成员的“好”群，并称这些为s^*-连接集群。我们接 下来进行到818，完成。因此图8一般举例说明了显示常规连接的方法的 本发明的一种实施方式，其中输入是内容项的集合，以及输出是项的“s- 连接”集群。

正确性论据

常规连接算法的正确性要求：对于在数据集1里的x.1和在数据集2 里的x.2，当且仅当相似性(x.1，x.2)>s.0时，x.1和x.2或者a)在结果集里 识别为成对的，或者b)x.1和x.2的一个或两者由在它们的自连接树内的 锚代表，以及它们的表示直接出现或间接连接在结果集里。

根据结果集的结构，我们知道为结果集挑选的任何对满足相似性(x.1， x.2)>s.0。这样建立“仅当”说明的部分a)。

为了建立“仅当”说明的部分b)，我们注意到，我们将D.1和D.2的 自连接树构造成，从顶端锚或一次性项到树中的在其之下的任何项的总体 相似性的下界是s^*。换言之，我们考虑到了任何项到它的锚的距离，并合 计基于树的高度的总体相异性，以确保在树内的项的任何连接对至少是相 似性s^*。由于所说明的在每个自连接树内的总体相似性，我们只需要考虑 在s^*-连接集群里任何其它成员的附加的相似性，其由锚到另外的锚或直接 到项而产生。这个附加的距离可导致在最后的解决方案里的一些可能成对 的消除。

对于论据的“当”说明，假设相反的存在x.1和x.2，其中x.1和x.2 分别来自数据集1和2，其中，相似性(x.1，x.2)>s.0，而且在结果集里未出 现x.1和x.2。换言之，存在来自数据集的一对匹配项，而我们未能通过在 结果集里它们的直接出现，也未能通过在结果集里的代表性锚来识别所述 匹配。我们希望建立矛盾(contradiction)。

这意味着我们具有如下情况：在连接算法期间的任何时间，x.1和x.2 中的任一个或两者在结果集里没有出现，而且，它们的自连接树中向上的 锚中的任何一个也没有出现在结果集。我们将通过归纳继续。

对于基本情形，假设x.1是顶端的锚，或它出现在一个一次性群中。 假设x.2同样如此。连接算法的第一步将两个数据集的所有顶端的锚和一 次性成员结合到单个集合里，并使用s^*阈值在其上执行自连接。为进一步 处理，识别包含来自数据集1和数据集2的每个的至少一个成员的任何集 群；我们将其称为s^*-连接集群。但是这导致矛盾，因为我们具有的情形是 x.1和x.2在顶端集里，且它们满足s^*条件，但是在所述情形中，自连接程 序将它们放入结果集合里。

对于归纳的情形，假设x.1既不是顶端锚，也不在一次性群里。这意 味着它在包含锚的群里。并反之，每个锚或者在一次性群里，或者它也在 有锚的群里。通过自连接树的构造，我们知道x.1与顶端锚或与一次性群 成员的相似性至少是s^*。

相同的推理适用于x.2。由此，我们知道x.1和x.2在顶端集里具有满 足s^*条件的表示。但是在程序的过程中，我们从D.1和D.2构成顶端项的 s^*-连接集群。因此，对于我们来说，不直接构成具有x.1和x.2的表示的 群的唯一的方法是，假设所述表示被分离到未由公共锚连接的不同的群 中。但是这与自连接的属性发生矛盾。

由此，我们已经建立了论据的“当”和“仅当”说明。

讨论

我们注意到，在两个数据集间执行连接的工作发生在两部分。首先， 我们在每个数据集上单独地进行自连接。第二，我们在每个数据集的顶端 元素上进行自连接。实际上，我们看到，由于锚作为各自的群成员的代理 而出现，因此，当数据集在它自身内具有相当程度的相似性时，顶端集可 以大大地小于整体数据集。当两个数据集具有高度的内部相似性时，那么 顶端成员的数量将相对小，且在结合的顶端集上的自连接将相对迅速。

另一方面，当数据集在其自身内包含非常小的相似性，那么自连接产 生了大量一次性群，而锚很少。在这种情形，顶端成员将几乎像全部数据 集一样大。如果第二数据集同样如此，那么我们看到，在顶端集上的自连 接将构成大量工作。

我们指出，用于连接两个数据集的这个程序能扩展成连接多个数据 集。首先，在每个数据集上分别进行自连接。第二，将每个自连接的顶端 成员收集到组合的顶端成员集里，并在所述集上执行自连接。

实际上，当增加或移除项时，为数据集递增地更新相似性索引是有意 义的，因为自连接是与其它数据集连接的前提，并且反之，相似性索引是 自连接的必要组成。参考文献R.Nakano的日期为2005年2月的美国专利 申请第11/361166号“Method and apparatus for efficient indexed storage for unstructured content”中描述的程序可适用于这种情况。

“群”和“集群”

本领域技术人员将认识到，通常用几个术语描述相同的事物。如在这 个描述使用的，使用术语“群”和“集群”或相似的短语指相同的事物。 例如，在上述定义部分中，我们这样定义s-集群：(s-集群)我们说当对于 在集合中的任何项x，对于在集合中的项具有大于或等于s的相似性时， 一致的项集合构成s-集群。词“集群”指“项”的集合，在别处指“内容 项”。通过说它们在“集群”里，强调了在集群里的所有元素具有s或更大 的两两相似性。例如，如果相似性阈值s是99％，我们具有10个图像 p.1，....，p.10，并在被适当转变为它们各自的内积空间向量后，对于在 {1，....，10)中的所有i和j，所述相似性(p.i，p.j)>＝0.99。

另一例子在自连接部分的讨论中，我们规定：给定在(0，1)中的s 的值，在D中的每个项x属于具有如下属性的集群C(x)：....这里词“集 群”指相同的事物。所以继续上述的例子，存在值s＝0.99，其中，图像集 合里的每个图像x具有的属性为，图像的两两相似性满足或超过99％阈值。

另一例子是关于群的讨论，例如在图8中公布了“每个自连接产生好 群和一次性群的树”。这里，自连接操作被描述为产生好群和一次性群。 这与说好群是满足相似性阈值s的s-集群是相同的。一次性群是未能满足 s阈值的内容项的集。例如，如果我们已经设置s为99％，那么好群是0.99- 集群。但是一次性群是准则未能满足0.99-集群条件的集合。如果保持相似 性阈值条件，则我们能够使用术语“好集群”、“好集群”和“s-集群”来 表示相同的事物“。否则，如果未保持相似性条件，则我们能够使用术语 “一次性群”和“一次性集群”或相似短语来表示相同的事物。

从这里我们看到，“群”和“集群”(和相似短语)指具有一些已知两 两相似性值的内容项的集。因为我们知道这个，我们能够断言是否获得了 给定的相似性阈值s。特别地，如果内容项的所有对超过s相似性，我们 具有s-集群、好群或好集群。否则，我们不具有s-集群，但是改为具有一 次性群或一次性集群。

附带说明，注意，如果我们具有n个内容项且我们不知道它们的所有 n*(n-1)/2个两两相似性值，那么我们不能判定它们是否构成好群、一次性 群、好集群、一次性集群或s-集群。在简并的情形下，任何n个项构成0- 集群。换言之，内容项的任何对具有相似性>＝0，这成立，但是无助于我 们。

要说明或证明的(Quod erat demonstrandum)

我们已经显示对于大规模高维数据集如何执行基于相似性查询、自连 接和常规连接。

因此描述了用于大规模高维数据集的快速的基于相似性的查询、自连 接和连接的方法和设备。

返回参考图1，图1举例了网络环境100，其中可使用描述的技术。 网络环境100具有连接S个服务器104-1到104-S以及C个客户端108-1 到108-C的网络102。如所示，几个计算机系统以S个服务器104-1到104-S 以及C个客户端108-1到108-C的形式通过网络102彼此连接，网络102 可能是例如基于企业的网络。注意，可选择地，网络102可以是或包括一 个或更多下列项：因特网、局域网(LAN)、广域网(WAN)、卫星链路、 光纤网络、电缆网或它们的组合和/或其它。服务器可代表，例如仅仅磁盘 存储系统或存储器以及计算资源。同样地，客户端可具有计算、储存和浏 览能力。这里描述的方法和设备可被用于实质上任何类型的通讯装置或计 算设备，而不论是本地的还是远程的，例如LAN、WAN、系统总线、微 处理器、主机、服务器等等。

返回参考图2，图2以框图形式举例说明了计算机系统200，其是显 示在图1中的任何客户端和/或服务器的代表。该框图是高级概念表示形 式，并可以用种种方式及通过不同结构实现。总线系统202与中央处理器 (CPU)204、只读存储器(ROM)206、随机存取存储器(RAM)208、 储存器210、显示器220、音频222、键盘224、指示器(pointer)226、不同 种类的输入/输出(I/O)设备228和通信系统(communications)230互相连 接。总线系统202可以是例如作为系统总线的一个或更多这样的总线外设 部件互连(PCI)、加速图形端口(AGP)、小型计算机系统接口(SCSI)、 电气和电子工程师协会(IEEE)标准号1394(FireWire)、通用串行总线 (USB)等等。CPU204可以是单个、多重或甚至是分布式计算资源。储 存器210可以是压缩磁盘(CD)、数字化视频光盘(DVD)、硬盘(HD)、 光盘、磁带、快闪记忆体、记忆棒、录影机等等。显示器220可以是例如 电子射线管(CRT)、液晶显示器(LCD)、投影系统、电视机(TV)等等。 注意，依赖于计算机系统的实际实现，计算机系统可包括框图中的组件的 一些、全部、更多或重新排列。例如，瘦客户端(thin client)可由缺少例 如传统键盘的无线手持设备组成。因此，在图2的系统上的许多变化是可 能的。

为了讨论和理解本发明，应理解，本领域技术人员使用各种各样的术 语描述技术和方法。而且，在描述中，为了解释的目的，为了提供本发明 的通透的理解而提出许多明确的细节。然而对于本领域普通技术人员将是 明显的是，可实践本发明而无需这些明确的细节。在一些实例里，为了避 免使本发明模糊不清，众所周知的结构和设备以框图形式显示，而不是详 细地显示。已足够详细地描述了这些实施方式，以使本领域普通技术人员 能够实践本发明，并应理解，可利用其它的实施方式，且可进行逻辑的、 机械的、电的和其它改变而不背离本发明的范围。

根据算法和对例如在计算机存储器内的数据位的操作的象征性表示， 介绍了描述的一些部分。这些算法描述和表示是数据处理领域的普通技术 人员使用的方式，以便最有效地将其工作的实质传达给本领域的其他普通 技术人员。算法在这里通常被设想为导致期望结果的自一致的动作序列。 这些是要求物理量的物理处理的动作。虽然不一定，但通常这些量采取能 够被储存、转移、结合、比较和以其他方式处理的电或磁信号的形式。主 要是由于公共使用的原因，有时将这些信号称为位、值、单元、符号、字 符、术语、数字或等，已证明是方便的。

然而，应该牢记，所有这些以及相似的术语与适当的物理量相关联， 且仅仅是适用于这些量的方便的标签。除非特别声明，否则从讨论中明显 的，应认识到，贯穿描述，利用了例如“处理”或“计算”(computing) 或“计算”(calculating)或“确定”或“显示”或之类的术语的讨论，可 以指计算机系统或类似电子计算设备的动作和处理，这些动作和处理将在 计算机系统的寄存器和存储器内的表示为物理(电)量的数据，操纵并转 换为在计算机系统存储器或寄存器或其它这样的信息存储器、传输设备或 显示设备内的类似地表示为物理量的其它数据。

用于执行这里的操作的设备能实现本发明。这样的设备可被特别地构 建以实现所需目的，或者它可包括通用计算机，其被储存在计算机里的计 算机程序有选择地激活或重新配置。这样的一个计算机程序可存储在计算 机可读存储介质里，例如但不限于，包括软盘、硬盘、光盘、压缩磁盘- 只读存储器(CD-ROM)、以及磁光盘、只读存储器(ROM)、随机存取存 储器(RAM)、电可编程只读存储器(EPROM)、电可擦除可编程只读存 储器(EEPROM)、闪存、磁或光卡等等的任何类型的盘，或适合于电子 指令的本地计算机储存或远程计算机储存的任何类型的介质。

这里提出的算法和显示不是固有地涉及任何特殊的计算机或其它设 备。依照这里教授的，可通过程序使用各种各样的通用系统，或者可证明 构建更专门的设备来执行要求的方法是方便的。例如，通过对通用处理器 编程，或通过硬件和软件的任何组合，可用硬连线电路实现根据本发明的 任何方法。本领域的普通技术人员将立即认识到，本发明能用不同于所描 述的计算机系统结构来实践，包括手持设备、多处理器系统、基于微处理 器或可编程的消费类电子产品、数字信号处理(DSP)设备、机顶盒、网 络个人计算机、小型计算机、大型计算机及类似处理。本发明还可在分布 式计算环境中实践，其中，任务通过由通信网络链接的远程处理设备执行。

本发明的方法可使用计算机软件实现。如果是用符合公认标准的程序 设计语言编写，被设计成实现该方法的指令序列能够被编译，用于在多种 硬件平台上执行，并用于通过接口连接到许多操作系统。另外，本发明不 参考任何特殊的程序设计语言来描述。将理解，可使用多种程序设计语言 实现如这里描述的本发明教授的内容。此外，在本领域中以一种形式或其 它形式(例如程序、过程、应用程序、驱动程序、....)提及软件作为采取 行动或造成结果是很普遍的。这样的表达仅仅是一种简要表达方式，用来 指示计算机的软件执行使得计算机的处理器实现动作或产生结果。

应理解，本领域技术人员使用各种各样的术语和技术描述通信、协议、 应用、执行、机制等等。根据算法或算术表达式，一种这样的技术是对技 术实现的描述。即，当技术可以例如实现为在计算机上执行代码时，所述 技术的表达可更适宜地且更简便地作为公式、算法或算术表达式传送和通 信。因此本领域的普通技术人员将表示A+B＝C的模块看作是一加法函数， 该模块的硬件和/或软件实现接收两个输入(A和B)并产生总和输出(C)。 因此，如描述的公式、算法或算术表达式的使用应理解为至少具有硬件和 /或软件的物理实施方式(例如一个计算机系统，其中本发明的技术被实践， 并被实现为实施方式)。

机器可读介质被理解为包括用于以机器(例如，计算机)可读形式储 存或传播信息的任何机制。例如，机器可读介质包括只读存储器(ROM)； 随机存取存储器(RAM)；磁盘存储介质；光存储介质；闪存设备；电、 光、声或其它形式的传播信号(例如载波、红外信号、数字信号等等)； 等等。

正如在本说明中使用的，“一种实施方式”或“一个实施方式”或相 似的短语意味着描述的特征包括在本发明的至少一种实施方式里。本说明 里提及“一种实施方式”不一定指相同的实施方式；然而，这样的实施方 式也不互相排斥。“一种实施方式”也不意味着仅是本发明的单个实施方 式。例如，在“一种实施方式”中描述的特征、结构、动作等等可也包括 在另外的实施方式里。因此，本发明可包括这里描述的实施方式的多种组 合和/或结合。

因此，描述了用于大规模高维数据集的快速的基于相似性的查询、自 连接和连接的方法和设备。

附录1

(内积空间)给定在向量空间中的任意两项x、y，有满足下列属性的内 积：

a.<x，x>>＝0

b.<x，x>＝0 iffx＝0.

c.<x，y>＝<y，x>

d.<a*x，y>＝a*<x，y>

e.<x+y，z>＝<x，z>+<y，z>

在两个非零元素x和y之间的相似性可表示为，

相似性(x，y)＝<x，y>/sqrt(<x，x>*<y，y>).

我们注意到内部空间是有如下度量的度量空间。

‖x‖＝sqrt(<x，x>).

三角不等式为，

‖x-y‖^Λ2<＝‖x‖^Λ2+‖y‖^Λ2