多个查询修订模型的集成

摘要

一种信息检索系统，包括查询修订架构，其集成了多个不同的查询修订器，每个查询修订器实现一个或者多个查询修订策略。修订服务器接收用户的查询，并且与各个查询修订器连接，每个查询修订器生成一个或者多个潜在修订的查询。修订服务器评估潜在修订的查询，并且选择它们中的一个或者多个提供给用户。

权利要求

1.一种用于查询修订的方法，包括：

计算多个查询对中的每个查询对的出现频率，每个查询对包括原始查询和修订查询，其中所述查询对的出现频率是所述修订查询在一个或多个用户会话中的出现次数与所述原始查询在所述一个或多个用户会话中的出现次数之比；

计算所述多个查询对中的每个查询对的质量分值的提高，其中所述质量分值的提高是根据针对查询对中的所述修订查询的点击行为数据得到的，针对查询对中的所述修订查询的点击行为数据与针对所述查询对中的所述原始查询的点击行为数据相关；

至少部分地基于所计算的出现频率和查询对的质量分值，计算每个查询对的置信度度量；

基于计算出的相应置信度度量选择所述多个查询对中的一个或多个查询对，其中所选择的一个或多个修订查询中的每个修订查询都产生最少数目的新搜索结果，其中新搜索结果是未出现在响应于所述修订查询的相应原始查询的多个最高排名搜索结果中的搜索结果；以及提供所选择的一个或多个查询对中的每个查询对的修订查询作为针对所选择的查询对的原始查询的建议修订。

2.根据权利要求1所述的方法，其中针对所述修订查询的点击行为数据是基于对于响应于所述修订查询的搜索结果进行的点击的持续时间。

3.根据权利要求2所述的方法，其中所述多个点击中的一个点击的持续时间是基于所述点击发生的时间和后续点击发生的时间。

4.根据权利要求1所述的方法，其中针对所述查询对中的所述修订查询的点击行为数据比针对所述查询对的所述原始查询的点击行为数据指示更高水平的用户满意度。

5.根据权利要求1所述的方法，其中基于计算出的相应置信度度量选择所述多个查询对中的一个或多个查询对包括：基于它们的相应置信度度量对所述多个查询对排名。

6.根据权利要求1所述的方法，其中所选择的一个或多个修订查询中的每个修订查询产生最少数目的搜索结果。

7.一种用于查询修订的设备，包括：

用于计算多个查询对中的每个查询对的出现频率的装置，每个查询对包括原始查询和修订查询，其中所述查询对的出现频率是所述修订查询在一个或多个用户会话中的出现次数与所述原始查询在所述一个或多个用户会话中的出现次数之比；

用于计算所述多个查询对中的每个查询对的质量分值的提高的装置，其中所述质量分值的提高是根据针对查询对中的所述修订查询的点击行为数据得到的，针对查询对中的所述修订查询的点击行为数据与针对所述查询对中的所述原始查询的点击行为数据相关；

用于至少部分地基于所计算的出现频率和查询对的质量分值来计算每个查询对的置信度度量的装置；

用于基于计算出的相应置信度度量选择所述多个查询对中的一个或多个查询对的装置，其中所选择的一个或多个修订查询中的每个修订查询都产生最少数目的新搜索结果，其中新搜索结果是未出现在响应于所述修订查询的相应原始查询的多个最高排名搜索结果中的搜索结果；以及用于提供所选择的一个或多个查询对中的每个查询对的修订查询作为针对所选择的查询对的原始查询的建议修订的装置。

8.根据权利要求7所述的设备，其中针对所述修订查询的点击行为数据是基于对于响应于所述修订查询的搜索结果进行的点击的持续时间。

9.根据权利要求8所述的设备，其中所述多个点击中的一个点击的持续时间是基于所述点击发生的时间和后续点击发生的时间。

10.根据权利要求7所述的设备，其中针对所述查询对中的所述修订查询的点击行为数据比针对所述查询对的所述原始查询的点击行为数据指示更高水平的用户满意度。

11.根据权利要求7所述的设备，其中用于基于计算出的相应置信度度量选择所述多个查询对中的一个或多个查询对的装置包括：用于基于它们的相应置信度度量对所述多个查询对排名的装置。

12.根据权利要求7所述的设备，其中所选择的一个或多个修订查询中的每个修订查询产生最少数目的搜索结果。

说明书

多个查询修订模型的集成

[0001] 相关申请的交叉引用

[0002] 本申请是优先权日为2005年3月29日、国际申请日为2005年3月30日、国际申请号为PCT/US2005/010681、中国专利申请号为200580049822.8的专利申请的分案申请。

[0003] 本发明涉及：

[0004] 2003年9月22日提交的题为“System and Method for Providing Search Query Refinements”的美国专利申请系列号No.10/688,721；

[0005] 2003年9月30日提交的题为“Method and Apparatus for Characterizing Documents Based on Clusters of Related Words”的美国申请系列号No.10/676,571；

[0006] 2003年12月15日提交的题为“Large Scale Machine Learning Systems and Methods”的美国申请系列号No.10/734,584；

[0007] 2004年6月28日提交的题为“Systems and Methods for Deriving and Using an Interaction Profile”的美国申请系列号No.10/878,926；

[0008] 2004年7月26日提交的题为“Phrase Identification in an Information Retrieval System”的美国申请系列号No.10/900,021；

[0009] 2005年3月28日提交的题为“Determining Query Terms of Little Significance”的美国申请系列号No.11/×××,×××；

[0010] 2005年3月30日提交的题为“Determining Query Terms Synonyms Within Query Context”的美国申请系列号No.11/×××,×××；以及

[0011] 美国专利No.6,285,999；

[0012] 在此将以上申请中的每一个通过参考并入。

技术领域

[0013] 本发明通常涉及信息检索系统，并且更具体地涉及用于修订用户查询的系统架构。

背景技术

[0014] 信息检索系统(例如因特网搜索引擎)一般能够快速地提供通常与用户的查询相关的文档。搜索引擎可以使用词语和文档频率的各种统计量度，以及文档之间和词语之间的关联，以便确定文档与查询的相关性。大多数搜索引擎设计下的关键技术假设是用户查询准确地表示用户的期望的信息目标。

[0015] 事实上，用户通常难以表示出良好的查询。单个查询经常不能提供期望的结果，并且用户频繁地输入关于同一主题的多个不同的查询。这些多个查询将通常地包括查询词语的宽度(breadth)和特征中的变化、猜测的实体名称、词序、词的数量等等的改变。因为不同的用户广泛地具有各种能力来成功地修订他们的查询，已经提出了各种自动的查询修订方法。

[0016] 最通常地，查询精化(refinement)用于从较一般的查询中自动地生成较精确的(即较窄的)查询。当用户输入过宽的查询时，其前面的结果包括关于用户的信息需要的文档的超集，主要使用查询精化。例如，想要关于三菱格兰(Galant)汽车信息的用户可能输入查询“三菱”，该查询过于宽泛，因为其结果将包含许多不同的三菱公司，而不仅仅是汽车公司。由此，将期望对该查询精化(尽管在此是困难的，因为缺少用于确定用户的特定信息需要的附加上下文)。

[0017] 然而，当用户输入过于具体的查询时，其中正确修订将加宽查询，或者当前面的结果与用户的信息需要不相关时，查询精化并不有用。例如，查询“三菱格兰(Galant)信息”可能因为词语“信息”而导致较差的结果(在这种情况下，关于三菱格兰(Galant)汽车的结果太少)。在这种情况下，正确修订用来加宽对“三菱格兰(Galant)”的查询。由此，尽管查询修订在某些情况下起作用，但是在很多情况下，需要通过使用其他查询修订技术来最好地满足用户的信息需要。

[0018] 另一查询修订策略使用同义词列表或者词典以扩展查询，从而捕捉用户的潜在信息需要。然而，与查询精化一样，查询扩展不总是修订查询的适合方式，并且结果的质量非常依赖于查询词语的上下文。

[0019] 因为在每个实例中没有一种查询修订技术可以提供期望的结果，所以期望具有一种方法，其提供多个不同的查询修订方法(或者策略)。

发明内容

[0020] 信息检索系统包括提供多个不同查询修订器(reviser)的查询修订架构，其中每个修订器实现其自己的查询修订策略。每个查询修订器评估用户查询以确定用户查询的一个或者多个潜在修订的查询。修订服务器与查询修订器交互作用以获得潜在修订的查询。修订服务器还与信息检索系统中的搜索引擎交互作用，以针对每个潜在修订的查询获得搜索结果集。修订服务器选择一个或者多个修订的查询，用于与针对每个选择的修订的查询的搜索结果的子集一起呈现给用户。由此用户能够查看针对修订的查询的搜索结果的质量，并且然后选择修订的查询之一以获得针对修订的查询的搜索结果全集。

[0021] 接下来参照各个附图、图表以及技术信息对本发明进行描述。附图仅出于示意的目的描绘了本发明的各种实施方式。根据以下描述本领域的技术人员将容易地认识到在不偏离本发明原理的前提下，可以采用所示出和描述的结构、方法以及功能的可选实施方式。

附图说明

[0022] 图1a是提供查询修订的信息检索系统实施方式的整体系统图；

[0023] 图1b是可选的信息检索系统的整体系统图；

[0024] 图2是原始用户查询的示例结果页面的图示；

[0025] 图3是示例修订查询页面的图示。

具体实施方式

[0026] 系统概述

[0027] 图1a示出了根据本发明的一个实施方式的系统100。系统100包括前端服务器102、搜索引擎104以及相关联的内容服务器106、修订服务器107以及多个查询修订器108。在操作期间，用户经由传统客户端118通过网络(诸如因特网，未示出)访问系统100，其在任意类型的客户端计算设备上操作，例如执行浏览器应用或者适合用于通过因特网相关协议(例如TCP/IP以及HTTP)通信的其他应用。尽管仅示出了单个客户端118，但是系统100可以支持与许多客户端的很多个并发会话。在一个实施中，系统100在高性能服务器类计算机上操作，并且客户端设备118可以是任何类型的计算设备。关于服务器和客户端计算机的硬件方面的细节对于本领域技术人员已公知，在此不再赘述

[0028] 前端服务器102负责接收客户端118提交的搜索查询。前端服务器102向搜索引擎104提供查询，该搜索引擎根据搜索查询来评估查询以取回搜索结果集，并且将结果返回前端服务器102。搜索引擎104与一个或者多个内容服务器106通信以选择关于用户的搜索查询的多个文档。内容服务器106存储从不同网站索引(和/或检索)的大量文档。可选地或者附加地，内容服务器106存储在各个网站上存储的文档的索引。在此将“文档”理解为任何形式的可索引内容，包括任何文本或者图形格式的文本文档、图像、视频、音频、多媒体、演示、网页(其可以包括嵌入的超链接和其他元数据和/或程序，例如以Javascript编写)等。在一个实施方式中，根据文档的链接结构，对每个索引的文档赋予页面等级。页面等级作为文档重要性的独立于查询的度量。在美国专利No.6,285,999中描述了页面等级的示例性形式，在此通过参考将其并入。基于文档的页面等级(和/或文档重要性的其他独立于查询的度量)、以及文档重要性(例如搜索词语在文档中的位置和频率)的一个或者多个依赖于查询的信号，搜索引擎104对每个文档分配分值。

[0029] 前端服务器102还向修订服务器107提供查询。修订服务器107与多个不同查询修订器108进行接口连接，其中每个查询修订器108实施不同的查询修订策略或者策略集。在一个实施方式中，查询修订器108包括：加宽修订器108.1、语法修订器108.2、精化修订器108.3以及基于会话的修订器108.4。修订服务器107向每个修订器108提供查询，并且响应于每个修订器108而获取一个或者多个潜在的修订查询(在此称为“潜在的”，因为在此时它们还没有被修订服务器107采用)。系统架构特别地设计为允许使用任何数量的不同查询修订器108，因为不好的执行查询修订器108将被去除，以及因为在将来需要时将添加新的查询修订器108(由普通修订器108.n来指示)。这赋予了系统100特别的灵活性，并且还使得系统能够被定制以及适应用于特定主题内容领域(例如，用于在如医药、法律等领域的修订器)、企业(针对内部信息检索系统，专用于特别商业领域或者公司域的修订器，)、或者针对不同语言(例如针对指定语言或者方言的修订器)。

[0030] 优选地，每个修订的查询与置信度度量度量(confidence measure)相关联，该置信度度量度量表示修订是良好修订的概率，良好修订即修订的查询将产生的结果比原始查询产生的结果与用户的信息需要更相关。由此，每个潜在修订的查询可以通过元组(tuple)(Ri，Ci)来表示，其中R是潜在修订的查询，并且C是与该修订的查询相关联的置信度度量。在一个实施方式中，针对每个修订器108的每个修订策略，预先人工地估计这些置信度度量。可以从测试下的示例查询和修订的查询的结果分析中导出该度量。例如，精化修订器
108.3可以对来自原始短查询(例如三个或者更少词语)的修订的查询分配高置信度度量，以及对来自原始长查询(四个或者更多词语)的修订的查询分配低置信度度量。这些基于经验评估的分配示出了添加词语到短查询有助于显著地改进查询关于潜在的信息需要的相关性(即短查询可能过于宽泛，并且这种查询的精化可能集中在较窄并且较相关的结果集上)。相反地，加宽修订器108.1可以对从长查询减少一个或者多个词语、或者向长查询添加同义词的修订的查询分配高置信度度量。在其他实施方式中，一个或者多个修订器108可以针对其潜在修订的查询中的一个或者多个动态地生成置信度度量(例如在运行时)。结合图
1b在下文中对这种实施方式进一步描述。置信度度量的分配可以由其他组件执行(例如修订服务器107)，并且可以考虑依赖于查询的数据和独立于查询的数据两者。

[0031] 修订服务器107可以选择一个或者多个(或者所有)潜在修订的查询，并且将这些提供到搜索引擎104。搜索引擎104以与处理正常查询相同的方式处理修订的查询，并且将每个提交的修订的查询的结果提供到修订服务器107。修订服务器107评估每个修订的查询的结果，包括比较修订的查询的结果和原始查询的结果。修订服务器107然后可以选择一个或者多个修订的查询作为最佳修订的查询(或者至少很好地适合于原始查询的修订的查询)，如下文所述。

[0032] 修订服务器107接收所有潜在修订的查询R，并且通过它们的相关联的置信度度量C从最高到最低置信度度量对它们进行排序。修订服务器107通过潜在修订的查询的排序表进行迭代，并且传送每个潜在修订的查询到搜索引擎104以获得搜索结果集。(可选地，修订服务器107可以首先选择潜在修订的查询的子集，例如那些具有阈值水平以上的置信度度量的潜在修订的查询)。在一些情况下，可能已经提取前面的搜索结果(例如通过修订器108或者修订服务器107)，同时执行修订策略或者估计置信度度量，在这种情况下修订服务器107可以使用这样获得的搜索结果。

[0033] 针对每个潜在修订的查询，修订服务器107决定是否选择潜在修订的查询还是丢弃该查询。选择可以依赖于针对修订的查询的前N个搜索结果的评估，既独立于又相关于原始查询的搜索结果。通常地，修订的查询应该产生搜索结果，该搜索结果比原始查询更精确地反应用户的信息需要。通常评估前十个结果，但是如果期望的话可以处理更多或者更少的结果。

[0034] 在一个实施方式中，如果具有以下条件，则选择潜在修订的查询：

[0035] i)修订的查询产生至少最小数量的搜索结果。例如，将该参数设置为1将丢弃所有(并且仅丢弃)没有搜索结果的修订。结果的可接受的最小数量的一般范围是1到100。

[0036] ii)修订的查询在修订的前面的结果中产生最小数量的“新”结果。当结果未出现在原始查询或者先前选择的修订的查询的前面的结果中时，该结果是“新”的。例如将该参数设置为2将要求每个选择的修订具有至少两个前面的结果，其在任何先前选择的修订的查询的前面的结果中或者原始查询的前面的结果中都未出现。该限制确保在选择的修订中的结果的多样性，将证明至少一个修订是有用的机会最大化。例如，如图3中可见，针对每个修订的查询的前三个结果304不同于其他结果集。这给予用户对与修订的查询高度相关的搜索结果的宽泛检查(survey)。

[0037] iii)还没有选择修订的查询的最大数量。换言之，当已经选择了修订的查询的最大数量时，则丢弃所有剩余修订的查询。在一个实施方式中，将修订的查询的最大数量设置为4。在另一个实施方式中，修订的查询的最大数量被设置为在2和10之间。

[0038] 前述选择参数的结果是将在修订的查询页面300上包括选择的修订的查询集。修订服务器107构建了到该页面的链接，并且将该链接提供到前端服务器102，如前所述。修订服务器107确定修订的查询页面300上的修订的查询的顺序和布局。修订的查询优选地按它们的置信度度量(从最高到最低)顺序列出。

[0039] 前端服务器102包括在搜索结果页面中提供的链接，然后该搜索结果页面被传送到客户端118。然后用户可以查看对于原始查询的搜索结果、或者选择到修订的查询页面的链接，并且由此查看选择的修订的查询以及其关联结果。

[0040] 修订的查询的呈现

[0041] 图2示出了提供给客户端118的示例结果页面200。在这个简单的实施中，搜索结果200页面包括[sheets(片状物)]的原始查询202以及该查询的结果204。到修订的查询集的链接206被包括在页面200的底端。然后，用户则可以点击链接206，并且访问修订的查询页面。图3中示出了示例页面300。在此，呈现了前面的三个修订的查询，如修订的查询链接
302.1、302.2以及302.3所示，该修订的查询链接分别针对[linens(亚麻布)]、[bedding(被褥)]以及[bed sheets(床单)]的修订的查询。在每个修订的查询链接302以下是针对该查询的前面的三个搜索结果304。

[0042] 在与原始结果页面200分开的页面300上提供修订的查询存在多种优势。首先，屏幕区域是有限的资源，并因此，尽管可能但不希望通过屏幕区域列出了修订的查询本身(不预览它们的关联结果)，因为用户看不见其结果的上下文中的修订的查询。通过将修订的查询放置在独立页面300上，用户可以看见最佳修订的查询以及与它们相关联的前面的结果，使得用户能够在选择修订的查询自身之前，选定看起来最佳地满足他们的信息需要的修订的查询。尽管在单个(虽然很长)页面上可能包括原始查询和修订的查询的结果两者，该方法将要求用户向下滚动页面以查看所有修订的查询，或者将弄乱页面的初始可视部分。取而代之的是，在图2和图3中示出的优选实施方式中，用户可以看见与查询修订相关联的结果，点击每个修订的查询链接302，并且访问针对选择的修订的查询的整个搜索结果集。在许多情况下，该方法将还优选地自动使用修订的查询，以获得搜索结果并且自动地将它们呈现给用户(例如无须用户选择或者交互)。另外，该方法还具有通过示出最佳潜在修订而间接教导用户如何创建更佳查询的附加优势。在另一实施方式中，修订服务器107可以强迫查询修订被显示在原始结果页面200上，例如，在独立窗口中或者在原始结果页面200内。

[0043] 显示附加信息(例如搜索结果304)的方法还可以用于主要结果页面200上，其中该附加信息是关于查询修订的，以帮助用户更好地理解修订。当存在单个非常高质量的修订查询(或者少量非常高质量修订)时，诸如在校正拼写的修订的情况下，这一点尤其有用。校正了拼写的修订的查询可以与诸如前面的结果的题目、URL以及片段(snippet)的附加信息一起在结果页面200上示出，以帮助用户确定拼写校正建议是否是良好的建议。

[0044] 在另一实施方式中，修订服务器107使用置信度度量来决定是否完全示出查询修订，并且如果决定示出，则决定如何突出地放置修订或者其链接。将在下文对该实施方式进行描述。

[0045] 查询修订器

[0046] 再次参考图1，现在描述各种查询修订器108。加宽修订器108.1生成有效加宽原始查询范围的一个或者多个修订的查询。在原始查询过窄的情况下，这些修订尤其有用。存在可以由加宽修订器108.1使用的多个不同的策略。

[0047] 首先，该修订器108.1可以通过添加同义词以及相关词语作为析取项(disjunct)来加宽查询。查询经常过于具体，因为用户恰巧选定特定词来描述一般概念。如果关注的文档不包含该词，则用户的信息需要仍然未满足。添加同义词作为析取项的查询修订可以加宽查询并且将期望的文档带进结果集。类似地，有时添加相关词而不是添加实际的同义词作为析取项更有帮助。可以在此使用任何适合的查询加宽方法，诸如相关词语、同义词、词典或者字典等。一种用于查询加宽的方法在于2005年3月30日提交的题为“Determining Query Term Synonyms Within Query Context”的美国申请系列号No.11/×××,×××中公开，通过参考将其并入。

[0048] 第二，该修订器108.1通过去掉一个或者多个查询词语可以加宽查询。如所示出的前面的例子，有时去掉查询词语(如例子查询“三菱格兰(Gallant)信息”中的“信息”)可能得到良好的查询修订。在该方法中，加宽修订器108.1确定哪些查询词语不重要，其中因为它们的存在与它们不存在相比未能显著改进搜索结果。在2005年3月28日提交的题为“Determining Query Terms of Little Significance”的美国申请系列号No.11/×××,×××中描述了用于为搜索目的而识别不重要的词语的技术，在此通过参考将其并入。这种技术的结果可以用于通过去掉不重要的词语来修订查询。

[0049] 语法修订器108.2可以通过对原始查询进行各种类型的语法改变来修订查询。这些包括以下修订策略：

[0050] ·如果存在引用，去除原始查询中的任何引用。通过搜索引擎104将引用中的查询作为单个文字来对待，其仅返回具有整个查询串的文档。通过允许搜索引擎104基于文档与任意查询词语的总体相关性而返回文档，该修订增加了搜索结果的数量。

[0051] ·添加围绕整个查询的引用。在一些实例中，查询更适合于被作为完整短语来处理。

[0052] ·添加围绕查询更像实际短语的n-grams(查询内某个连续词语的数量)的引用。查询内n-grams的识别可以使用以下各种源来进行：

[0053] A)常用短语的自建字典。

[0054] B)根据频率数据建立的短语列表。在此，基于出现具有统计上显著频率的词语的序列而识别短语。例如，良好的bi-gram[t1 t2]具有以下特性：如果[t1]和[t2]两者一起出现在文档中，具有比随机概率更高的概率，则它们表现为bi-gram[t1 t2]。一种用于构建短语列表的方法在2004年7月26日提交的题为“Phrase Identification in an Information Retrieval System”的美国申请系列号No.10/900,021中公开，在此通过参考将其并入。

[0055] C)常用名和姓的列表(例如从人口调查数据或者任何其他源所获得)。语法修订器108.2针对查询词语[t1 t2]的每个连续对确定[t1]是否包含在常用名的列表中，以及[t2]是否包含在常用姓的列表中。如果如此，则将查询[t1 t2]的子部分(subportion)置于引用标记中，以形成潜在修订的查询。

[0056] 一个普遍问题是在查询中使用停用词(stopword)。分级算法通常忽略频繁的词语，诸如“the”、“a”、“an”、“to”等。在一些情况中，这些实际上是查询中的重要词语(考虑查询例如“to be or not to be”)。因此，语法修订器108.2还创建多个修订的查询，该修订的查询使用“+”算符(或者类似的算符)，以便强制包括这样的词语，而无论这种词语何时出现在查询中。例如查询[the link]，将建议为[+the link]。

[0057] ·除去标点符号和其他符号。用户偶然添加改变查询意义的标点符号或者其他句法(syntax)(诸如符号)。因为大多数用户是无意这样做的，所以语法修订器108.2还通过除去标点符号和其他类似的句法(不论何时出现)而产生修订的查询。例如，针对查询[rear window+movie]，语法修订器产生查询[rear window movie]，其将防止搜索引擎104关于字符序列“window+”进行搜索，其根本不可能产生任何结果。

[0058] 精化修订器108.3可以使用任何适合的方法来精化(即变窄)查询，以便更具体地描述用户的潜在信息需要。在一个实施方式中，精化修订器108.3通过比较搜索查询的词语矢量表示和已知搜索查询的词语矢量而产生查询修订，其先前已经与它们各自的搜索结果相关联并根据该搜索结果加权。选择具有最接近矢量的一个或多个已知搜索查询作为潜在的修订的查询。

[0059] 更具体地，在一个实施方式中精化修订器108.3操作如下。精化修订器108.3使用用户的原始查询以获得从搜索引擎104选择的多个搜索结果(例如，前面的100个结果)。精化修订器108.3访问预先存在的数据库并且将这些文档中的每一个与一个或者多个先前使用的搜索查询相匹配，其中所述搜索查询将该文档包括在其结果中。预先存在的数据库存储与搜索查询相关联的文档，其中查询和文档之间的关联通过针对文档的查询的相关性分值来加权。

[0060] 第二，精化修订器108.3使用聚类算法来基于从匹配的存储的查询的词语以及对应的权重形成的词语矢量而形成搜索结果文档群集。词语矢量是单位长度归一化的多维矢量，其中每一维对应一个词语，该词语可以是单个词或者词组合。基于在每个群集中出现的存储文档的数量和与匹配的存储文档相对应的原始搜索文档的相关性分值来对群集进行排名。最高排名群集被选择作为潜在的精化群集。群集可以使用各种聚类算法来形成，该聚类算法诸如分层合并聚类算法(hierarchical agglomerative clustering algorithm)，如E.Rasmussen在“Information Retrieval”(W.Frakes & R.Baeza-Yates des.92)中的“Clustering Algorithms”所描述的那样，在此通过参考将该公开并入。

[0061] 第三，精化修订器108.3针对每个潜在的精化群集计算群集质心。然后精化修订器108.3针对每个群集确定潜在的修订的查询。在给定的精化群集中，针对与群集中的文档相关联的每个先前存储的搜索查询，精化修订器108.3基于到群集质心的搜索查询的词语矢量距离和存储的与该搜索查询相关联的文档数量，对存储的查询进行评分。在每个潜在精化群集中，分值最高的先前存储的查询被选择作为潜在的修订的查询。

[0062] 最后精化修订器108.3提供选择的修订的精化查询到修订服务器107。一个适合的精化修订器的细节进一步在2003年9月22日提交的题为“System and Method for Providing Search Query Refinements”的美国专利申请系列号No.10/688,721中公开，在此通过参考将其引入。

[0063] 基于会话的修订器108.4可以使用任何适合的方法，该方法基于其他用户在过去已经做出的改变的分析而使用基于会话的用户数据更正确地捕捉用户的潜在信息需要。在一个实施方式中，基于会话的修订器108.4基于从多个单独用户会话中收集的点击数据而提供一个或者多个修订的查询。查询对的出现频率初始是使用由基于会话的修订器108.4生成的两个表来计算的。查询对是出现在单个用户会话中的两个查询的序列，例如第一查询[sheets(片状物)]，其后跟有第二查询[linens(亚麻布)]或者第二查询[silk sheets(丝质床单)]。重现单独查询的第一表是根据用户会话查询数据(例如存储在图1b的日志文件110中的数据)生成。在一个实施方式中，重现查询以最小频率出现，例如每天一次。重现查询对的第二表也根据日志文件110生成，每个查询对包括第一查询，其后跟有第二查询。根据这两个表，每个查询对的出现频率计算作为第一表中的第一查询的出现计数的一部分。例如如果查询[sheets(片状物)]出现100次，并且100次中有30次在其后跟有第二查询[linens(亚麻布)]，则作为第一查询的出现计数的一部分，查询对[sheets(片状物)，linens(亚麻布)]的出现频率是30/100或者30％。对于任何给定的第一查询，如果出现频率超过了某个阈值，随着第二查询作为针对第一查询的候补修订，保留查询对。在一个实施方式中，该阈值是1％。

[0064] 对于候补修订的查询，查询对中第二查询比该对中第一查询在质量方面的提高是使用由基于会话的修订器108.4从用户点击数据而生成的两个附加表来计算的。质量分值表是针对该对中的每个查询而生成的。根据该表，计算该对中的第二查询在质量方面超过该对中的第一查询的提高(如果有提高)。

[0065] 在一个实施方式中，质量分值是通过从点击行为数据估计用户满意程度来确定。一种这样用于确定质量分值的方法是使用交互简档，如2004年6月28日提交的题为“Systems and Methods for Deriving and Using an Interaction Profile”的美国申请系列号No.10/878,926中所描述的那样，在此通过参考将其并入。

[0066] 在一个实施方式中，质量分值计算基于存储的(例如在日志文件110中存储的)用户点击数据。质量分值是基于搜索结果上的第一点击的估计的持续时间。在一个实施方式中，特定点击的持续时间从第一点击和随后点击发生的次数来估计，其可以与其他用户会话查询数据存储在例如图1b的日志文件110中。进行评分包括对没有点击的搜索结果分配分值为0，并且继续沿着应用于第一点击和随后点击之间的持续时间的S曲线，较长的点击接近于分配质量分值为1。在一个实施方式中，20秒对应于0.1，40秒对应于0.5，以及60秒对应于0.9。从数据中排除不相关的内容(例如标题广告)上的点击。在另一实施方式中，收集针对查询所有产生的点击，而不仅仅是第一点击。

[0067] 然后基于会话的修订器108.4可以使用上述的频率出现和质量分值数据来计算作为候补修订的查询的第二查询超过第一查询的期望效用。在一个实施方式中，期望的效用是查询对的出现频率与该对中第二查询在质量方面超过第一查询的提高的乘积。在该例子中，如果针对第二查询的质量分值高于针对第一查询的质量分值，则发生质量方面的改善。如果第二查询的期望效用超过阈值，则将第二查询标记为潜在的修订的查询。在一个实施方式中，阈值为0.02，例如对应于10％的频率和在质量方面提高0.2，或者20％的频率和在质量方面提高0.1。也可以使用期望效用计算的其他变形。

[0068] 如上文所述，每个修订的查询可以与置信度度量相关联，该置信度度量表示修订是良好修订的概率。在基于会话的修订器108.4的情况下，修订的查询的期望效用可以用作针对该修订的查询的置信度度量。

[0069] 使用基于会话的修订器108.4的查询修订的例子如下所述。第一用户查询是[sheets(片状物)]。存储的数据指示跟在[sheets(片状物)]后面的一个常用用户输入的(第二)查询是[linens(亚麻布)]并且另一常用输入的第二查询是[silk sheets(丝质床单)]。基于存储在日志文件110中的数据，查询对[sheets(片状物)，linens(亚麻布)]的频率是30％，并且查询对[sheets(片状物)，silk sheets(丝质床单)]的频率是1％，作为第一查询[sheets(片状物)]的出现百分比。例如，如果查询[sheets(片状物)]在表中出现了100次，则[sheets(片状物)，linens(亚麻布)]出现了30次并且[sheets(片状物)，silk sheets(丝质床单)]出现了一次。假设作为候补修订的第二查询阈值是1％，则这两个查询都将保留。

[0070] 接下来，数据指示针对[sheets(片状物)]的质量分值是0.1，而针对第二查询[linens(亚麻布)]和[silk sheets(丝质床单)]的质量分值分别是0.7和0.8。这样，[linens(亚麻布)]在质量方面超过[sheets]的提高是0.6(0.7-0.1)，并且[silk sheets(丝质床单)]在质量方面超过[sheets(片状物)]的提高是0.7(0.8-0.1)。

[0071] 然后，基于会话的修订器108.4将每个修订的期望效用计算为频率分值与质量方面的提高的乘积。对于[sheets(片状物)，linens(亚麻布)]，频率(30％)与质量方面的提高(0.6)的乘积得出期望效用为0.18。对于[sheets(片状物)，silk sheets(丝质床单)]，频率(1％)与质量方面的提高(0.7)的乘积得出期望效用为0.007。这样，针对输入第一查询[sheets(片状物)]的用户，第二查询[linens(亚麻布)]具有比查询[silk sheets(丝质床单)]更高的期望效用，并且因此[linens(亚麻布)]是较好的查询修订建议。这些期望效用可以用作如上所述的修订的查询的置信度度量。

[0072] 在运行时生成修订置信度度量

[0073] 现在参考图1b，这里示出了根据本发明的信息检索系统的另一实施方式。除了先前描述的图1a的元件，还存在日志文件110、会话跟踪器114以及修订器置信度估计器112。如上所述，查询修订器108可以向置信度度量提供一个或者多个修订的查询，该置信度度量是查询修订器108提供给修订服务器107的。修订服务器107使用置信度度量来确定选择哪个可能的修订的查询用于包括在修订的查询页面300上。在一个实施方式中，在运行时可以获得置信度度量，至少部分地基于在关于给定原始查询选择修订的查询中的历史用户活动。

[0074] 在图1b的实施方式中，前端服务器102向会话跟踪器114提供用户点进行为、以及原始查询和修订的查询信息。会话跟踪器104维持日志文件110，该日志文件存储与用户所访问的查询修订链接302相关联的每个用户查询、与每个修订的查询相关联的结果、以及与用于对修订的查询的质量建模的原始查询和修订的查询的各种特征。存储的信息可以包括，例如：

[0075] 对于原始查询：

[0076] ·原始查询自身；

[0077] ·原始查询中的每个词；

[0078] ·原始查询的长度；

[0079] ·原始查询的主题群集；

[0080] ·针对原始查询的信息检索分值；以及

[0081] ·针对原始查询的结果数量。

[0082] 对于修改的查询：

[0083] ·修订的查询自身；

[0084] ·修订的查询中的每个词；

[0085] ·产生其的修订技术的标识；

[0086] ·修订的查询的长度；

[0087] ·与修订的查询相关联的主题群集；

[0088] ·针对前面的搜索结果的信息检索分值(例如，页面等级)；

[0089] ·针对修订的查询找到的结果的数量；

[0090] ·在修订的查询链接302上的点击长度；以及

[0091] ·在修订的查询结果304上的点击长度。

[0092] 使用任何适合的主题标识方法对针对查询的主题群集进行标识。在2003年9月30日提交的题为“Method and Apparatus for Characterizing Documents Based on Clusters of Related Words”的美国申请系列号10/676,571中描述了一种适合的方法，在此通过参考将其并入。

[0093] 修订器置信度估计器112使用预测模型，例如多个、逻辑回归模型分析日志文件110以基于修改的查询和查询的特征来产生一组规则，该规则可以用于估计针对给定的查询修订的查询是成功修订的可能性。在2003年12月15日提交的题为“Large Scale Machine Learning Systems and Methods”的美国申请系列号No.10/734,584中描述了一个适合的回归模型，在此通过参考将其并入。修订器置信度估计器112基于以下假设而操作：用户对修订的查询链接302上的长点击指示了用户对该修订作为用户的原始信息需要的准确表示满意。可以认为长点击发生在当用户停留在点击页面上一段最小时间段时，例如最小为60秒。从对修订的查询链接302上的点击长度，修订器置信度估计器112可以训练预测模型来预测长点击符合修订的查询和原始查询的各种特征的可能性。认为具有长点击的高预测可能性的修订的查询是针对其关联原始查询的较好(即，更成功)的修订。

[0094] 在一个针对预测模型的实施方式中，置信度估计器112选择与修订的查询相关联的特征；从日志文件收集点击数据；使用该特征和点击数据制定规则；以及添加该规则到预测模型。另外，置信度估计器112可以使用点击数据制定附加规则并且选择性地添加该附加规则到模型。

[0095] 在运行时，修订服务器107向修订器置信度估计器112提供原始查询、以及从各种查询修订器108接收的修订的查询中的每一个。修订器置信度估计器112将原始查询和修订的查询应用于预测模型以便获得预测度量，该预测度量作为先前提及的置信度度量。可选地，每个查询修订器108可以直接调用修订器置信度估计器112以便获得预测度量，并且然后将这些值传递回到修订服务器107。尽管所描述的实施方式示出了修订器置信度估计器112作为单独的模块，但是修订服务器107代替地可以提供置信度度量估计器功能。在任一情况下，如上所述，修订服务器107使用置信度度量，以便选择和排序将示于用户的修订的查询。

[0096] 在一个实施方式中，修订服务器107使用置信度度量以便确定是否完全示出查询修改，如果确定为示出，则确定怎样突出地放置修订或者其链接。为了这样做，修订服务器107可以使用先前讨论的初始置信度度量或者上文所述的动态生成的置信度度量。例如，如果最佳置信度度量落入阈值以下，这可以指示没有一个潜在候补修订中是非常好的，在这种情况下对原始结果页面200不进行修改。在另一方面，如果一个或者多个修订的查询具有在另一阈值以上的非常高的置信度度量，则修订服务器107可以强制查询修订、或者到修订的查询页面300的链接在原始结果页面200上非常突出地示出，例如在页面的顶部附近并且用特殊字体、或者在某个其他突出位置示出。如果置信度度量在两个阈值之间，则到修订的查询页300的链接可以放置在较不突出的位置上，例如在搜索结果页面200末端，例如，如链接206所示。

[0097] 可以并行地(例如，获得针对查询修订的结果并且计算针对查询修订的置信度度量)、和/或交织地(例如从查询修订器接收多个查询修订并且构建不工作的查询修订的排序列表，而不是接收所有查询修订然后对查询修订的列表进行排序)执行处理上文所述的步骤。另外，尽管在客户端/服务器搜索系统的环境中描述了以上实施方式，但是本发明还可以作为单独的机器(例如，单独PC)的部分来实施。这可能是有用的，例如在诸如谷歌桌面搜索的桌面搜索应用的环境中。

[0098] 本发明特别描述了关于一个可能的实施方式的细节。本领域技术人员将理解本发明可以以其他实施方式实现。首先，对组件、词语的大写开头字母、属性、数据结构或者任何其他编程或者结构方面进行的特别命名不是强制性的或重要的，并且实施本发明或者其特征的机制可以具有不同的名称、格式或者协议。另外，系统可以通过所描述的硬件和软件的组合来实施，或者完全用硬件元件来实施。而且，在此描述的各种系统组件之间的特别的功能性划分仅是示例性的，并且不是强制的；由单个系统组件执行的功能可以代替地由多个组件来执行，并且由多个组件执行的功能可以代替地由单个组件来执行。

[0099] 上文描述的某些部分按照关于信息的操作的算法和符号表示呈现了本发明的特征。这些算法描述和表示是由数据处理领域的技术人员所使用的手段，以便对本领域的其他技术人员最有效地传达他们的工作本质。虽然对这些操作进行了功能性地或者逻辑地描述，但应理解由计算机程序来实施这些操作。而且，还证明将这些操作布置称作模块或者功能名称有时是方便的，并不损失通用性。

[0100] 除非特别描述，否则根据上述描述显然可以理解，贯穿描述，所描述的动作和处理是计算机系统或者类似的电子计算设备的描述的动作和处理，该计算机系统或者类似的电子计算设备处理和转换数据，该数据表示为在计算机系统存储器或者寄存器或者其他这种信息存储、传输或者显示设备中的物理(电子)量。在此不提供这种计算机系统的基础硬件的详细描述，因为该信息对于计算机工程领域的技术人员是普遍公知的。

[0101] 本发明的某些方面包括在此以算法形式描述的处理步骤和指令。应该注意到本发明的指令和处理步骤可以用软件、固件或者硬件来实现，以及当用软件实现时，本发明的指令和处理步骤可以被下载以便驻留在由实时网络操作系统使用的不同平台上以及从所述平台上操作。

[0102] 本发明的某些方面已经针对独立或者单个例子进行了描述；然而应该理解，本发明的操作不限于此。因此，所有对单个元件或者组件的涉及应该解释为还涉及多个这种组件。类似地，除非明确地声明，否则涉及“a”、“an”或者“the”应该解释为包括涉及多个。最后，词语“多个”的使用意味着两个或者两个以上实体、数据项等，如适合用于讨论的本发明的一部分，并且覆盖无限的或者过多的条目数量。

[0103] 本发明还涉及用于在此执行操作的设备。该设备可以针对所需目的特定地构建，或者可以包括由存储在可由计算机访问的计算机可读介质上的计算机程序重新配置或者选择性地激活的通用计算机。这种计算机程序可以存储在计算机可读存储介质中，诸如但不限制于任何类型的盘，包括软盘、光盘、CD-ROM、磁光盘、只读存储器(ROM)、随机访问存储器(RAM)、EPROM、EEPROM、磁或者光卡、或者适合用于存储电子指令的任何类型介质，并且每个均耦合到计算机系统总线。集成电路设计和视频编解码领域的技术人员应该理解，可以以各种类型的集成电路基于上述功能和结构描述而容易地制造本发明，包括应用专用集成电路(AISC)。另外，本发明可以并入到各种类型的视频编码设备中。

[0104] 在此呈现的算法和操作未固有地涉及任何特别的计算机或者其他设备。各种通用系统还可以根据在此的教导与程序一起使用，或者可以证明便于构建更具体化的设备从而执行所要求的方法步骤。多种这样的系统所要求的结构以及等效变形对于本领域技术人员而言是明显的。另外，本发明未参考任何特别的编程语言进行描述。应该理解，可以使用多种编程语言实施在此所描述的本发明的教导，并且将对特定语言的任何涉及提供给本发明的最佳模式和实现的公开。

[0105] 最后，应该注意，主要为了易读性和示教的目的而主要地选择本说明书中使用的语言，并且可以不为描绘或者限制本发明实质内容选择该语言。因此，本发明的公开内容旨在示意性而并非限制本发明的范围。