查询多方面信息的方法和系统

1.一种在信息检索系统中查询多方面信息的计算机实现的方法，所述方法包括：
由所述信息检索系统构建倒排索引，所述倒排索引具有多个以一一对应关系与多个置入列表关联的唯一索引标记，每个置入列表包括多个文档中的一个或多个文档，其中所述多个唯一索引标记中的索引标记是以下两者之一：作为注释包括在所述多个文档中的一个文档内的方面标记，以及所述方面标记的路径前缀，其中所述注释指示树形结构中的路径，所述树形结构代表包括所述文档的方面，所述树形结构包括多个节点，所述节点代表对所述文档进行分类的类别和一个或多个子类别；
由所述信息检索系统接收包括针对所述多个文档的多个约束的查询，所述多个约束与所述多个唯一索引标记中的多个索引标记以及对应于所述多个索引标记的多个置入列表关联；以及
由所述信息检索系统执行所述查询，所述执行包括：
利用所述多个约束和所述倒排索引来标识所述多个置入列表，以及
求所述多个置入列表的交集以获得所述查询的结果。
2.如权利要求1中所述的方法，其中所述多个约束包括一个或多个方面约束以及一个或多个自由文本约束，并且其中所述标识所述多个置入列表包括：
通过所述倒排索引标识第一组以一一对应关系与所述一个或多个方面约束关联的一个或多个索引标记以及第二组以一一对应关系与所述一个或多个自由文本约束关联的一个或多个索引标记，所述第一组和所述第二组一个或多个索引标记包括在所述多个唯一索引标记中；以及
通过所述倒排索引标识第一组一个或多个置入列表和第二组一个或多个置入列表，所述第一组的所述一个或多个置入列表以一一对应关系与所述第一组的所述一个或多个索引标记关联，并且所述第二组的所述一个或多个置入列表以一一对应关系与所述第二组的所述一个或多个索引标记关联。
3.如权利要求1中所述的方法，其中所述构建所述倒排索引包括：
通过所述倒排索引生成完整路径标记及与其关联的完整路径标记置入列表，所述完整路径标记置入列表包括多个代表所述多个文档的标识符，其中所述多个标识符中的一个标识符代表所述文档并包括有效负载值，所述有效负载值标识所述文档在所述树形结构中的完整路径，并且所述有效负载值包括由唯一地标记所述树形结构的每个同胞节点的方案提供的一组完整路径指示符。
4.如权利要求3中所述的方法，还包括：
建立多个计数器的分层结构，每个计数器与所述树形结构的所述多个节点中的一个节点关联，其中通过所述一组完整路径指示符对所述多个计数器中的一个计数器进行索引；
以及
更新存储在所述计数器中的值，所述值指示对所述多个文档中的一个或多个文档的计数，通过类别的子类别或由所述多个约束中的一个约束指示的子类别来对所述一个或多个文档进行分类。
5.如权利要求3中所述的方法，其中所述方案是杜威标记方案。
6.如权利要求1中所述的方法，还包括：
由所述信息检索系统接收包括在所述查询中的算术表达式，所述算术表达式与包括在所述多个文档中的一个或多个文档内的至少一个数字字段关联；以及
计算所述算术表达式的值，对所述多个约束中的一个约束指示的类别的每个子类别执行所述计算。
7.如权利要求6中所述的方法，其中所述算术表达式包括聚合函数和基本公式中的至少一个，
其中所述聚合函数包括和、积、最大值、最小值和平均值中的至少一个，以及其中所述基本公式包括一个或多个数字字段、一个或多个数字常数、一个或多个算术算子，以及指示带括号表达式的括号的任何组合。
8.如权利要求1中所述的方法，其中所述构建所述倒排索引包括：
对于所述多个文档中的每个文档，指定所述多个唯一索引标记中的一组一个或多个索引标记作为一组一个或多个精确标记，每个精确标记指示对所述多个文档中的一个或多个文档进行分类的最终子类别，其中由所述最终子类别分类的每个文档不会由所述最终子类别的下级子类别进行分类；以及
通过使用所述一组一个或多个精确标记的所述查询，将所述文档标识为位于所述最终子类别中，但不在所述最终子类别的任何下级子类别中。
9.一种用于在计算环境中查询多方面信息的信息检索系统，所述系统包括：
用于由所述信息检索系统构建倒排索引的装置，所述倒排索引具有多个以一一对应关系与多个置入列表关联的唯一索引标记，每个置入列表包括多个文档中的一个或多个文档，其中所述多个唯一索引标记中的索引标记是以下两者之一：作为注释包括在所述多个文档中的一个文档内的方面标记，以及所述方面标记的路径前缀，其中所述注释指示树形结构中的路径，所述树形结构代表包括所述文档的方面，所述树形结构包括多个节点，所述节点代表对所述文档进行分类的类别和一个或多个子类别；
用于由所述信息检索系统接收包括针对所述多个文档的多个约束的查询的装置，所述多个约束与所述多个唯一索引标记中的多个索引标记以及对应于所述多个索引标记的多个置入列表关联；以及
用于由所述信息检索系统执行所述查询的装置，所述用于执行的装置包括：
用于利用所述多个约束和所述倒排索引来标识所述多个置入列表的装置，以及用于求所述多个置入列表的交集以获得所述查询的结果的装置。
10.如权利要求9中所述的系统，其中所述多个约束包括一个或多个方面约束以及一个或多个自由文本约束，并且其中所述用于标识所述多个置入列表的装置包括：
用于通过所述倒排索引标识第一组以一一对应关系与所述一个或多个方面约束关联的一个或多个索引标记以及第二组以一一对应关系与所述一个或多个自由文本约束关联的一个或多个索引标记的装置，所述第一组和所述第二组一个或多个索引标记包括在所述多个唯一索引标记中；以及
用于通过所述倒排索引标识第一组一个或多个置入列表和第二组一个或多个置入列表的装置，所述第一组的所述一个或多个置入列表以一一对应关系与所述第一组的所述一个或多个索引标记关联，并且所述第二组的所述一个或多个置入列表以一一对应关系与所述第二组的所述一个或多个索引标记关联。
11.如权利要求9中所述的系统，其中所述用于构建所述倒排索引的装置包括：
用于通过所述倒排索引生成完整路径标记及与其关联的完整路径标记置入列表的装置，所述完整路径标记置入列表包括多个代表所述多个文档的标识符，其中所述多个标识符中的一个标识符代表所述文档并包括有效负载值，所述有效负载值标识所述文档在所述树形结构中的完整路径，并且所述有效负载值包括由唯一地标记所述树形结构的每个同胞节点的方案提供的一组完整路径指示符。
12.如权利要求11中所述的系统，还包括：
用于建立多个计数器的分层结构的装置，每个计数器与所述树形结构的所述多个节点中的一个节点关联，其中通过所述一组完整路径指示符对所述多个计数器中的一个计数器进行索引；以及
用于更新存储在所述计数器中的值的装置，所述值指示对所述多个文档中的一个或多个文档的计数，通过类别的子类别或由所述多个约束中的一个约束指示的子类别来对所述一个或多个文档进行分类。
13.如权利要求11中所述的系统，其中所述方案是杜威标记方案。
14.如权利要求9中所述的系统，还包括：
用于由所述信息检索系统接收包括在所述查询中的算术表达式的装置，所述算术表达式与包括在所述多个文档中的一个或多个文档内的至少一个数字字段关联；以及用于计算所述算术表达式的值的装置，对所述多个约束中的一个约束指示的类别的每个子类别执行所述计算。
15.如权利要求14中所述的系统，其中所述算术表达式包括聚合函数和基本公式中的至少一个，
其中所述聚合函数包括和、积、最大值、最小值和平均值中的至少一个，以及其中所述基本公式包括一个或多个数字字段、一个或多个数字常数、一个或多个算术算子，以及指示带括号表达式的一组或多组括号的任何组合。
16.如权利要求9中所述的系统，其中所述用于构建所述倒排索引的装置包括：
用于对于所述多个文档中的每个文档，指定所述多个唯一索引标记中的一组一个或多个索引标记作为一组一个或多个精确标记的装置，每个精确标记指示对所述多个文档中的一个或多个文档进行分类的最终子类别，其中由所述最终子类别分类的每个文档不会由所述最终子类别的下级子类别进行分类；以及
用于通过使用所述一组一个或多个精确标记的所述查询，将所述文档标识为位于所述最终子类别中，但不在所述最终子类别的任何下级子类别中的装置。

查询多方面信息的方法和系统\n技术领域\n[0001] 本发明涉及用于在信息检索系统中搜索由倒排文本索引编码的多方面信息的方法和系统。\n背景技术\n[0002] 传统的信息检索(IR)系统将自由文本搜索与上下文导航相结合以增强用户体验。例如，销售产品的网站提供了关键字搜索接口来搜索与销售的产品关联的文档数据库，并且所述接口结合了浏览菜单以允许用户到达产品的若干级的类别。响应于用户发出搜索数据库的关键字查询，信息检索系统向用户呈现一组相关文档以作为该查询的结果，并且还改变导航菜单以显示给定查询的最相关方面。需要改进这些公知的信息检索系统呈现关键字搜索结果并更新上下文导航菜单的速度。此外，将自由文本搜索与上下文导航相结合所需的开发工作是巨大的。因此，需要克服相关技术的之前缺陷和限制中的至少一个。\n发明内容\n[0003] 本发明提供了一种在信息检索系统中查询多方面信息的计算机实现的方法，所述方法包括：\n[0004] 由所述信息检索(IR)系统构建倒排索引，所述倒排索引具有多个以一一对应关系与多个置入列表(posting list)关联的唯一索引标记，每个置入列表包括多个文档中的一个或多个文档，其中所述多个唯一索引标记中的索引标记是以下两者之一：作为注释包括在所述多个文档中的一个文档内的方面标记，以及所述方面标记的路径前缀，其中所述注释指示树形结构中代表包括所述文档的方面的路径，所述树形结构包括多个节点，所述节点代表对所述文档进行分类的类别和一个或多个子类别；\n[0005] 由所述信息检索系统接收包括针对所述多个文档的多个约束的查询，所述多个约束与所述多个唯一索引标记中的多个索引标记以及对应于所述多个索引标记的多个置入列表关联；以及\n[0006] 由所述信息检索系统执行所述查询，所述执行包括：\n[0007] 利用所述多个约束和所述倒排索引来标识所述多个置入列表，以\n[0008] 及\n[0009] 求所述多个置入列表的交集以获得所述查询的结果。\n[0010] 还在本文中说明和要求保护与以上概述的方法对应的系统和计算机程序产品。\n[0011] 有利地，本发明提供了高效地将方面信息编码到倒排索引中的可伸缩技术。此外，本发明提供了高效地对结合自由文本约束和导航约束的查询求值的运行时算法，由此更快地返回查询结果。此外，所公开的运行时算法是健壮的，即使索引的文档可能被不一致地分类。\n附图说明\n[0012] 图1是根据本发明的实施例的在信息检索系统中查询由倒排文本索引编码的多方面信息的系统的方块图；\n[0013] 图2是根据本发明的实施例的可以由图1的系统搜索的多方面信息的实例；\n[0014] 图3示出了根据本发明的实施例的入站文档到要由图1的系统使用的树形结构的映射；\n[0015] 图4A是根据本发明的实施例的要由图1的系统搜索的多方面文档的分类的实例；\n[0016] 图4B示出了根据本发明的实施例的与图4A的分类关联的倒排索引；\n[0017] 图4C示出了根据本发明的实施例的图4A的分类的特殊方面标记和置入列表；\n[0018] 图5示出了根据本发明的实施例的在图4A的分类中对每个文档的完整路径进行编码的分类和标记方案；\n[0019] 图6是根据本发明的实施例的与图5的分类和标记方案对应的计数器的分层结构；\n[0020] 图7是根据本发明的实施例在图1的系统中执行搜索查询的过程；以及[0021] 图8是根据本发明的实施例的实现图7的算法的计算系统。\n具体实施方式\n[0022] 概述\n[0023] 本发明提供了向信息检索系统添加多方面导航能力的可伸缩解决方案。本文公开的解决方案包括用于对多方面信息进行编码的倒排索引，以及高效地对结合导航约束和自由文本谓语(即，关键字)的查询求值的运行时算法。此外，本发明提供了高效地对查询约束中指定的类别的子类别内包括的文档数进行计数的技术。此外，本文还公开了计算与此类子类别相关的聚合函数的技术。\n[0024] 查询多方面信息的系统\n[0025] 图1是根据本发明的实施例的在信息检索系统中查询由倒排文本索引编码的多方面信息的系统的方块图。信息检索系统100(也称为多方面搜索系统)包括接收搜索查询104的搜索引擎102。搜索引擎102接收入站文档106，文档106将方面标记作为注释包括在每个文档的文本中。此外，搜索引擎102使用方面标记来建立将方面信息与置入列表关联的倒排索引108。每个置入列表包括一组入站文档106中的一个或多个文档(也称为资格文档)。此外，搜索引擎102通过在倒排索引108中求置入列表的交集来执行查询104以确定查询结果110。\n[0026] 图2是根据本发明的实施例的可以由图1的系统搜索的多方面信息的实例。如在此使用的，将方面定义为具有有向非循环图(DAG)或树形结构的分层结构或分类，它们通过类别和一个或多个子类别对项目进行分类。多方面搜索系统的用户通过向下扩展方面的类别和子类别来对搜索空间进行导航。多方面信息200包括通过类型202、语言204和标题206对电影进行分类的三个方面。类型类别之下的子类别包括戏剧、爱情剧、喜剧和动作片。每个这些类型的子类别都存在其他级别的子类别。例如，戏剧的子类别包括犯罪片、战争片和爱情片。\n[0027] 使用图2的各方面中组织的多方面影片信息，针对任何语言的影片执行示例性数据库搜索。以下示出了针对此搜索的图形向下扩展：\n[0028] 类型\n[0029] →故事片\n[0030] 犯罪片(200)\n[0031] 战争片(200)\n[0032] 爱情片(100)\n[0033] →语言\n[0034] 英语(400)\n[0035] 法语(100)\n[0036] 将搜索结果显示为包括英语或法语故事片的电影的标题列表(例如，The Godfather，由Marlon Brando和Al Pacino主演；The Great Escape，由Steve McQueen主演；Scarface，由Al Pacino主演；The FrenchConnection，由Gene Hackman主演；\nBreathless，由Jean-Paul Belmondo主演，等等)。括号内的数字指示在每个故事片子类别以及在每个语言子类别中符合条件的影片数(即，计数)。例如，犯罪片之后的(200)指示数据库中有200部犯罪片。括号中的这些数字指引用户进一步向下扩展。\n[0037] 继续该实例，显示了现在将搜索限于故事片类型中的英语电影的第二向下扩展：\n[0038] 类型\n[0039] →故事片\n[0040] 犯罪片(100)\n[0041] 战争片(50)\n[0042] 爱情片(50)\n[0043] 语言\n[0044] →英语(200)\n[0045] 在此第二向下扩展中，示出的故事片的计数从第一向下扩展下降，因为仅考虑了英语故事片。另外，同样通过排除法语故事片缩短了搜索结果列表(例如，The Godfather，由Marlon Brando和Al Pacino主演；The GreatEscape，由Steve McQueen主演；Scarface，由Al Pacino主演；The FrenchConnection，由Gene Hackman主演，等等)。\n[0046] 仍继续该实例，输入“Al Pacino”作为关键字搜索项，得到的向下扩展显示如下：\n[0047] 类型\n[0048] →故事片\n[0049] 犯罪片(10)\n[0050] 语言\n[0051] →英语(10)\n[0052] 在此情况下，搜索引擎确定战争片和爱情片的计数都为零，因此，不再将这两个子类别显示为向下扩展选择。在搜索结果列表中，仅显示了AlPacino主演的英语故事片(例如，The Godfather，由Marlon Brando和Al Pacino主演；以及Scarface，由Al Pacino主演)。\n[0053] 索引\n[0054] 图3示出了根据本发明的实施例的入站文档到要由图1的系统使用的树形结构的映射300。入站文档的类别和子类别的分层结构是树形结构的方面或在索引之前转换成树形结构的DAG结构的方面。例如，DAG 302包括与节点D关联的文档d1。在索引之前，将DAG 302转换为树形结构的方面3 04，其中文档d1与两个不同的节点D关联。在转换为方面3 04之后，倒排索引将路径A.B.D(而非路径A.C.D)视为在不同节点结束。\n[0055] 每个入站文档包括一个或多个方面标记。如在此使用的，将方面标记定义为指示方面的树形结构分类中路径的文档注释。在一个实施例中，将方面标记作为元数据插入使用通用标记语言(例如，可扩展标记语言(XML))的文档。在下文中，由术语“方面：”后跟路径指示符(例如，“方面：A.B.D”)来表示特定方面标记。对于本领域的技术人员显而易见的是，可以使用其他表示法来指示方面标记。方面标记所指示的路径通常以该方面的树形结构的叶节点结束，但是也可能以树形结构的内部节点结束。\n[0056] 图4A是根据本发明的实施例的要由图1的系统搜索的多方面文档的分类实例。分类400包括虚拟根节点401并且还包括两个方面402和404。方面402包括类别406(即，节点A)、子类别408、410、412(即，分别为节点B、C和D，它们是节点A的子类别)、子类别\n414(即，节点E，它是节点B的子类别)，以及子类别416(即，节点F，它是节点C的子类别)。\n方面402还包括文档418、420和422(即，分别为文档d1、d2和d3)。文档d1包括在子类别414和416中，文档d2包括在子类别408中，而文档d3包括在子类别416中。\n[0057] 方面404包括类别426(即，节点X)和节点X的子类别428和430(即，分别为节点Y和Z)。方面404还包括子类别428中的文档418和子类别430中的文档420。\n[0058] 应指出的是，可以将文档包括在多个方面中，并且可以包括在一个方面的多个路径中。例如，将文档d1包括在方面4 02的路径A.B.E和A.C.F以及方面404的路径X.Y中。要指示其包括在路径A.B.E、A.C.F和X.Y中，文档d1包括以下方面标记：方面：A.B.E、方面：A.C.E和方面：X.Y。\n[0059] 倒排索引由多方面搜索系统100(参见图1)构建并由搜索查询用于查找与包括在所述倒排索引中的一个或多个索引标记匹配的文档。索引标记是文档中的关键字或对元数据进行编码的任意字符串。倒排索引将每个索引标记与置入列表关联，置入列表是符合条件的文档(例如，一个或多个包括索引标记作为方面标记的文档)的一个或多个标识符的列表。例如，倒排索引将索引标记x与包括文档d1、d2及d5的第一置入列表关联并将索引标记y与包括文档d5及d9的第二置入列表关联。要针对索引标记“x、y”执行搜索查询，则求与x和y关联的置入列表的交集以生成d5作为查询结果。该结果指示文档d5同时包括索引标记“x”和索引标记“y”。\n[0060] 在一个实施例中，倒排索引中的置入列表内的每个项都包括可选的有效负载，其中可以存储有关文档的其他信息。在下文中，方括号(即，[])指示有效负载。例如，0.1.0是d3[0.1.0]中的有效负载。\n[0061] 返回上述有关图2的电影数据库搜索实例，可以由包括方面标记交集的查询提供任何语言的故事片电影标题的搜索。作为一个实例，该查询可以具有以下语法：\n[0062] 方面：类型.故事片 “与” 方面：语言\n[0063] 同样，可以由以下查询提供Al Pacino主演的英语犯罪片的电影标题的上述搜索：\n[0064] 方面：类型.故事片.犯罪“与”方面：语言.英语“与”“al pacino”每个索引标记“方面：类型.故事片.犯罪”和“方面：语言.英语”与倒排索引中的置入列表关联。\n倒排索引还包括关键字“al pacino”的置入列表。要执行此查询，求与“方面：类型.故事片.犯罪”、“方面：语言.英语”和“al pacino”关联的置入列表的交集以便确定查询结果。\n[0065] 在一个实施例中，查询语法还包括返回子类别路径名称及其计数的函数(例如，获得计数)。所返回的子类别路径名称是由查询中的方面限制所指定的类别或子类别下的每个子类别的名称。例如，可以执行以下查询以返回“类型.故事片”子类别下的子类别名称和计数(参见图2)，以及返回“语言”类别下的子类别名称和计数(参见图2)：\n[0066] 方面：类型.故事片“与”方面：语言，获得计数(*)\n[0067] 使用与图2相关的上述图形向下扩展中显示的计数，该样例查询返回类型.故事片.{犯罪片(200)，战争片(200)，爱情片(100)}以及语言.{英语(400)，法语(100)}。在*\n以上示出的示例性语法中，获得计数()指示所述计数基于查询的方面限制(即，“方面：类型.故事片”和“方面：语言”)。\n[0068] 应指出的是，包括在查询中的计数函数可以使用与查询的方面限制不同的方面限制。例如，使用图5的分类，查询“方面：A“与”方面：X，获得计数(方面：A.B)”将返回与方面A.B相关(而不是与A和X相关)的候选文档的子类别名称和计数。在下文中根据图\n5和6更详细地说明了计数的确定。\n[0069] 图4B示出了与图4A的分类关联的倒排索引450。倒排索引450由多方面搜索系统100(参见图1)构建并包括具有一一对应关系的索引标记452和置入列表454。每个索引标记或者是包括在文档中的方面标记(所述文档包括在关联的置入列表中)，或者是源自方面标记指示的路径的唯一前缀的方面标记。作为一个实例，图4A中的文档d1位于路径A.B.E中并包括方面标记“方面：A.B.E”。在该实例的倒排索引中，d1在与索引标记“方面：A.B.E”(即，是包括在d1中的方面标记的索引标记)关联的置入列表中，以及在与索引标记“方面：A”和“方面：A.B”(即，源自路径A.B.E的唯一前缀)关联的置入列表中。注意，虽然d1也包括在路径A.C.F中，后者也具有路径前缀A，但是索引标记“方面：A”在倒排索引中仅出现一次，以保持索引标记列表中的表项的唯一性。\n[0070] 当执行查询时，搜索引擎102(参见图1)使用倒排索引来查找构成查询结果的一个或多个符合条件的文档。作为与图4B相关的实例，为了查找符合查询“方面：A.B‘与’方面：X.Y”的条件的文档，求置入列表[d1，d2]与[d1]的交集以提供文档d1的查询结果。\n[0071] 入站文档可能包括脏数据(例如，文档分类的不一致性)。例如，图4A中的文档d1归类于路径A.B.E和A.C.F之下。这些路径可以代表两个相互排斥的类别。本文描述的方法对此类不一致性是健壮的。\n[0072] 图4C示出了根据本发明的实施例的图4A的分类的特殊方面标记和置入列表。在一个实施例中，由搜索引擎构建的倒排索引包括最终类别部分470，后者以一一对应关系将特殊方面标记(也称为特殊精确标记)47 2与置入列表关联。对于每个文档，倒排索引的最终类别部分包括指示文档所属的任何路径的最终类别或子类别的特殊方面标记(多个)。\n此最终类别/子类别索引允许查询“精确地”位于类别或子类别中的文档(即，属于类别或子类别，但是不属于所述类别或子类别的任何下级)。\n[0073] 特殊精确标记472指示图4A的分类的类别和/或子类别。在图4C的实例中，特殊精确标记“方面：A.B”与包括文档d2的置入列表关联，由此指示d2精确地位于节点B子类别中(参见图4A中的方面402)且不位于由节点B的子节点表示的子类别中(即，不位于节点E子类别中)。\n[0074] 确定符合条件的文档的计数\n[0075] 图5示出了根据本发明的实施例的对与图4A的分类中每个文档关联的所有完整路径进行编码的分类和标记方案。分类500包括施加于图4A的分类400的简明标记方案(例如，杜威标记方案)。有关图5中示出的节点和文档401-430的说明，请参考上文与图\n4A相关的说明。根据分类500的每个父节点，将唯一标识符(例如，来自从0开始的一系列整数)分配到每个同胞节点。在图5中，使用杜威标记方案将0和1分别分配给同胞节点A和X。此外，将0、1和2分别分配给图5中的同胞节点B、C和D，并将0和1分别分配给同胞节点Y和Z。此外，所述标记方案将0分配给图5中没有同胞的子节点(例如，节点E和F)。将完整路径(例如，字符串“fullpath”)添加到倒排索引并且将其与包括代表所有可以由搜索引擎102(参见图1)搜索的文档的标识符的置入列表相关联。每个代表完整路径标记置入列表中的文档的标识符包括有效负载值，所述有效负载值使用来自标记方案的指示该文档的所有完整路径的指示符。例如，分类500的完整路径标记和关联的置入列表是：\n[0076] fullpath d1[0.0.0，0.1.0，1.0]，d2[0.0，1.1]，d3[0.1.0]上述完整路径标记和置入列表示出了文档d1包括在完整路径A.B.E、A.C.F，以及X.Y中，所述路径分别对应于有效负载值0.0.0、0.1.0以及1.0；文档d2包括在完整路径A.B和X.Z中，所述路径分别对应于有效负载值0.0和1.1；文档d3包括在完整路径A.C.F中，所述路径对应于有效负载值0.1.0。对本领域的技术人员显而易见的是，还可以使用其他基于非杜威标记方案的编码。\n[0077] 图6是根据本发明的实施例的对应于图5的分类和标记方案的计数器分层结构。\n计数器分层结构600由多方面搜索系统100(参见图1)构建以包括对应于图5的根节点\n401的根节点601，以及在分别与类别或子类别节点406、408、410、412、414、416、426、428和\n430(参见图5)对应的节点606、608、610、612、614、616、626、628及630处的计数器。由标记方案(参见图5)提供的值对图6中的每个计数器进行索引，其中该值是图5中计数器的对应节点的完整路径的编码。例如，由杜威编码0.1.0对节点616的计数器F[]进行索引并将其与图5中的分类500的完整路径A.C.F关联。\n[0078] 分层结构600中的计数器由多方面搜索系统100(参见图1)用于跟踪与用作搜索查询中约束的类别(或子类别)的每个子类别关联的符合条件文档的计数。例如，图6中的完整路径A.C.F下的符合条件文档与杜威编码0.1.0关联。确定编码0.1.0的每个前缀且递增与每个前缀关联的计数器。在此实例中，确定的第一前缀0.1.0是编码中最左侧的\n0，它对应于分类600中的部分路径A。然后递增计数器606(即，对应于部分路径A的计数器)。从0.1.0确定的第二前缀为0.1，它对应于部分路径A.C，并且递增计数器610。最终，确定了完整前缀0.1.0且递增与完整路径A.C.F对应的计数器616。\n[0079] 为了支持导航操作，本发明的实施例提供了其他计数。在一个实施例中，查询API指定查询的计数函数(例如，获得计数)是局部地(即，仅下级)还是全局地(即，整个子树)计数。此指定局部还是全局模式有助于找到整个树中对于给定查询具有更高计数的节点。在执行查询之后，可以将用户的导航位置置于与该查询最相关(即，具有更高的计数)的节点处。例如，将图4A和方面：A的分类用作“获得计数”函数的输入，所述函数在“获得计数”处于全局模式时返回A.B、A.C、A.D、A.B.E和A.C.F的计数，并在“获得计数”处于局部模式时仅返回A.B、A.C和A.D的计数。\n[0080] 查询执行算法\n[0081] 图7示出了根据本发明的实施例的在图1的系统中执行搜索查询的运行时算法。\n虽然该查询执行算法使用了杜威编码，但是对于本领域的技术人员显而易见的是，还可以使用其他基于非杜威标记方案的编码。在图7的查询执行算法开始之前，由多方面搜索系统100(参见图1)接收入站文档并且如上所述构建倒排索引。查询执行算法始于在步骤700接收搜索查询。所述搜索查询包括包含一个或多个方面限制(也称为约束)F1、F2、......、Fn的输入702。输入702可选地包括自由文本(也称为关键字)限制T和/或一个或多个计数器方面限制C1、C2、......、Cm。\n[0082] 在步骤704，使用倒排索引来标识与T及F1、F2、......、Fn关联的置入列表。求这些标识的置入列表的交集以确定一个或多个符合条件文档的列表。在步骤706，使用完整路径标记来查找杜威编码E1、E2、......、Ek以寻找在步骤704中确定的每个符合条件的文档。对于每个编码Ei，Ei中的杜威数位在步骤708中用于递增与C1、C2、......、Cm指示的类别和/或子类别的子类别相关联的计数器。在步骤710，返回(例如，显示)符合条件的文档以及C1、C2、......、Cm的每个子类别中符合条件的文档计数和C1、C2、......、Cm的那些子类别的名称。查询执行算法在步骤712结束。\n[0083] 查询执行实例\n[0084] 作为应用图7的查询执行算法的实例，将分类500(参见图5)和以下查询视为输入702：\n[0085] 方面：A.B“与”方面：X，获得计数(*)\n[0086] 在此实例中，通过步骤704中求方面标记交集而找到的符合条件的文档为文档d1和d2(即，图5的文档418和420)。步骤706确定匹配查询中方面限制的d1和d2的杜威编码为d1[0.0.0，1.0]和d2[0.0，1.1]。对于d1，步骤7 08递增与0.0，0.0.0，1及1.0(即，分别为路径A.B、A.B.E、X和X.Y)关联的计数器。对于d2，步骤708递增与0.0，1和1.1(即，分别为路径A.B，X和X.Z)关联的计数器。最终，步骤710返回符合条件的文档d1和d2，以及A.B和X的子类别以及这些子类别中符合条件的文档的计数。例如，将子类别和计数表示为A.B{E(1)}X{Y(1)，Z(1)}，其中子类别在大括号(即，“{}”)中列出，并且每个计数在紧随其关联的子类别的括号中。\n[0087] 聚合函数\n[0088] 在一个实施例中，向包括在查询语法中的上述计数函数(例如，获得计数)补充了提供方面数据聚合的更通用的函数，其中聚合比对属于特定类别的子类别的记录或文档的简单计数更复杂。在特定方面搜索应用(如商业智能(BI)应用)中需要此类聚合且有助于导航到方面的子类别。\n[0089] 在特定数据集合(例如，企业数据)中，每个文档都具有一个或多个与其关联的数字字段且所述字段在搜索引擎102中索引(参见图1)。方面查询104(参见图1)包括自由文本部分和类别约束，以及一组要求子计数(即，所述组中每个类别的所有子类别的计数，如以上与图5及6相关的说明)的类别。在每个类别需要子计数的情况下，本发明关联数字字段(与索引文档关联)上的一个或多个算术表达式。搜索引擎102(参见图1)计算并返回每个子类别的算术表达式(多个)，此外还计算匹配文档的数量。每个算术表达式可以包含聚合函数(例如，和、积、平均值、最大值或最小值)和/或基本公式(例如，数字字段和/或数字常数、加、减、乘和/或除运算符，以及括号的任何组合)。算术表达式的一个实例是AVG{contract_value-2*estimated_cost}。提供了接口，以便可以将算术表达式添加到查询104(参见图1)，并与搜索结果中的计数一起返回。\n[0090] 例如，假定“项目集合”中的每个文档具有两个与其关联的数值：contract_value和estimated_cost。此外，假定存在地理范围，并且选择了类别“US”(即，表示美国)且子类别是美国的50个州。如上所述，搜索引擎102(参见图1)计算每个州的项目数。在此实施例中，对于每个州，搜索引擎还使用聚合函数来针对该州中所有项目的值[contract_value-estimated_cost](即，期望利润)求和。此聚合指示每个子类别(即，每个州)的项目的期望利润，而非仅提供该州的项目计数。计算系统\n[0091] 图8是根据本发明的实施例的用于实现图7的算法的计算系统。计算单元800适于存储和/或执行多方面搜索系统814的程序代码，并且通常包括中央处理单元(CPU)802、存储器804、输入/输出(I/O)接口806、总线808、I/O设备810和存储单元812。CPU 802执行计算单元800的计算和控制功能。CPU 802可以包括单个处理单元，或分布于一个或多个位置(例如，在客户机和服务器上)中的一个或多个处理单元之间。\n[0092] 在实际执行多方面搜索系统814的程序代码期间使用了存储器804的本地存储元件。存储器804的高速缓冲存储器元件提供至少一些程序代码的临时存储，以便减少在执行期间必须从大容量存储装置检索代码的次数。此外，存储器804可以包括未在图8中示出的其他系统，例如，在CPU802上运行并提供对计算单元800内和/或连接到计算单元800的各种组件的控制的操作系统(例如，Linux)。存储器804可以包括任何已知类型的数据存储装置和/或传输介质，包括大容量存储装置、磁介质、光介质、随机存取存储器(RAM)、只读存储器(ROM)、数据高速缓存、数据对象等。存储单元812例如是存储数据的磁盘驱动器或光盘驱动器。此外，类似于CPU 802，存储器804可以位于单个物理位置，其中包括一个或多个类型的数据存储装置，或以各种形式分布于多个物理系统间。此外，存储器804可以包括分布于例如LAN、WAN或存储区域网络(SAN)(未示出)之间的数据。\n[0093] I/O接口806包括与外部源往返交换信息的任何系统。I/O设备810包括任何已知类型的外部设备，包括显示器、键盘、鼠标、打印机、扬声器、手持设备、传真机等。总线808提供计算单元800中每个组件之间的通信链路，并可以包括任何类型的传输链路，包括电、光、无线链路等。\n[0094] I/O接口806还允许计算单元800从辅助存储设备(例如，存储单元812)存储和检索信息(例如，程序指令或数据)。辅助存储设备可以是非易失性存储设备(例如，容纳CD-ROM盘的CD-ROM驱动器)。计算单元800可以从其他辅助存储设备(未示出)存储和检索信息，所述设备可以包括直接存取存储器(DASD)(例如，硬盘或软盘)、磁-光盘驱动器、磁带驱动器或无线通信设备。\n[0095] 本发明可以采取完全硬件实施例、完全软件实施例或同时包含硬件和软件元素的实施例的形式。在优选实施例中，本发明以软件来实现，所述软件包括但不限于固件、驻留软件、微码等。\n[0096] 此外，本发明可以采取可从计算机可用或计算机可读介质访问的计算机程序产品的形式，所述计算机可用或计算机可读介质提供了可以被计算单元800或任何指令执行系统使用或与计算单元800或任何指令执行系统结合的多方面搜索系统814的程序代码。出于此描述的目的，计算机可用或计算机可读介质可以是任何能够包含、存储、传送、传播或传输由指令执行系统、装置或设备使用或与所述指令执行系统、装置或设备结合的程序的装置。\n[0097] 所述介质可以是电、磁、光、电磁、红外线或半导体系统(或装置或设备)或传播介质。计算机可读介质的实例包括半导体或固态存储器、磁带、可移动计算机盘、RAM 804、ROM、硬磁盘和光盘。光盘的当前实例包括光盘-只读存储器(CD-ROM)、光盘-读/写(CR-R/W)和DVD。\n[0098] 通过实例的方式提供了在此示出的流程图。可以存在对在此说明的这些图或步骤(或操作)的变化而不偏离本发明的精神。例如，在特定情况下，可以通过不同的顺序执行步骤，或可以添加、删除或修改步骤。所有这些变化都被视为如所附权利要求中所述的本发明的一部分。\n[0099] 虽然在此出于示例目的说明了本发明的实施例，但是对于本领域的技术人员来说，许多修改和更改将是显而易见的。因此，所附权利要求旨在包括所有此类落入本发明的真正精神和范围内的修改和更改。