CN1568469A - 用于信息检索的分层数据驱动导航系统及方法 - Google Patents

Abstract

本发明涉及数据驱动的、分层信息导航系统和方法，允许按照特征化资料的某些共同的属性搜索文档集或其它资料。本发明包括采用这一导航模式的数据驱动的、分层导航系统的几个方面。本发明的导航系统包括界面特征、知识库和分类学定义过程和用于生成知识库的分类过程、基于图形的可导航数据结构和用于生成数据结构的方法，系统基于环球网的应用，以及实现该系统的方法。用户能根据选择用于属性的所需值来搜索或浏览特定文档集。数据驱动的、分层信息导航系统和方法通过将术语与资料关联、定义术语中的分层关系集以及提供术语间的指导搜索机构来启动这一导航模式。

Description

用于信息检索的分层数据驱动导航系统及方法

技术领域

本发明通常涉及信息导航系统和搜索引擎。

背景技术

随着增强的计算能力和网络体系结构允许集聚大量信息和对那种信息的广泛访问，从信息数据库的信息检索是愈加具有挑战性的问题，特别是在环球网(WWW)。信息检索过程的目的是允许识别用户感兴趣的资料。

随着用户可以检索的资料数量的增加，识别与搜索有关的资料变得日益重要，但也日益困难。由信息检索过程引起的挑战包括提供直观、灵活的用户界面以及在合理的时间量内精确地识别与用户需要有关的资料。信息检索过程包含两个相关的技术方面，即，信息组织和访问。

当前信息导航系统通常遵循三个范例的一个。一种信息导航系统采用数据库查询系统。在典型的数据库查询系统中，用户通过指定用于固定数据字段来制定结构化查询，以及该系统列举其数据字段包含那些值的文档。例如，PriceSCAN.com使用这种界面。通常，数据库查询系统为用户提供基于表格的界面，将表格输入转换成以正式数据库语言，诸如SQL的查询，然后在关系数据库管理系统上执行查询。典型的基于查询的系统的缺点包括它们允许用户进行不返回文档的查询以及它们提供仅导致另外的结果集(对应于用户搜索说明的文档)限制的查询修改选项，而不扩展或扩充结果集。

第二种信息导航系统是全文(free-text)搜索引擎。在典型的全文搜索引擎中，用户通常以布尔表达式的形式输入任意的文本串，以及系统通过列举包含匹配文本的文档来响应。例如Google.com包括全文搜索引擎。通常，全文搜索引擎向用户提供搜索表格，通常是单行，以及使用预计算过的索引处理查询。通常这一索引将每个文档与包含在那个文档中的大部分字关联，而不独立地考虑文档的内容。因此，结果集通常是混合相关和不相关文档的大量、无组织列表。尽管已经开发出试图确定用户查询的目的并提供结果的相关等级或者缩小或组织结果集的变形，但这些系统在实现这些目的方面是有限制的并且不可靠。

第三种信息导航系统是基于树的目录。在基于树的目录中，用户通常以树的根节点开始并通过相继地选择通向树中的其他节点的细化分支来指定查询。例如，Shopping.yahoo.com使用基于树的目录。在典型的实现中，将硬编码树(hard-coded tree)存储在数据结构中，以及相同或另一数据结构将文档映射到他们所处的树的节点或多个节点。特定的文档通常通过树，从仅一条或至少几个路径访问。导航状态的集合是相对静止的-虽然通常将文档增加到目录中的节点上，目录的结构通常保持相同。在纯基于树的目录中，将目录节点排列成所有用户都从其开始的单个根节点，以及经用户从根节点选择的分支的独特序列仅能到达的每个其他的目录节点(directorynode)。这种目录强加树的分支必须是导航不相交的限制-即使分配给不相交分支的文档的方式对用户来说不直观。可以通过增加另外的链接以便将树转换成非循环有向图来解决这一刻板性。更新目录结构仍然是困难的任务，而且叶节点特别倾向于以大量相应的文档告终。

在所有这些类型的导航系统中，对用户在浏览其结果集后有效地修改查询是很困难的。在数据库查询系统中，用户可以增加项或从查询去除项，但对用户来说避免指定太少查询(即，太多结果)或指定太多查询(即，无结果)通常很困难。在全文搜索引擎中，出现相同的问题。在基于树的目录中，对用户来说，唯一修改查询的方法是通过选择分支来缩小它或通过退回到在前分支来概括它。

用于信息检索的各种其他系统也是可用的。例如，Danish et al.的美国专利No.5,715,444和5,983,219，均名为“Method andSystme for Executing a Guided Parametric Search”公开了用于从一系列项识别单个项的界面。该界面向用户提供存在于一系列项中的特征的一组列表并识别满足所选定的特性的项。

发明内容

本发明的分层数据驱动信息导航系统和方法使用与那些资料有关的某些共同的属性，启动文档集或其他资料的导航。该导航系统界面允许用户选择用于与当前导航状态中的资料相关的属性值并返回对应于用户选择的资料。本发明通过将项(属性值对)与文档关联、定义项中的分层细化关系集(即，偏序)，以及基于项与文档的关联以及项中的关系，提供导向导航机制来启动这一导航模式。

本发明包括与分层数据驱动导航系统有关的几个部分和特性。在这些中为用户界面、知识库、用于生成和维护知识库的方法、可导航的数据结构和用于生成数据结构的方法、基于WWW的系统应用，以及实现该系统的方法。尽管在此主要参考用于导航产品数据库的基于WWW的系统来描述本发明，应当理解到能在任何数据库上下文中采用类似的导航系统，其中资料可以与术语相关并且用户能通过那些术语识别感兴趣的资料。

本发明使用有关资料集的信息知识库来设计界面并采用该界面来通过提供相关的导航选项引导用户通过导航状态集。知识库包括列举与资料有关的属性、用于每个属性的值范围以及与术语(属性值对)有关的偏序的表示。用于与娱乐有关的资料的属性值对可以是例如product：Movie和Director.Spike Lee。(在本说明书中，这一属性中表示属性值对：Value格式；导航状态表示为属性值对的相对集)。知识库还包括将资料集中的每个项与特征化那个项的术语集关联的分类映象。

知识库通常是按域组织的，域是符合自然分组的资料集。最好，选择域以便易处理的多个属性足以有效地区分以及在那个域的资料中导航。知识库最好包括每个域的特性，其可以包括涉及那个域中的文档的分类的规则或缺省期望。特定项可以在不止一个域中。

本发明包括用于导航的用户界面。用户界面最好将用户导航状态呈现为按属性组织的一组术语。对指定的术语集，用户界面显示与那些术语有关的资料并显示用于缩小或概括导航状态的相关导航选项。在本发明的一个方面中，用户通过选择和取消选定术语来在资料集中导航。

在本发明的一个方面中，用户界面立即响应选择或取消选定术语，而不等待用户指示和提交由多个术语组成的复杂查询。只要已经执行查询，用户可以通过选择另外的术语或通过细化现有的术语来缩小导航状态(navigation state)。另外，用户可以通过取消选定已经选择过的术语或通过概括术语来扩大导航状态。在优选实施例中，用户可以通过以不同于选择它们的顺序取消选定术语来扩大导航状态。例如，用户可能以{products：Movies}开始，通过选择另外的术语缩小到{product：Movies；Genre：Drama}，再次缩小到{product：Movies；Genre：Drama；Director：Spike Lee}，然后通过取消选定术语来概括到{product：Movies；Director：Spike Lee}。

在本发明的另一方面中，用户界面允许用户使用全文搜索来查找感兴趣的术语。在本发明的另一方面中，用户界面还允许用户在与资料有关的描述信息上使用全文搜索。

在本发明的另一方面中，用户界面向用户显示用于缩小导航状态的上下文相关的导航选项。用户界面不向用户显示其选择没有对应于最终导航状态中的文档的术语。用户界面仅向用户显示与当前导航状态中的至少一个项关联的术语。同时，当它们变得相关时，用户界面显示新的导航选项。知识库可以包含确定特定属性或术语何时变得可用于用户以便导航的规则。

在本发明的另一方面中，例如，当资料对应于可用于从各个源购买的产品时，知识库包括已经从资料聚集的标准表示的目录。

在本发明的另一方面中，知识库可以包括库定义、组成同时可搜索的资料集。库可以包括来自一个或多个域的文档。可以将项指定给不止一个库。知识库可以包括定制用于特定库的导航的规则。

在本发明的另一方面中，通过多级、重复过程来开发知识库。工作流管理分配资源以便最小化生成和维护知识库的效率。

使用知识库来通过资料集生成支持导航的数据结构。在本发明的一方面中，导航系统由将术语集映射到与那些术语相关的资料集的导航状态的分层(即偏序)组成。在本发明的另一方面中，通过对应于从一个导航状态缩小到另一个的术语的转变，关联导航状态。可以预先全部或部分计算，或在运行时整个计算导航状态。

附图说明

从下述说明和附图，将更全面地理解本发明，包括那些和其他特征，其中：

图1是根据本发明的实施例的导航系统的用户界面的视图。

图2是图1的用户界面的视图，表示导航术语的下拉选择列表。

图3是图1的用户界面的视图，表示导航状态。

图4是图1的用户界面的视图，表示导航状态。

图5是图1的用户界面的视图，表示导航状态。

图6是图1的用户界面的视图，表示导航状态。

图7是图1的用户界面的视图，表示导航状态。

图8是图1的用户界面的视图，表示导航状态。

图9是图1的用户界面的视图，表示用于术语的全文搜索的结果。

图10是图1的用户界面的视图，表示有关特定文档的信息。

图11A-11C是根据本发明的实施例，如何能部分排序属性值范围的代表性例子。

图12是用于根据本发明的实施例，选择和分类文档的过程的框图。

图13是示例说明根据本发明的实施例，如何分类文档集的表。

图14是根据本发明的实施例，导航状态的代表性偏序(partialorder)。

图15是根据本发明的实施例，用于预计算导航状态的过程的框图。

具体实施方式

用户界面

根据本发明的一个实施例，图1表示分层、数据驱动导航系统的用户界面10。导航系统在知识库中定义的文档集上操作。如所示，最好向用户提供使用导航系统的至少两种备选方法：(1)通过选择术语来在文档集中导航，或(2)通过在搜索框中输入所需关键词。

导航系统最好按域组织文档。根据本发明的一个实施例，如图1-10所示的用户界面10在为葡萄酒域的一部分的文档集上操作。最好，域定义反映自然分组的一部分文档集。通常，用来分类域中的文档的属性集将是用来分类整个文档集的易处理的属性子集。域定义可以是产品类型，例如，酒或消费者电子设备。可以将域分成子域以便进一步组织文档集。例如，能分成电视的子域、立体声设备等等的消费者电子设备域。文档可以对应于产品或服务。

用户界面可以允许用户每次在一个域中导航。另外，用户界面可以允许同时导航多个域，特别是当某些属性对多个域是通用时。

用户界面允许用户在导航状态集中导航。每个状态由一组术语和与那些术语有关的文档集组成。用户通过选择和取消选定术语来在导航状态集中导航以便获得对应于每个选定术语集的导航状态。最好，如图4中，用户界面10显示通过显示术语52的列表50的导航状态和对应于那个状态的一些或全部文档42的列表41。最好，用户界面显示按属性组织的导航状态的术语52。最好，初始导航状态是对应于无术语选择，因此，对应于集合中的所有文档的根状态。

如图2所示，用户界面10允许用户通过选择用于属性22的值28，或通过用更具体的一个(如果适当的话)代替当前所选定的值来缩小导航状态。最好，用户界面10向用户呈现可用于缩小当前导航状态的选项，最好具有按属性组织的相关术语。在本发明的一些实施例中，如图2所示，用户能从用在当前导航状态中按属性22组织的指示符24所表示的下拉列表26选择值28。用户界面10可以以各种格式显示这些导航选项。例如，值能呈现为图形或符号而非文本。界面可以考虑到选择项的任一方法，例如，鼠标点击、击键、或语音命令。可以通过各种媒介和设备，诸如电视或WWW，或电话或无线设备提供界面。尽管在此主要论述为可视界面，界面可以包括音频部分或主要是基于音频的。

最好，在当前导航状态下，用户界面仅显示将导致具有最小一个文档的导航状态的用于缩小导航状态的选项。用于提供导航选项的这一最佳标准确保无“僵局”，或无对应于空结果集的导航状态。

最好，用户界面可以显示用于缩小导航状态的选项，如果它们导致具有确实比当前更少的文档的导航状态的话。这样做以确保用户界面不必向用户显示在当前导航状态中已经通过术语暗示过的选择。

最好，用户一选择术语28来缩小当前导航状态，用户界面就显示新导航状态，而没有由用户的任何另外的触发动作。因为系统通过立即反馈响应每个用户，用户不需要制定全面的查询，然后提交查询。

根据本发明的一个实施例，如图3和4所示，用户界面10可以通过允许用户从所选定的术语的列表50去除术语52来扩大当前导航状态。例如，界面10可以通过用于去除选择的复选框54和按钮56提供列表50以便触发新选择。在所示的实施例中，用户可以按任何顺序去除所选定的术语52并能一次去除不至一个选择52。

最好，显示给用户的导航选项是上下文相关的。例如，细化在前选定的术语的术语可以变为最终导航状态中的导航选项。例如，参考图5，在选择术语Flavors：Wood and Nut Flavors52后(用户已经选定属性Flavors的值Wood和Nut Flavors23)，Wood和NutFlavors23则出现在属性列表20中的新导航状态的界面中并允许选择与那个特定属性有关的值以便进一步细化查询。用户界面也可以显示最初未显示的某些属性，当它们变为新相关时。例如，将图3与图2相比，仅在用户已经选择在前导航状态中的术语Region：FrenchRegion后，属性French Vineyards25才出现在属性的列表20中。用这种方式，可以将属性嵌入成所需的多个等级。当那些属性变得相关时，将属性显示为导航选项避免在那些选项变得有意义之前，由于导航选项使用户不知所措。

另外，对一些属性22，可以应用多个无比(非细化)选择值28。例如，对属性Flavor，值Fruity和Nutty，它们的没有任一个细化另一个，可以被选择以便术语Flavors：Fruity和Flavors：Nutty缩小导航状态。因此，用户有时能通过选择单个属性下的多个值来细化查询。

最好，将除去作为导航选项的某些属性，如果它们不再是有效或有用的选择。例如，如果结果集中的所有文档共享共用术语(除选择来达到导航状态的术语外)，那么选择那个术语将不会进一步细化结果集，因此，作为导航选项的与那个术语有关的属性被除去。例如，将图6与图4比较，  已经除去作为导航选项的属性WineTypes27，因为在结果集中的所有文档42共享相同的术语，WineTypes：Appelational Wines。在优选实施例中，界面10的另外特性在于将这一信息作为结果集中的文档42的共同特性显示给用户。例如，参考图6，界面10包括表示结果集中的文档42的共同特性的显示60。当结果集中的所有文档共享那个术语时，除去作为导航选项的术语防止用户由于选择不细化结果集而浪费时间。

最好，用户界面可以除去作为导航选项的值，如果它们的选择将导致结果集中无文档。例如，将图8与图7比较，在用户选择术语Wine Spectator Range：95-100后，用户界面除去作为导航选项的属性Appelations22的值的列表26中的所有值28，29，除值AlexanderValley29和Napa Valley29外。Alexander Valley29和Napa Valley29仅是用于返回结果集中的至少一个文档的属性Appellations的值的列表26中的两个值；所有其他值28返回空集。除去作为将导致空结果集的导航选项的值通过防止用户到达僵局来节省用户时间。

最好，用户界面允许用户使用全文搜索来搜索所需词。根据本发明的一个实施例，如图9所示，搜索框30最好允许用户执行用于感兴趣的术语的全文搜索，而不执行文档本身的全文本搜索。最好，用户界面通过显示包括由属性36组织的术语34的列表32，并允许用户从它们中选择来响应这种搜索。最好，用户界面通过向用户显示对应于选择的那个术语的导航状态来响应用户选择。然后用户可以从那个状态导航(即，通过缩小或扩大它)，或执行用于术语的另外的全文搜索。

最好，用户界面10显示对应于当前导航状态的全部或部分文档列表41。最好，如果用户对特定文档42感兴趣，用户可以选择它并获得包含有关它的另外的信息的记录70，包括与那个文档有关的术语74的列表72，如图10所示。最好，用户界面10允许用户选那些术语74的任一子集，以便导航到对应于所选定的术语集的导航状态。

最好，用户界面10还提供直接链接到相关但不一定概括或细化本发明的相关导航状态的导航选项。这些链接最好由本导航状态推断用户兴趣并允许用户横跨相关主题。例如，如果用户正观看食品域中的特定导航状态，链接可以将用户引导到使那些食品更全面的葡萄酒域中的葡萄酒的导航状态。

尽管在此已经将导航系统的界面描述为用户界面10，界面能提供访问导航系统的其它形式。在另外的实施例中，界面可以是应用程序界面以允许为或通过其他应用访问导航系统。界面还可以增强独立的面向数据的应用的功能性。界面还可以用在基于WWW的应用或基于XML应用的上下文中。导航系统还可以同时支持多个界面模式。用多种方式可以使导航系统可用，例如，经无线通信或在手持设备上。

知识库

最好，导航系统将与导航有关的所有信息存储在知识库中。知识库是来自两个过程的信息库：分类学定义的分类。分类学定义是识别相关属性以便特征化文档、确定用于那些属性的可接受值(诸如值列表或范围)，以及定义术语(属性值对)中的细化关系的偏序的过程。分类是将术语与文档关联的过程。还可以使用知识库来维护支持这两个过程的任何信息资产，诸如域、分类规则和缺省期望。另外，可以使用知识库来维护影响用户导航经历的互补信息和资料。

分类学定义过程识别适当地特征化文档的一组属性。组织分类学定义过程的典型方法是将文档集排列成为符合自然分组的文档集的域，以及对那个域来说，易处理的多个属性足以在那个域的文档中有效地区分和导航。知识库最好包括每个域的特征，其可以包括涉及那个域中的文档分类的规则或缺省期望。

分类学定义过程还识别当适当时，用于每个属性的在变化的特征级的值的全集。这些值最好识别集合中的文档的特定属性。可以清楚地列举或隐含地定义这些值。例如，对“颜色”属性，可以指定有效颜色值的全集，但对“价格”或“日期”属性，可以指定值落在其中的范围或通用日期类型，而不定义范围。识别那些值的过程可以包括研究域或分析文档集。

分类学定义过程还定义术语中的细化关系的偏序(属性值对)。例如，术语Origin：France能细化术语Origin：Europe。细化关系是可传递和反对称的，但不一定全部。传递性表示如果术语A细化术语B以及术语B细化术语C，那么术语A细化术语C。例如，如果Origin：Paris细化Origin：France和Origin：France细化Origin：Europe，那么Origin：Paris细化Origin：Europe。反对称表示如果两个术语不同，那么术语不能彼此细化。例如，如果Origin：Paris细化Origin：France，那么Origin：France不细化Origin：Paris。

另外，术语中细化关系的偏序不一定全部一个。例如，能有两个术语，Origin：France和Origin：Spain以便没有一个术语细化另一个。具有这一属性的两个术语被说成是不可比。通常，如果对从那个集选择的不同术语的任一对，一组两个或多个术语为互相不可比，则两个术语不可比。典型地，但不一定，具有不同属性的两个术语将是不可比的。

假定一组术语，如果术语不细化该集中的任一其他术语，则为最大术语，以及如果该集中的没有其他术语细化它，则它是最小术语。例如，在集{Origin：France，Origin：Paris，Origin：Spain，Origin：Madrid}中，Origin：France和Origin：Spain是最大的，而Origin：Paris和Origin：Madrid是最小的。在知识库中，术语如果不细化任何其他术语则为根术语，如果没有其他术语细化它，则该术语为叶术语。

图11A、11B和11C示例说明根据偏序关系排列的、能用于分类葡萄酒的属性112和值114。属性112是Type/Varietal、Origin和Vintage。每个属性112对应于用于那个属性的最大术语。属性112能具有相比不可比值(例如，Vintage)、值的树(例如，Origin)或允许值细化两个或多个相互不可比值的集(例如，Type/Varietal)的通用偏序的固定集。箭头113表示值114中的细化关系。

可以用几种方法识别和开发属性和值，包括手动或自动处理和分析文档。此外，这种分析可以是自顶向下或自底向上；即，从根术语开始并进行达到叶术语，或从叶术语开始并努力进行根术语。对具有所显示的发明来传播消息的感兴趣的零售商或其他人也可以定义属性和术语。

分类过程通过将每个文档与一组术语关联来定位(locate)导航状态中的文档。每个文档与一组相互不可比术语，例如{Type/Varietal：Chianti，Origin：Italy，Vintage：1996}以及任何其他所需描述性信息相关。如果文档与指定术语有关。那么文档也将与指定术语细化的所有术语相关。

分类过程可以根据各种工作流处理。以串行或并行分类文档，以及可以一次或多次并以任何顺序执行自动和手动分类步骤。为提高精确性和吞吐量，可以将人类专家指定为监视用于特定文档子集分类任务，或甚至用于特定文档子集的特定属性的专家。另外，可以交织分类和分类学过程，特别是从一个过程获得的知识允许在另一中改进。

图12表示说明在用于分类过程250的可能流程中的阶段。数据采集步骤252，即，用于数据库的文档集，可以用各种不同方法。例如，具有导航系统将在其上操作的产品目录的零售商可以将描述其产品的文档集提供为预先定义集。另外，可以从一个源，例如一个Web站点，或从多个源，诸如多个Web站点收集文档，然后聚集。如果所需文档是Web页，那么可通过适当地爬行Web、选择文档并删除该域中不适合的文档来收集文档。在数据转换步骤254，格式化并解析所收集的文档以便于进一步处理。在自动分类步骤256中，按序处理格式化和解析文档以便自动将文档与术语联系。在手动分类步骤258中，人类评论家可以校验和修改自动分类，从而确保质量控制。最好，在自动分类步骤256或手动分类步骤258中违反的任何规则或期望将被标记并显示给人类评论家作为手动分类步骤258的一部分。如果将收集的文档分成域，那么通常将有指定用来分类来自每个域的文档的最小或最佳属性集的规则以及其他域特定的分类规则。当完成分类处理时，每个文档将具有与其相关的一组术语，其定位导航状态集中的文档。

在图13中，表180表示所分类的葡萄酒瓶集的可能表示。最好，每个记录与能是唯一标识符的文档号182、名称184和相关术语186相关。名称最好是允许经全文搜索引擎以及经基于术语的导航系统可以访问的集合的描述性信息。

在本发明的另一方面中，知识库可以包括文档的规范表示的目录。每个目录记录表示可以与一个或多个文档有关的概念上不同的项。目录允许来自与项有关的多个文档，可以是来自多个源的配置文件信息的聚集。例如，如果由两个卖主销售相同的葡萄酒，以及如果一个卖主提供制造年份以及地理位置信息以及另一个提供口味信息，能在用于那种葡萄酒的目录记录中组合来自两个卖主的信息。目录也可能通过删除重复配置来提高分类过程的效率。在图12中，目录创建步骤260将所分类的文档与目录记录关联，当适当时，创建新目录记录。为便于参照，通过唯一标识符，可在目录中唯一地标识项。

知识库也可以定义库，其中库是分组以便一次可搜索的文档的子集。例如，特定的在线葡萄酒商人可能不希望显示对应于由那个商人的竞争者销售的产品的文档，即使知识库包含这种文档。在这种情况下，知识库可以定义不包括由商人的竞争者销售的葡萄酒的文档库。在图12中，库创建步骤262可以定义基于属性、术语或文档的任何其他属性的库。可以用不止一个库标识文档。知识库可以包含已经为特定库定制的属性或术语。

在图12中，输出处理步骤264将来自知识库的信息输出到执行生成可导航数据结构所需的另外的处理的系统的另一阶段。

导航状态

导航系统清楚或隐含地表示导航状态的集合。这些导航状态通过由涉及术语的偏序导出的细化的偏序来关联。

导航状态具有两种表示。第一，导航状态对应于文档集合的子集。第二，导航状态对应于相互不可比术语集。图14基于如上所述的葡萄酒例子，示例说明用于文档和术语的一些导航状态。例如，一个导航状态224是{Origin：South America}(文档#1，#4，#5)；第二导航状态224是{Type/Varietal：White，Origin：United States}(文档#2，#9)。对应于每个导航状态的文档的子集包括通常与相应的相互不可比术语集中的所有术语关联的文档。同时，对应于每个导航状态的相互不可比术语集包括来自对文档子集来说共同的术语集的所有最小术语，即，共同与子集中的每个文档关联的术语集。每个导航状态最好是唯一的并且全部指定，对每个特定的术语集来说，或对指定文档集来说，仅有一个对应的导航状态。

定义导航状态集最好的一个方法是通过标准的相互不可比术语集唯一地识别每个导航状态。将任意术语集映射到规范相互不可比术语集的两步映射过程创建满足这一属性的状态。在该过程的第一步中，将任意术语集映射到与所有这些术语相关的文档的子集上。回想如果文档与指定术语关联，那么文档也将与指定术语细化的所有术语关联，在过程的第二步中，将这一文档子集映射到对那个文档集中的所有文档共同的术语集中的最小术语集上。从这一第二步导出的术语集是唯一识别相应的文档子集，从而是用于导航状态的规范表示的相互不可比术语集。通过示例，参考图14中的葡萄酒例子，术语集{Origin：France}映射到文档子集{文档#8，#11}上，其依次映射到规范术语集{type/varietal：Red，Origin：France}上。

通过从与术语有关的偏序导出的细化关系220的偏序，关联导航状态222，224，226。能根据文档子集或定义导航状态的术语集来表示这一偏序。根据文档子集表示的导航状态A细化导航状态B，如果对应于状态A的文档集是对应于状态B的文档集的子集的话。根据术语集表示的导航状态A细化导航状态B，如果状态B中的所有术语均在状态A中或被状态A中的术语细化的话。参考图14，对应于术语集{type/Varietal：Red，Origin：Chile}{文档#4}的导航状态226细化对应于{Origin：Chile}(文档#4，#5)的导航状态224。由于导航状态中的细化关系产生偏序，因此它们是可传递并且反对称的。在例子中，{Type/Varietal：Red，Orgin：Chile}(文档#4)细化{Origin：Chile}(文档#4，#5)以及{Origin：Chile}(文档#4，#5)细化{Origin：South America}(文档#1，#4，，#5)；因此，{Type/Varietal：Red，Orgin：Chile}(文档#4)细化{Origin：SouthAmerica}(文档#1，#4，，#5)。将根导航状态222定义成对应于整个文档集的导航状态。将叶导航状态226定义成不能进一步细化的导航状态，并且通常(尽管不一定)对应于各个文档。在根222和叶226之间能有任意多个间接导航状态224。假定一对导航状态A和B，其中B细化A，那么在偏序中有多个能将A连接到B的间接导航状态224的路径。为便于定义，参考在此所述的实现，将导航状态视为自细化。

用户通过察看通常在根导航状态22开始的一个或多个导航状态的序列来浏览文档集。在这些状态中，有三个基本的模式。第一模式是细化，或将当前导航状态移动到细化它的导航状态。用户能通过将术语增加到当前导航状态上或通过细化当前导航状态中的术语来执行细化，即用术语的细化来代替那个术语。在用户增加或细化术语后，根据如上所述的两步映射，能将新术语集映射到规范术语集上。第二模式是概括，或将当前导航状态移动到当前状态细化的更通用的导航状态上。用户能通过从当前导航状态去除术语或通过概括当前导航状态中的术语，即，用当前术语细化的术语代替当前术语来执行概括。在用户去除或概括术语后，能将新术语集映射到规范术语集上。第三模式以所需术语集的形式简单地创建查询，所需术语集能被再次映射到规范术语集上以便获得导航状态。

实现

将知识库变换成可导航数据结构以便实现本发明。可以全部预计算、运行时动态计算或部分预计算导航状态。可以使用超高速缓存来避免导航状态的冗余计算。

在优选实施例中，导航状态集可以表示为图形，最好是具有标记边缘的有向非循环多重图。图形是由节点和边缘组成的组合结构，其中每个边缘链接一对节点。由边缘链接的两个节点被称为终点。根据本发明，节点对应于导航状态，以及边缘表示从一个导航状态细化到另一个的转变。由于细化是有向的，每个边缘从更通用的节点指向细化它的节点。因为在导航状态上存在偏序，在图中没有有向循环，即，图形是非循环的。最好，图形是多重图，因为其允许连接指定节点对的多个边缘的可能性。每个边缘用术语标记。每个边缘具有从更通用的终点的术语集开始、增加边缘术语和使用两步映射来使这一术语集翻译成进行细化的规范形式的属性，细化导致为另一终点的导航状态。即，每个边缘表示基于增加单个术语的节点间的细化转变。

为理解图形的结构，下述定义是有用的：后裔、先辈、最小共同先辈(LCA)、真先辈、真后裔以及最大下界(GLB)。这些定义应用于术语中和节点中的细化偏序上。如果A和B是术语以及B细化A，那么B被说成是A的后裔以及A被说成是B的先辈。另外，如果A和B是不同的术语，那么B被说成A的真后裔，以及A被说成是B的真先辈。如果A和B均是节点，应用相同的定义。

如果C是A的先辈，以及C也是B的先辈，那么C被说成是A和B的共同先辈，其中A、B和C均是术语或者均是节点。A和B的共同先辈集的最小元素被称为A和B的最小共同先辈(LCA)。如果没有术语具有一对不可比先辈，那么两个术语或两个节点的LCA是唯一的。例如，Origin：Argentina和Origin：CHile的LCA是图11B的术语110的偏序中的Origin：South America。然而，一般来说，可以有用于指定术语或节点对的LCA集。

图形中的节点计算最好自底向上执行。

可以由分类文档直接计算图形中的叶节点-即，对应于叶导航状态的节点。典型地，但不一定必须，叶节点将对应于包含单个文档的集。通过计算叶节点的LCA闭合-即叶节点的子集的LCA的所有节点，获得剩余的、非叶节点。

根据称为用于标记方便的R函数的细化函数，确定图形的边缘。R函数将两个节点A和B用作自变量，其中A是B的真先辈，以及返回最大术语集以便如果术语C在R(A，B)中，那么用术语C细化节点A导致A的真后裔和B的先辈(不一定是真的)的节点。例如，在图14中，R({Type/Varietal：Red}，{Type/Varietal：Merlot，Orgin：Argentina，Vintage：1998})＝{Type/Varietal：Merlot，Origin：South America，Vintage：1998}。如果B₁是B₂的先辈，那么R(A，B₁)是R(A，B₂)的子集-假定A是B₁和B₂的真先辈。例如，R({Type/Varietal：Red}{Type/Varietal：Red，Origin：SouthAmerica})＝{Origin：South America}，

在图中，节点A和B之间的边缘将对应于R(A，B)中的术语子集。同时，没有来自单个先辈节点A的两个边缘使用用于细化的相同术语。如果节点A具有后裔节点集(B₁，B₂，...)以便术语C处于所有R(A，B_i)中，那么仅来自具有术语C的节点A的边缘到达LCA(B₁，B₂，...)，其被保证是节点Bi中的唯一最大节点。在图14中，例如，来自具有术语Origin：South America的节点{Type/Varietal：Red}的边缘经过节点{Type/Varietal：Red，Origin：South America}而不是节点的真后裔{Type/Varietal：Merlot，Orgin：South America，Vintge：1998}和{Type/Varietal：Red，Origin：Chile}。图形的LCA闭合属性确保在B_i中存在唯一最大节点。因此，每个边缘将节点-术语对唯一地映射到那个节点的真后裔上。

图形的LCA闭合导致对指定术语集S来说，其术语集细化S的节点集具有唯一最大节点的有用特性。这一节点被称为S的最大下界(GLB)。

可以清楚地计算图形并将图形存储在组合数据结构中；在不一定包含清楚的节点和边缘表示的结构中隐含地表示图形，或使用结合这些策略的方法来表示图形。因为导航系统通常将在大量文档集上操作，最好用可缩放的方法来表示该图形。

能通过计算每个可能的叶节点的子集的LCA来获得该图形。然而，这种方法在叶节点的数量方面按指数增长，并且固有的不能伸缩。用于获得LCA闭合的另外的策略是重复地考虑图中的所有节点对，检索每个对的LCA是否在图形中，以及根据需要，将那个LCA增加到该图形中。这一策略尽管在前一个上有显著的改进，但仍然相对地不可缩放。

预计算节点的更有效的方法是顺序地处理文档集，计算用于每个文档的节点，以及将那个节点以及维护LCA闭合所需的任何其他节点增加到图形上。系统存储节点和边缘作为有向非循环多重图形。初始化该图形以便包含对应于空术语集的单个节点，根节点。参考图15，在用于将新节点插入该图形的过程230中，在步骤232，为将插入不对应于现有节点的图形的每个新文档，系统创建新节点。在步骤234，在将新节点插入图形中之前，系统递归地生成任何缺少的LCA节点并将其插入根节点(或先辈节点)和新节点之间。为确保每个节点插入后的LCA闭合，系统在插入其真先辈的所有其他节点后，插入在步骤236和238中丢失的文档节点。

插入新节点需要在步骤236中增加从先辈到节点的适当的边缘，以及在步骤238中增加新节点外的后裔。最好通过识别具有引起新节点的细化术语并且还没有用在通向新节点的中间先辈的边缘上的那些细化术语的先辈来确定进入节点的边缘。节点外的边缘最好通过计算新节点的GLB和适当地增加从新节点到GLB以及到GLB具有到其边缘的节点的边缘来确定。

通过遵循用于集合中的每个文档的上述过程，可以预计算整个图形。在图形的大小易处理的情况下，或如果用户很想察看具有相等概率的每个导航状态，最好预计算图形。然而，实际上，用户通常比其他更频繁地察看一些导航状态。的确，当图形变大时，可能根本看不到一些导航状态。不幸的是，将察看导航状态的频率的可靠预测是很困难的。

预计算导航状态的另外的策略是创建允许动态地计算导航状态的索引。特别地，能按与那个文献有关的或具有与那个文档相关的细化的所有术语来索引每个文档。最终的索引通常在大小方面比存储导航状态的图形的数据结构更小。这一动态方法可以节省空间和预计算时间，但其可能以用于操作的较高响应时间或较高计算需求的代价来完成此操作。动态实现可以使用从指定导航状态返回所有细化术语R函数的一个变量形式，以及用于计算术语集的GLB的过程。

可以预计算导航状态的子集。最好预计算动态计算代价最高的状态。例如，如果状态对应于大量文档子集，最好预先计算它。在一个可能的部分预计算方法中，可以预计算对应于高于阈值大小的文档子集的所有导航状态。如果频繁地察看状态，最好预计算状态。在一些实例中，可以预测将察看导航状态的频率。即使将察看导航状态的频率不能预先预测，能通过高速缓存动态计算的结果来降低连续地预计算需要。可以高速缓存最近或最频繁察看的状态。

如参考界面所述，系统支持三种查询操作-即通过指定术语来细化、概括和查询。可以根据图形来进一步描述这些操作。对查询细化，系统列举在从对应于当前导航状态的节点的边缘上的术语。当用户选择用于细化的术语时，系统通过显示那个边缘通向的节点来响应。类似地，对查询概括选项，系统列举和选择通向(而不是从)对应于当前导航状态的节点的边缘。另外，可以通过指定术语集，将查询概括实现为特定的查询情形。对通过指定一组关键字的查询来说，系统创建对应于指定术语集的虚拟节点并确定图形中的虚拟节点的GLB。如果未发现GLB，那么将没有文档满足查询。否则，GLB节点将是对应于所有文档满足查询的导航状态的图形中的最通用节点。

本发明的导航系统允许信息提供者使导航系统覆盖在所有文档集上。通过不同的提供者能独立地执行本发明的知识库和导航方面，以及信息提供者可以向单独的实体外界供应这些函数。类似地，通过导航专家，可以输入所生成的知识库。信息提供者也可以将这一导航需求外界供应给导航系统提供者。导航系统提供者能向消费者收取用于系统的许可费，而与其使用量无关。另外，如果产品是可用的，导航系统提供者能经系统按每次点击、每次购买向消费者收费，或通过导航系统，由一次点击生成的每个交易收费。导航系统提供者还能充当聚集器-由多个源编译记录、将它们组合到全局数据集中，以及生成导航系统以便搜索数据集。

根据本发明的导航系统也可以提高用户配置能力和销售能力。导航系统可以基于用户选择，包括选择来开发导航状态集的特定路径来维护用户配置文件。使用知识库，系统还可以通过将具有关于相关文档、属性和术语的信息的选择信息补充到知识库中来推断有关用户喜好和兴趣的另外的信息。可以将那个信息使用到与用户感兴趣的文档有关的市场商品和服务上。

已经针对本发明的特定实施例给出了上述说明。本发明可以以其他特定形式具体实现而不背离本发明的范围和范围。仅通过参考和示例说明而不通过限制在此使用的实施例、图、术语和例子。通过附加权利要求表示本发明的范围以及落在权利要求的等效的意思和范围内的所有改变打算包含在此。

Claims (84)

1.一种用于资料集的导航系统，包括：

特征化所述资料的多个属性；

描述所述资料的多个值，其中每个值具有与所述至少一个属性的关联，以及每个关联定义属性-值对，以及其中一些属性-值对细化其他属性-值对；

多个导航状态，其中每个导航状态对应于特定属性-值对集和特定资料子集；以及

界面，所述界面提供多个转变，每个转变提供两个导航状态间的直接路径，其中每个转变表示从对应于始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集的变化，其中一系列一个或多个转变提供任意两个导航状态间的路径，在至少第一导航状态和第二导航状态间有不至一个路径。

2.如权利要求1所述的导航系统，其中从始发导航状态到目的地导航状态的至少一个转变表示细化用于始发导航状态的相应的属性-值对集的一个的值。

3.如权利要求1所述的导航系统，其中从始发导航状态到目的地导航状态的至少一个转变表示用于始发导航状态的相应的属性-值对集的一个的值的概括。

4.如权利要求1所述的导航系统，其中从始发导航状态到目的地导航状态的至少一个转变表示取消选定用于始发导航状态的相应的属性-值对集的一个的属性。

5.如权利要求1所述的导航系统，其中从始发导航状态到第一目的地导航状态的第一转变表示选择对应于第一属性的属性-值对，以及从始发导航状态到第二目的地导航状态的第二转变表示选择对应于第二属性的属性-值对。

6.如权利要求1所述的导航系统，其中从始发导航状态到目的地导航状态的至少一个转变表示对应于属性的属性-值对的说明，对该属性，在对应于始发导航状态的属性-值对集中没有对应的属性-值对。

7.如权利要求1所述的导航系统，其中始发导航状态对应于资料集中的一个资料，从所述始发导航状态到目的地导航状态的至少一个转变表示选择与所述始发导航状态相关的特定属性-值对。

8.如权利要求1所述的导航系统，其中清楚地定义与所述多个属性的至少一个关联的值。

9.如权利要求1所述的导航系统，其中隐含地定义与所述多个属性的至少一个关联的值。

10.如权利要求1所述的导航系统，其中对共享共同属性的属性-值对，没有属性-值对细化多个相互不可比属性-值对。

11.如权利要求1所述的导航系统，其中对共享共同属性的属性-值对，至少一个属性-值对细化多个相互不可比属性值对。

12.如权利要求1所述的导航系统，其中没有属性-值对细化多个相互不可比属性-值对。

13.如权利要求1所述的导航系统，其中至少一个属性-值对细化多个相互不可比属性-值对。

14.如权利要求1所述的导航系统，其中对相应于不同属性的任意两个属性-值对，所述两个属性-值对是不可比的。

15.如权利要求1所述的导航系统，其中所述资料集包括与单个主题区相关的资料。

16.如权利要求1所述的导航系统，其中所述资料集包括与多个主题区相关的资料。

17.如权利要求1所述的导航系统，其中所述资料集包括资料子集，所述子集可整体导航，在所述资料集中的所述资料的一部分被指定到所述子集。

18.如权利要求17所述的导航系统，其中采用所述界面来提供与所述资料子集有关的多个转变。

19.如权利要求17所述的导航系统，其中所述资料集包括多个子集，所述多个子集的每一个可独立地整体导航，所述资料集中的一部分资料被指定到每个子集，所述资料的至少一个被指定到不止一个子集。

20.如权利要求1所述的导航系统，进一步包括用于所述资料集中的每个资料的配置文件，所述配置文件包括属性-值对集。

21.如权利要求20所述的导航系统，所述配置文件进一步包括说明性信息。

22.如权利要求1所述的导航系统，所述界面包括人工用户界面。

23.如权利要求1所述的导航系统，所述界面包括应用程序界面。

24.如权利要求1所述的导航系统，其中所述界面能在基于环球网的环境中操作。

25.如权利要求1所述的导航系统，其中所述界面能在基于XML环境中操作。

26.如权利要求1所述的导航系统，其中所述界面补充独立面向数据程序的功能性。

27.如权利要求1所述的导航系统，所述界面包括基于所述多个导航状态中的多个转变，允许从当前导航状态导航的指导搜索工具。

28.如权利要求27所述的导航系统，所述界面包括用于搜索属性的全文搜索工具。

29.如权利要求27所述的导航系统，所述界面包括用于搜索值的全文搜索工具。

30.如权利要求27所述的导航系统，进一步包括用于所述资料集中的每个资料的配置文件，所述配置文件包括说明性信息，所述界面包括用于搜索所述配置文件中的说明性信息的全文搜索工具。

31.如权利要求27所述的导航系统，所述界面包括访问所述资料集中的资料。

32.如权利要求27所述的导航系统，所述界面包括显示对应于当前导航状态的属性-值对。

33.如权利要求32所述的导航系统，显示对应于当前导航状态的属性-值对包括用户选定的属性-值对和推理的属性-值对，所述界面包括用户选定的属性-值对和推理属性-值对的指示。

34.如权利要求32所述的导航系统，显示对应于当前导航状态的属性-值对仅包括相互不可比属性-值对。

35.如权利要求32所述的导航系统，其中所述显示按属性组织对应于当前导航状态的属性-值对。

36.如权利要求32所述的导航系统，其中所述显示按更通用属性-值对组织对应于当前导航状态的属性-值对。

37.如权利要求27所述的导航系统，所述指导搜索工具包括显示用于从当前导航状态选择的导航选项，所述选项对应于所述当前导航状态的转变。

38.如权利要求37所述的导航系统，所述导航选项包括为对应于当前导航状态的所述属性-值对的细化的属性-值对。

39.如权利要求38所述的导航系统，其中所述选项包括显示属性-值对列表集，每个列表对应于所述属性的一个，列表包括细化对应于当前导航状态的属性-值对的属性-值对，以及一些列表包括对相应于当前导航状态的属性-值对不可比的属性值对。

40.如权利要求37所述的导航系统，其中所述显示按属性组织导航选项。

41.如权利要求37所述的导航系统，其中所述显示按更通用属性-值对组织导航选项。

42.如权利要求37所述的导航系统，所述导航选项包括对应于当前导航状态的属性-值对不可比的属性-值对。

43.如权利要求37所述的导航系统，所述导航选项包括为对应于当前导航状态的属性-值对概括的属性-值对。

44.如权利要求37所述的导航系统，所述导航选项包括从对应于当前导航状态的所述属性-值对集取消选定属性-值对。

45.如权利要求37所述的导航系统，所述导航选项进一步包括到相关的导航状态的链接。

46.如权利要求45所述的导航系统，其中所述相关导航状态是当前导航状态的概括。

47.如权利要求45所述的导航系统，其中所述相关导航状态是当前导航状态的细化。

48.如权利要求45所述的导航系统，其中所述链接对应于两个或多个转变的路径。

49.一种用于定义用于资料集的分类学的方法，包括步骤：

定义特征化资料集中的资料的多个属性；

定义描述所述资料集中的资料的多个值，每个值具有与至少一个属性的关联，每个关联定义属性-值对；以及

定义所述属性-值对中的细化关系的分层，所述分层定义用于所述多个属性的至少一个的所述属性-值对中的偏序，所述分层包括从根级的多个细化级。

50.一种用于分类资料集的方法，包括步骤：

定义特性化资料集中的资料的多个属性；

定义描述所述资料集中的资料的多个值，所述值具有与至少一个属性的关联，每个关联定义属性-值对；

定义所述属性-值对中的细化关系的分层，所述分层定义用于所述多个属性的至少一个的所述属性-值对中的偏序，所述分层包括从根级的多个细化级；以及

通过将每个资料与属性-值对集关联，定义用于每个资料的配置文件。

51.如权利要求50所述的方法，其中定义用于每个资料的配置文件的步骤包括将每个资料与来自有限属性-值对子集的至少一个属性-值对关联。

52.如权利要求51所述的方法，其中所述有限属性-值对子集由对应于一个属性的所述属性-值对组成。

53.如权利要求50所述的方法，其中定义用于每个资料的配置文件的步骤包括将一些资料与来自有限属性-值对子集的仅一个属性-值对关联。

54.如权利要求53所述的方法，其中所述有限属性-值对子集由对应于一个属性的所述属性-值对组成。

55.如权利要求50所述的方法，其中定义用于每个资料的配置文件的步骤包括将一些资料与属性-值对关联以便与第一属性-值对的关联隐含与第二属性-值对的关联。

56.如权利要求50所述的方法，其中定义用于每个资料的配置文件的步骤包括将每个资料与说明性信息关联。

57.一种用于信息导航系统的知识库，所述导航系统在资料集上操作，包括：

特征化所述资料的多个属性；

描述所述资料的多个值，每个值具有与一个或多个属性的关联，每个关联定义属性-值对；

所述属性-值对中的细化关系的分层，所述分层定义所述属性-值对中的偏序，其中，对多个属性的至少一个，所述分层包括来自根级的多个细化级；以及

用于每个资料的配置文件，所述配置文件包括属性-值对集。

58.如权利要求57所述的知识库，进一步包括分类规则集。

59.如权利要求57所述的知识库，进一步包括用于分类过程的缺省期望集。

60.如权利要求57所述的知识库，进一步包括所述资料集中的子集定义集。

61.如权利要求57所述的知识库，进一步包括导航规则集。

62.一种允许用户浏览资料集的方法，特征化所述资料的多个属性，描述所述资料的多个值，每个值具有与所述至少一个属性的关联，以及每个关联定义属性-值对，一些属性-值对细化其他属性-值对，包括步骤：

定义多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子集；

提供界面，所述界面提供多个转变，每个转变提供两个导航状态之间的直接路径，其中每个转变表示从对应于始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集的变化，其中一系列一个或多个转变提供任意两个导航状态之间的路径，在至少第一导航状态和第二导航状态间有不止一个路径；

提供转变显示，用于选择；

接受转变选择；

获得与所选定的转变有关的结果导航状态；以及

提供所述结果导航状态中的修改转变显示用于选择。

63.如权利要求62所述的方法，其中提供用于选择的转变显示的步骤包括提供属性-值对的显示。

64.如权利要求62所述的方法，其中提供接受转变选择的步骤包括接受属性-值对的选择。

65.如权利要求62所述的方法，其中提供修改转变显示的步骤包括提供修改属性-值对集的显示。

66.如权利要求65所述的方法，其中提供修改属性-值对集的显示的步骤包括提供用于在前选定的属性-值对的细化属性-值对集的显示。

67.如权利要求64所述的方法，其中接受属性-值对集的选择的步骤触发获得结果导航状态的步骤。

68.如权利要求63所述的方法，其中提供显示的步骤包括按属性组织所述属性-值对。

69.如权利要求65所述的方法，其中提供修改属性-值对集的显示包括按更通用的属性-值对组织所述属性-值对。

70.如权利要求62所述的方法，其中提供修改显示的步骤包括增加在所述显示中在前未表示的属性。

71.如权利要求62所述的方法，进一步包括接受另外选定的属性-值对和获得与所选定的属性-值对和所述另外的选定属性-值对有关的另外的结果导航状态的步骤。

72.如权利要求71所述的方法，其中所述另外的选定属性-值对与不同于所选定的属性-值对的属性关联。

73.如权利要求62所述的方法，进一步包括显示在前选定的属性-值对的列表的步骤。

74.如权利要求73所述的方法，进一步包括接受取消选定所选定的属性-值对和获得修改的结果导航状态的步骤。

75.一种用于允许用户浏览资料集的方法，特征化所述资料的多个属性，描述所述资料的多个值，每个值具有与所述至少一个属性的关联，每个关联定义属性-值对，一些属性-值对细化其他属性-值对，多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子集，提供多个转变的界面，每个转变提供两个导航状态之间的直接路径，其中每个转变表示从对应于始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集的变化，其中一系列一个或多个转变提供任意两个导航状态之间的路径，在至少第一导航状态和第二导航状态之间有不止一个路径，包括步骤：

显示全文搜索框；

接受在所述全文搜索框中输入的搜索术语；

确定匹配所述搜索术语的所述属性-值对；

显示用于所述搜索术语的所述匹配属性-值对；

接受匹配属性-值对的选择；以及

输入对应于选择的所述匹配属性-值对的导航状态。

76.一种用于生成用于在资料集上操作的导航系统的导航数据结构的方法，特征化所述资料的多个属性，描述所述资料的多个值，每个值具有与所述至少一个属性的关联，每个关联定义属性-值对，一些属性-值对细化其他属性-值对，多个导航状态，每个导航状态对应于属性-值对集和特定资料子集，提供多个转变的界面，每个转变提供两个导航状态之间的直接路径，每个转变表示从对应于始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集的变化，一系列一个或多个转变提供任意两个导航状态之间的路径，在至少第一导航状态和第二导航状态之间有不止一个路径，导航数据结构包括对应于导航状态的节点和对应于导航状态之间的转变的边缘，包括步骤：

生成还没有在所述可导航数据结构中的用于所述资料集中的每个资料的新节点；

就最小共同先辈还没有在所述数据结构中的方面来说，将用于所述新节点的最小共同先辈插入所述数据结构中，以及每个节点已经存在于所述导航数据结构中；以及

对每个新节点，通过将边缘增加到节点中来插入所述节点。

77.一种用于提供信息导航系统的方法，所述信息导航系统包括资料集，特征化所述资料的多个属性，描述所述资料的多个值，每个值具有与所述至少一个属性的关联，每个关联定义属性-值对，一些属性-值对细化其他属性-值对，多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子集，包括步骤：

计算所述导航状态；

将所述导航状态存储在数据结构中；

提供到所述信息导航系统的界面，所述界面提供多个转变，每个转变提供两个导航状态之间的直接路径，其中每个转变表示从对应于始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集的变化，其中一系列一个或多个转变提供任意两个导航状态之间的路径，在至少第一导航状态和第二导航状态间有不止一个路径；

接受所述导航系统的查询；以及

响应所述查询，检索所存储的导航状态。

78.如权利要求77所述的方法，其中所述数据结构是包括节点和节点间的边缘的图形数据结构，所述节点表示导航状态，所述边缘表示转变。

79.一种提供信息导航系统的方法，所述信息导航系统包括资料集，特征化所述资料的多个属性，描述所述资料的多个值，每个值具有与所述至少一个属性的关联，每个关联定义属性-值对，一些属性-值对细化其他属性-值对，多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子集，包括步骤：

生成部分预计算导航状态集；

存储所述部分预计算导航状态集；

提供所述信息导航系统的界面，所述界面提供多个转变，每个转变提供两个导航状态之间的直接路径，其中每个转变表示从对应于始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集的变化，其中一系列一个或多个转变提供任意两个导航状态之间的路径，在至少第一导航状态和第二导航状态之间有不止一个路径；

接受所述导航系统的查询；以及

通过检索响应预计算导航状态或计算响应导航状态，返回响应导航状态。

80.一种提供信息导航系统的方法，所述信息导航系统包括资料集，特征化所述资料的多个属性，描述所述资料的多个值，每个值具有与所述至少一个属性的关联，每个关联定义属性-值对，一些属性-值对细化其他属性-值对，多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子集，包括步骤：

将所述导航状态存储在隐含表示中；

提供所述导航系统的界面，所述界面提供多个转变，每个转变提供两个导航状态之间的直接路径，其中每个转变表示从对应于始发导航状态的属性-值对集到对应于目的地导航状态的属性-值对集的变化，其中一系列一个或多个转变提供任意两个导航状态之间的路径，在至少第一导航状态和第二导航状态之间有不止一个路径；

接受所述导航系统的查询；

由所述隐含表示生成响应导航状态；以及

显示所述响应导航状态。

81.如权利要求80所述的方法，进一步包括将所述响应导航状态存储在高速缓存中的步骤。

82.一种配置导航系统的用户的方法，包括步骤：

提供导航系统，导航系统包括资料集，特征化所述资料的多个属性，描述所述资料的多个值，每个值具有与所述至少一个属性的关联，每个关联定义属性-值对，一些属性-值对细化其他属性-值对，多个导航状态，每个导航状态对应于特定属性-值对集和特定资料子集，以及提供多个转变的界面，每个转变提供两个导航状态之间的直接路径，其中每个转变表示从对应于始发导航状态的属性-值对集的变化，其中一系列一个或多个转变提供任意两个导航状态之间的路径，在至少第一导航状态和第二导航状态之间有不止一个路径，可按属性-值对选择转变；

接受用户的属性-值对选择以便在多个导航状态中导航；以及

跟踪所述用户选择的属性-值对。

83.如权利要求82所述的方法，进一步包括基于用户选择的属性-值对，开发用户配置文件的步骤。

84.如权利要求83所述的方法，其中开发用户配置文件的步骤进一步包括基于对应于由用户察看的所述导航状态的所述属性-值对，补充所述用户配置文件的步骤。

Images