2024年6月12日发(作者：)
(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(21)申请号 CN2.8
(22)申请日 2004.11.09
(71)申请人 奥弗图尔服务公司
地址 美国加利福尼亚州
(72)发明人 克努特·玛格纳·里斯维克 耶格威·阿舍米 托尔·埃格 哈瓦德·派特森
(74)专利代理机构 北京东方亿思知识产权代理有限责任公司
代理人 王怡
(51)
G06F17/30
权利要求说明书 说明书 幅图
(10)申请公布号 CN 101189602 A
(43)申请公布日 2008.05.28
(54)发明名称
具有分层存储的索引的搜索引擎
(57)摘要
一种搜索引擎，其包括搜索WWW
并且将在WWW上找到的网页存储在数据
库(100)中的采集器(102)。索引器(105)将数
据库中的网页编入索引以产生主索引。文
档映射部件(114)基于网页的等级将数据库
中的网页映射到多个分层中。等级可以基
于网页中具有较高价值的上下文。处理器
基于上述映射从主索引中产生多个子索
引。子索引被存储在搜索节点组(160)中。
该组是在逻辑上被排列成多个行和列的搜
索节点矩阵。同一列中的搜索节点包括相
同的子索引。同一行中的搜索节点包括不
同的子索引。从用户(112)那接收到的搜索
查询被发送到调度器(110)，调度器又将查
询转发给第一层的搜索节点。公开了滑落
算法，其指示调度器何时应当将搜索查询
转发给搜索节点的其它层。
法律状态
法律状态公告日
法律状态信息
未缴年费专利权终止IPC(主分
类):G06F17/30专利
2022-11-01
号:ZL2申请
日:20041109授权公告
日:20100127
法律状态
专利权的终止
权 利 要 求 说 明 书
1.一种用于为数据库中的数据项建立索引的方法，所述方法包括：
从数据库中获取数据项；
产生所述数据项的主索引；
基于所述数据项各自的等级将所述数据项映射到至少第一和第二层上；
基于所述映射从所述主索引产生至少第一和第二子索引；以及
将所述至少第一和第二子索引存储在不同的搜索节点中。
2.根据权利要求1所述的方法，其中所述数据库是可以通过万维网得到的网页和文
档的集合。
3.根据权利要求1所述的方法，其中所述映射基于所述数据项的静态相关分数。
4.根据权利要求1所述的方法，还包括：
在所述数据库上执行用于大量查询的搜索查询日志；以及
接收所述搜索查询日志的结果；
其中所述第一子索引基于所述查询日志的结果。
5.根据权利要求3所述的方法，还包括：
在所述数据库上执行用于大量查询的搜索查询日志；以及
接收所述搜索查询日志的结果；
其中所述第一子索引基于所述查询日志的结果。
6.根据权利要求1所述的方法，其中所述映射基于所述数据项的价值上下文。
7.根据权利要求1所述的方法，其中所述数据项为web网页并且所述映射基于所述
web网页的相关分数。
8.一种用于搜索数据库的方法，所述方法包括：
从数据库中获取数据项；
产生所述数据项的主索引；
基于所述数据项各自的等级将数据项映射到至少第一和第二层上；
基于所述映射从所述主索引产生至少第一和第二子索引；
将所述至少第一和第二子索引存储在不同的搜索节点中；
接收搜索查询；以及
搜索所述第一层以寻找与所述搜索查询有关的结果数据项。
9.根据权利要求8所述的方法，还包括：
当所述第一层不能产生阈值数目的结果数据项时，搜索所述第二层以寻找与所述搜
索查询有关的结果数据项。
10.根据权利要求8所述的方法，其中当所述第一层不能产生阈值数目的结果数据
项时，搜索所述第二层。
11.一种用于为数据库建立索引的系统，所述系统包括：
采集器，其搜集所述数据库以寻找数据项；
索引器，其接收所述数据项并产生主索引；
文档映射部件，其基于所述数据项各自的等级将所述数据项映射到至少第一和第二
层上；
处理器，其基于所述映射从所述主索引产生至少第一和第二子索引；
第一搜索节点，其存储所述第一子索引；以及
第二搜索节点，其存储所述第二子索引。
12.一种用于实现对数据库的搜索的搜索节点组，包括：
逻辑上被排列在多个行和多个列中的多个搜索节点；
所述多个列中任一列中的所有搜索节点实质上包括相同的信息；
所述多个行中任一行中的所有搜索节点包括不同的信息；
所述多个行中的搜索节点逻辑上被分为至少第一和第二层；
所述第一层中的搜索节点包括针对所述数据库的第一部分的索引；以及
所述第二层中的搜索节点包括针对所述数据库的第二部分的索引；其中
所述第一和第二层中的数据基于所述数据库的第一和第二部分中的信息各自的等级。
13.一种搜索引擎，包括：
采集器，其搜集数据库以寻找数据项；
索引器，其接收所述数据项并产生主索引；
文档映射部件，其基于所述数据项各自的等级将所述数据项映射到至少第一和第二
层上；
处理器，其基于所述映射从所述主索引产生至少第一和第二子索引；
第一搜索节点，其存储所述第一子索引；
第二搜索节点，其存储所述第二子索引；以及
调度器，其接收查询并且将所述查询转发给所述第一搜索节点。
14.根据权利要求13所述的搜索引擎，其中所述第一子索引被存储在逻辑上排列在
第一多个列中的第一多个搜索节点中；所述第二子索引被存储在逻辑上排列在第二
多个列中的第二多个搜索节点中，以使得所述第一和第二子索引被进而在逻辑上排
列在各自的多个逻辑行中。
15.根据权利要求13所述的搜索引擎，其中当所述第一层没有产生阈值数目的结果
数据项时，所述调度器将所述查询发送给所述第二层。
16.根据权利要求13所述的搜索引擎，其中当所述第一层未产生阈值数目的结果数
据项时，所述调度器将所述查询发送给所述第二层。
说 明 书
技术领域
本发明涉及搜索引擎，更具体地涉及将搜集到(crawled)的文档映射到多个分层中，
然后按照分级方式搜索那些分层的搜索引擎。
背景技术
万维网(“WWW”)是包括可以经互联网访问的数十亿个网页的分布式数据库。搜索
和索引这些网页以产生响应于用户查询的有用结果一直都是个难题。通常用于搜索
WWW的设备是搜索引擎。维护有效的搜索引擎是很困难的，因为WWW是在不
断地变化的，每天有数百万个网页被添加，而且现有网页也在连续不断地变化。此
外，执行搜索的成本通常直接对应于被搜索的索引的大小。为了处理WWW中的
大量数据，大多数搜索引擎都是分布式的并且使用复制和分割技术(下面会进行讨
论)以缩减文档的数量。
图1中示出了典型的现有技术的搜索引擎50。利用采集器102访问来自互联网或
其它源100的网页。采集器102集合来自源100的文档以确保这些文档可被搜索。
有很多用于采集器的算法，并且在大多数情况下，这些采集器顺着已知的超文本文
档中的链接来获得其它文档。采集器120所获取的网页被存储在数据库108中。之
后，索引器104为这些文档建立索引。索引器104为数据库108中的文档建立可搜
索的索引。用于建立索引的典型的现有技术方法包括倒排文件、向量空间、后缀结
构及这些方法的混合。例如，每个web网页可以被分解成网页上的词和每个词各
自的位置。然后利用这些词和它们各自的位置来为网页建立索引。然后将整个数据
库108的主索引分解成多个子索引(下面将讨论)并且将每个子索引发送给搜索节点
组106中的搜索节点。
在使用中，用户112将搜索查询输入到调度器110。调度器110应允组106中的一
列搜索节点执行查询并且将查询转发给那些被选择的搜索节点。被应允的一列搜索
节点要确保每个分区都被搜索一遍。搜索节点组106中的搜索节点搜索由索引器
104所产生的主索引中的各个部分并且将分类后的搜索结果与文档标识符和分数一
起返回给调度器110。调度器110合并接收到的结果以产生显示给用户112的按相
关分数分类的最终的列表。相关分数是查询本身和所产生的文档类型的函数。用于
相关的因素包括：诸如链接基数(cardinality)和网页性质之类的文档的静态相关分数；
诸如标题、元数据和文档头部之类的文档的高级部分；诸如外部引用和引用“级别”
之类的文档的权威性(authority)；以及诸如文档中的查询词频、全局性词频以及文
档内词的相对距离之类的文档统计信息。
现在参考图2，其示出了搜索节点组106。为了说明，用矩阵的形式示出了组106，
其被集合在列122a、122b等和行124a、124b等中。在每个搜索节点列122中，为
每个搜索节点复制同一套索引。例如，列122a行124a中的搜索节点与列122a行
124b中的搜索节点包括同一套索引子集。在每个搜索节点行124中，使用不同的
索引子集。索引被等分以拆分用于搜索的时间量。
例如，列122a行124a中的搜索节点包括与列122b行124a中的搜索节点不同的索
引子集。在每个搜索节点中，“I”表示用于整个数据库108的索引，“S”对应于搜索
节点，“Sn(In)”表示搜索节点n持有整个索引I的子索引n，
并且“Snm(In)”表示复制编号为m的搜索节点
n持有整个索引I的子索引n。
来自调度器110的每个查询被发送给各个搜索节点以使得每个分区中的单个节点被
查询。例如，行124a、124b等中的所有节点都被查询，因为这些节点的组合表示
总索引。即组120中的每一行都是包括整个索引的所有分区的一组搜索节点。得到
的结果被调度器110合并，生成来自该组的完整结果。通过按上述方式分割数据，
数据量被缩减了。例如，如果有n列，则每个节点的搜索时间基本上被减少了n倍
-除去调度器110用于合并结果的时间。
通过复制搜索节点，提高了每个索引的查询处理速度。在图2中，每一列的所有搜
索节点都持有相同的索引。这使得调度器110在选择一组搜索节点来处理输入查询
时可以在每个索引分区的列中的节点之间轮换。
但是，发明人已经确定在典型的搜索引擎中存在倾斜度非常大的搜索查询分布。例
如，最上面的25个查询可以占到总查询量的1％。因此，将主索引等分成更小的
子索引不能得到最佳结果。
因此，在本领域中需要能够考虑搜索查询的分布来组织其文档和索引的搜索引擎。
发明内容
一种搜索引擎，其包括搜索WWW并且将在WWW上找到的网页存储在数据库中
的采集器。索引器将数据库中的网页编入索引以产生主索引。文档映射部件基于网
页的等级将数据库中的网页映射到多个分层中。等级可以基于网页中具有较高价值
的上下文。处理器基于上述映射从主索引中产生多个子索引。子索引被存储在搜索
节点组中。该搜索节点组是在逻辑上被排列成多个行和列的搜索节点矩阵。同一列
中的搜索节点包括相同的子索引。同一行中的搜索节点包括不同的子索引。从用户
接收到的搜索查询被发送到调度器，调度器又将查询转发给第一层的搜索节点。公
开了滑落(fall through)算法，其指示调度器何时应当将搜索查询转发给搜索节点的
其它层。
本发明的一个方面是一种用于为数据库中的数据项建立索引的方法。该方法包括从
数据库中获取数据项并产生数据项的主索引。该方法还包括基于数据项各自的等级
将数据项映射到至少第一层和第二层上。该方法还包括基于上述映射从主索引中产
生至少第一和第二子索引；以及将上述至少第一和第二子索引存储在不同的搜索节
点中。
本发明的另一个方面是用于搜索数据库的方法。该方法包括从数据库中获取数据项
并且产生数据项的主索引。该方法还包括基于数据项各自的等级将数据项映射到至
少第一层和第二层上。该方法还包括基于上述映射从主索引中产生至少第一和第二
子索引。该方法还包括将上述至少第一和第二子索引存储在不同的搜索节点中；接
收搜索查询；以及搜索第一层寻找与搜索查询相关的结果数据项。
本发明的另一个方面是用于为数据库建立索引的系统。该系统包括搜集数据库以找
到数据项的采集器。索引器接收数据项并且产生主索引。文档映射部件基于数据项
各自的等级将数据项映射到至少第一和第二层上。处理器基于上述映射从主索引中
产生至少第一和第二子索引。第一搜索节点存储第一子索引。第二搜索节点存储第
二子索引。
本发明的另一方面是实现对数据库的搜索的搜索节点组。搜索节点组包括在逻辑上
被排列在多个行和列中的搜索节点。任一列中的所有搜索节点实质上包括相同的信
息。任一行中的所有搜索节点包括不同的信息。行中的搜索节点逻辑上被分为至少
第一和第二层。第一层中的搜索节点包括对于数据库中的第一部分的索引。第二层
中的搜索节点包括对于数据库中的第二部分的索引。第一和第二层中的数据分别基
于数据库的第一和第二部分中的信息的等级。
本发明的另一个方面是一种包括搜集数据库以找到数据项的采集器的搜索引擎。索
引器接收数据项并且产生主索引。文档映射部件基于数据项各自的等级将数据项映
射到至少第一和第二层上。处理器基于上述映射从主索引中产生至少第一和第二子
索引。第一搜索节点存储第一子索引。第二搜索节点存储第二子索引。调度器接收
查询并且将查询转发给第一搜索节点。
附图说明
图1是示出了现有技术的搜索引擎结构的框图。
图2是示出了根据现有技术的一组节点的示图。
图3是示出了根据本发明实施例的搜索引擎的框图。
图4是示出了根据本发明的实施例将文档映射到分层中的功能的示图。
图5是示出了根据本发明的实施例将文档映射到分层和相应的一组节点中的示图。
图6是示出了根据本发明的实施例将文档映射到分层和相应的一组节点中的示图。
图7是示出了根据本发明的实施例将文档映射到分层和相应的一组节点中的示图。
图8是示出了根据本发明实施例的滑落算法的各个变量的值的表格。
图9是示出了根据本发明实施例的搜索算法的操作的流程图。
具体实施方式 参考图3，示出了根据本发明实施例的搜索引擎90。采集器102搜集例如互联网 100之类的信息源或例如企业或机构的网络之类的其它文件或文档集，然后将数据 存储在与信息源相对应的数据库108中。然后，文档映射算法114将文档映射到分 层中，下面会讨论。由处理器111控制的索引器105基于数据库108中映射后的文 档建立多个子索引。搜索节点组160中的多个搜索节点中的每一个都存储有各自的 子索引并且能够搜索各自的子索引。调度器110将来自用户112的查询发送给搜索 节点组160，下面会讨论。 最近的研究发现存在对互联网上最普遍的信息查询的倾斜分布。例如，大多数查询 (50％-80％)在一百万个最经常被请求的查询之内。类似地，不同月份中的各天重复 着80-85％的相同查询。相反，只有7％的查询在类似的时间段中仅被请求过一次。 为了利用这些事实，搜索引擎使用不相交的分层结构，其中不必对索引进行等分。 现在参考图4，基于一组属性将数据库108中的每一条数据映射到多个分层(图中 示出了三个分层)中的一层中。例如，被认为具有在由数据库管理者定义的第一阈 值以上的与搜索查询无关的静态相关等级的文档可以被映射到第I层。具有基于另 一阈值的第二高的等级的文档可以被映射到第II层。又如，每个文档或web网页 中的多个部分可以被分到不同的分层中。在特定文档中，如图4所示，诸如头部和 锚(anchor)之类的高级上下文可以置于第I层中而文档的主体可以置于第II层中。 周期性地对数据库108中的数据执行映射。 现在参考图5，数据结构(未明确地示出)被存储在调度器110中以使得组160中的 搜索节点在逻辑上被安排到特定的分层。在文档映射算法114将数据库108中的文 档映射到分层中以后，索引器105基于上述分层产生多个相应的子索引。子索引被 存储在组160中的各个搜索节点中。组160包括搜索节点的逻辑列162a、162b、 162c等和逻辑行164a、164b等。虽然这些节点被示为物理上被布置为行和列，但 是应当清楚这些节点在物理上不必如此布置，只要它们在逻辑上按类似的方式排列 即可。 每一列162中的搜索节点包括对同一子索引的复制，因此调度器110可以循环经过 多个搜索节点。每一行164中的搜索节点包括不同的子索引。例如，如图5中所示， 列162a中的搜索节点都包括来自第I层的信息。因而，通过算法114确定要被映 射到第I层的文档被映射到第I层，在索引器105中创建子索引并且针对第I层的 子索引被存储在列162a中的搜索节点中。 类似地，列162b中的搜索节点包括在第II层中的一部分信息。列162c中的搜索节 点包括来自第II层的没有包括在列162b中的搜索节点中的剩余信息。示出了第II 层的两个搜索节点列，并且索引可以在这些节点之间等分。很显然可以使用任意数 目的节点。 类似地，列162b中的搜索节点包括来自第III层的一部分信息。为了便于图示组 160，每一列中的节点被示为具有相同的大小，但是很清楚每个节点可以包括与同 一行中的其它节点相同或不同的信息量。例如，列162a行164a中的节点相比列 162b行164a中的节点可能具有较少的信息，因为它们在不同的分层中。作为所示 出的分层结构的示例，在所有第I层的节点中可以为150万个文档建立索引，在所 有第二层的节点中可以为600万个文档建立索引，而在所有第三层的节点中可以为 1000万个文档建立索引。 来自调度器110的每个查询首先在第一层的索引中被搜索，然后搜索基于存储在调 度器110中的滑落算法(“FTA”)继续到其它分层的索引。FTA确定查询是否应当在 其它分层中继续执行，并且还确定应当如何合并来自多个分层的结果。换一种说法， FTA基于诸如结果集合中的相关分数和索引项(hit)数之类的标准来确定一组分层中 的查询路径。FTA还确定在考虑下一个分层之前每个分层有多少结果可以被使用。 FTA使用多个变量来确定是否应当考虑下一个分层，所述变量包括：hitlimit、 percentlimit、ranklimit、termranklimit和minusablehits。变量hitlimit是对在执行向 下一分层的滑落(fall-through)之前来自分层的要使用的索引项数的估计。例如，对 于从第1层到第2层的跳变，hitlimit可以是1000，而对于从第2层到第3层的跳 变，hitlimit可以是8100。Percentlimit是在执行向下一分层的滑落之前可被使用的 来自分层的索引项的最大百分数。如果给定分层中的索引项数小于所有被请求的结 果的percentlimit，则发生滑落。例如，对于从第1层到第2层的跳变，percentlimit 可以是10，而对于从第2层到第3层的跳变，percentlimit可以是30。 Termranklimit-如果正在被考虑的索引项的相关分数小于termranklimit的值乘以查 询中的词数加上另一变量Ranklimit的结果，则执行向下一个分层的滑落。例如， 对于从第1层到第2层的跳变，ranklimit可以是200并且termranklimit是400。例 如，在两个词的查询中，通过上述标准的索引项的相关分数将是200+(2×400)＝ 1000。对于从第2层到第3层的跳变，ranklimit可以是0并且termranklimit是0。 Minusablehits-对于给定分层为了不进行紧接着向下一分层滑落而应当通过上述 FTA的标准的索引项数。这个数目通常是在结果网页上呈现给用户的结果数。其 思想是如果已知为了产生最经常被请求的索引项数而需要滑落，则应当尽早进行滑 落。这个变量应当使用常数值。例如，对于从第1层到第2层的跳变， minusablehits可以是0，而对于从第2层到第3层的跳变，minusablehits可以是100。 由于第2层仅处理经过了第1层的那些查询，并且第3层仅处理经过了第1层和第 2层的查询，所以希望第I层具有最好性能的节点。第2和第3层中额外的容量可 以通过复制列或者通过减少每个节点处的文档数来实现。 在图5的实施例中，使用了一维分层结构，其中使用静态相关分数分配所有的文档 和相应的索引。例如，静态相关分数可以基于web上的链接基数、链接的受欢迎 性或站点的受欢迎性。 例如，在有十亿个记录的数据库中，基于静态相关，最上面的3千万个文档被映射 到第1层，接下来的3亿6千万个文档被映射到第2层，再接下来的6亿1千万个 文档被映射到第3层。这种配置的一个缺点是使用静态相关仅仅是用于确定相关文 档的全部方案的一部分。 现在参考图6，示出了根据本发明的另一组节点170。组170可以用来替换组160 并且包括在列172a、172b等和行174a、174b等中的节点。在本实施例中，实现了 1.5维的配置。在一段时间中，为一百万个最常见的查询运行查询日志。上述一百 万个查询中的每个查询的最开始的20个索引项被映射到第1层，如图6中的176 所示。这可能有大约五百万个文档。余下的文档根据静态相关分数进行分配。例如， 对于有十亿个文档的数据库，最上面的3千万个文档被映射到第1层(这些文档中 的五百万个文档被锁定到这一层)，3亿6千万个文档被映射到第2层，并且6亿1 千万个文档被映射到第3层。如上所述使用了FTA。 现在参考图7，示出了根据本发明的另一组节点180。组180可以用来替换组160 并且包括在列182a、182b等和行184a、184b等中的节点。在本实施例中，实现了 2维的配置。在图7的实施例中，可选地使用了与图6中的1.5维的配置相同的分 层分布。但是，所有文档的高价值上下文中的信息被首先与第I层同时搜索。在确 定文档的动态相关时，这些高价值上下文是各个web网页中最重要的部分。这些 部分包括标题、锚等。 如果需要更多的索引项，则在从返回的结果中除去副本的同时使用多层配置来连续 地搜索全部索引。例如，最上面的3千万个文档(如上所述有5百万个文档被锁定) 的主体上下文被映射到第1层，3亿6千万个文档的主体上下文被映射到第2层， 并且6亿1千万个文档的主体上下文被映射到第3层。使用新的第0层，其包括全 部的十亿个文档的高级上下文(superior context)。图8中示出了用于组180的体系 结构的FTA的一些变量值。可选的第4层可以用于较低价值的文档。这种文档可 以是纯链接或垃圾信息文档。通过搜索第0层中的所有层的高价值上下文，本发明 利用了以下事实，即在第2层和第3层的节点中搜索相对较小的子集的信息比在这 些节点中搜索被编入索引的全部信息要廉价得多。 现在参考图9，示出了总结了本发明的一些操作的流程图。在S2中，搜索引擎搜 集数据源。在S4中，从数据源汇集的文档被存储在数据库中。在S6中，使用上 述算法中的一种将文档分成多个分层。在S8中，文档被映射到所确定的分层中。 在S10中，基于所确定的分层产生子索引。在S12中，将子索引存储在搜索节点 组中的各个搜索节点中。在S13中，接收来自用户的搜索查询。在S14中，搜索 引擎搜索第I层中的索引。在S16中，基于FTA，搜索引擎搜索第II层的搜索节 点和其它层的搜索节点。在S18中，将搜索的结果提供给用户。 因而，通过将数据库中的采集到的文档映射到不相交的多个分层中，实现了更快速、 更节约成本的搜索引擎。此外，通过提供可以动态地决定搜索多少个分层的滑落算 法，提高了对数据库的缩减。 虽然结合优选实施例描述并示出了本发明，但是本领域技术人员应当清楚在不脱离 本发明的精神和范围的情况下可以进行各种变化和修改，并且本发明不应被局限于 上述方法或结果的具体细节中，因为上述变化和修改也要包括在本发明的范围内。
发布评论