Hierarchical data-driven search and navigation system and method for information retrieval

• US 7,567,957 B2
• Filed: 04/20/2006
• Issued: 07/28/2009
• Est. Priority Date: 05/18/2000
• Status: Active Grant

• Current Assignee: Oracle OTC Subsidiary LLC (Oracle Corporation)
• Original Assignee: Endeca Technologies Incorporated (Oracle Corporation)
• Inventors: Johnson, Keith A., Mohta, Vinay B., Gourley, David J., Walter, John S., Knabe, Frederick C., Ferrari, Adam J., Tunkelang, Daniel
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US11/408,797
• Publication Number:
  US 20070083505A1
• Time in Patent Office: 1,195 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A data-driven, hierarchical information search and navigation system and method enable search and navigation of sets of documents or other materials by certain common attributes that characterize the materials. The invention includes several aspects of a data-driven, hierarchical search and navigation system that employs this search and navigation mode. The search and navigation system of the present invention includes features of an navigation interface, a search interface, a knowledge base and a taxonomy definition process and a classification process for generating the knowledge base, a graph-based navigable data structure and method for generating the data structure, World Wide Web-based applications of the system, and methods of implementing the system. Users are able to search or browse a particular collection of documents by selecting desired values for the attributes or by searching the attribute-value pairs. A data-driven, hierarchical information search and navigation system and method enable this navigation mode by associating terms with the materials, defining a set of hierarchical relationships among the terms, providing a guided navigation mechanism based on the relationship between the terms, and providing a search mechanism that can respond to free-text queries with single-term or multi-term interpretations. In another aspect of the invention, implementations of the invention may be scalable through parallel or distributed computation.

Claims

1. A computer-implemented method for providing an information navigation system for searching a set of materials having navigation states, the method comprising:

providing information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

computing navigation states by using a computer, wherein for at least one navigation state of the computed navigation states the particular set of attribute-value pairs corresponding to the at least one navigation state includes a plurality of mutually incomparable attribute-value pairs,

wherein a first navigation state of the computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes,

wherein a second navigation state of the computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;

storing the computed navigation states in a data structure in a memory;

providing an interface to the information navigation system, the interface including a free-text search tool, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state, wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states, and wherein the interface operates in an XML-based environment;

searching, by using the computer, descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accepting a query to the navigation system based at least in part on the free-text query interpretations; and

retrieving a stored navigation state from the data structure responsive to the query.

2. The method of claim 1, wherein the descriptive information includes attribute-value pairs associated with the set of materials.

3. The method of claim 1, wherein the descriptive information includes text distinct from the attribute-value pairs associated with the set of materials.

4. The method of claim 1, wherein the free-text search tool is used to restrict the stored navigation state retrieved to materials matching a search entered into the free-text search tool.

5. A computer-implemented method for providing an information navigation system for searching a set of materials having navigation states, the method comprising:

providing information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

generating a partial set of pre-computed navigation states by using a computer,

wherein a first navigation state of the partial set of pre-computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the information navigation system that the first attribute characterizes,

wherein a second navigation state of the partial set of pre-computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the information navigation system that the third attribute characterizes;

storing the partial set of pre-computed navigation states in a data structure in a memory, the partial set of pre-computed navigation states stored in the data structure including at least one of the first navigation state and the second navigation state;

providing an interface to the information navigation system, the interface including a free-text search tool for and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation to the set of attribute-value pairs corresponding to a destination navigation state, wherein a series of one or more transitions provides a path between any two navigation states, wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state, wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states, and wherein the interface operates in an XML-based environment;

searching, by using the computer, descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accepting a query to the navigation system based at least in part on the free-text query interpretations; and

returning, to a user, a responsive navigation state by retrieving a pre-computed navigation state from the data structure based on the query.

6. The method of claim 5, wherein the descriptive information includes attribute-value pairs associated with the set of materials.

7. The method of claim 5, wherein the descriptive information includes text distinct from attribute-value pairs associated with the set of materials.

8. The method of claim 5, wherein the free-text search tool is used to restrict the responsive navigation state to materials matching a search entered into the free-text search tool.

9. A computer-implemented method for providing an information navigation system for searching a set of materials having navigation states, the method comprising:

providing information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

using a data structure in a memory to permit at least some navigation states of the plurality of navigation states to be computed dynamically,

wherein a first navigation state of the computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes,

wherein a second navigation state of the computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;

providing an interface to the navigation system, the interface including a free-text search tool, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, there being more than one path between at least a third navigation state and a fourth navigation state, wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states, and wherein the interface operates in an XML-based environment;

searching, by using a computer, descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accepting a query to the information navigation system based at least in part on the free-text query interpretations;

generating a responsive navigation state using the data structure based on the query; and

presenting the responsive navigation state to a user.

10. The method of claim 9, wherein the descriptive information includes attribute-value pairs associated with the set of materials.

11. The method of claim 9, wherein the descriptive information includes text distinct from attribute-value pairs associated with the set of materials.

12. The method of claim 9, wherein the free-text search tool is used to restrict the responsive navigation state to materials matching a search entered into the free-text search tool.

13. The method of claim 9, further including the step of storing the responsive navigation state in a cache.

14. The method of claim 9, wherein at least one of the transitions from an originating navigation state to a destination navigation state represents a refinement of the value of one of the corresponding set of attribute-value pairs for the originating navigation state.

15. The method of claim 9, wherein at least one of the transitions from an originating navigation state to a destination navigation state represents a generalization of the value of one of the corresponding set of attribute-value pairs for the originating navigation state.

16. The method of claim 9, wherein at least one of the transitions from an originating navigation state to a destination navigation state represents a de-selection of the attribute of one of the corresponding set of attribute-value pairs for the originating navigation state.

17. The method of claim 9, wherein a first of the transitions from an originating navigation state to a first destination navigation state represents a selection of an attribute-value pair corresponding to a first attribute and a second of the transitions from the originating navigation state to a second destination navigation state represents a selection of an attribute-value pair corresponding to a second attribute.

18. The method of claim 9, wherein at least one of the transitions from an originating navigation state to a destination navigation state represents a specification of an attribute-value pair corresponding to an attribute for which there is no corresponding attribute-value pair in the set of attribute-value pairs corresponding to the originating navigation state.

19. The method of claim 9, wherein an originating navigation state corresponds to only one of the materials in the set of materials, at least one of the transitions from the originating navigation state to a destination navigation state representing a selection of a particular attribute-value pair associated with the originating navigation state.

20. The method of claim 9, wherein the values associated with at least one of the plurality of attributes are defined explicitly.

21. The method of claim 9, wherein the values associated with at least one of the plurality of attributes are defined implicitly.

22. The method of claim 9, wherein, for attribute-value pairs sharing a common attribute, no attribute-value pair refines a plurality of mutually incomparable attribute-value pairs.

23. The method of claim 9, wherein, for attribute-value pairs sharing a common attribute, at least one attribute-value pair refines a plurality of mutually incomparable attribute-value pairs.

24. The method of claim 9, wherein no attribute-value pair refines a plurality of mutually incomparable attribute-value pairs.

25. The method of claim 9, wherein at least one attribute-value pair refines a plurality of mutually incomparable attribute-value pairs.

26. The method of claim 9, wherein, for any two attribute-value pairs corresponding to different attributes, the two attribute-value pairs are incomparable.

27. The method of claim 9, wherein the set of materials includes materials related to a single subject area.

28. The method of claim 9, wherein the set of materials includes materials related to a plurality of subject areas.

29. The method of claim 9, wherein a portion of the materials in the set of materials is assigned to a subset of the set of materials, the subset being integrally navigable.

30. The method of claim 29, wherein the interface is adapted to provide a plurality of transitions related to the subset of materials.

31. The method of claim 9, wherein the set of materials includes a plurality of subsets, each of the plurality of subsets being independently integrally navigable, a portion of the materials in the set of materials being assigned to each subset, at least one of the materials being assigned to more than one subset.

32. The method of claim 9, wherein the information navigation system includes a profile for each of the materials in the set of materials, the profile including a set of attribute-value pairs.

33. The method of claim 32, the profile further including descriptive information.

34. The method of claim 9, the interface including a human user interface.

35. The method of claim 9, the interface including an application program interface.

36. The method of claim 9, wherein the interface operates in a World Wide Web-based environment.

37. The method of claim 9, wherein the interface supplements the functionality of an independent data-oriented program.

38. The method of claim 9, the interface including access to the materials in the set of materials.

39. The method of claim 9, the interface including a presentation of attribute-value pairs corresponding to the current navigation state.

40. The method of claim 39, the presentation of attribute-value pairs corresponding to the current navigation state including user-selected attribute-value pairs and inferred attribute-value pairs, the interface including an indication of user-selected attribute-value pairs and of inferred attribute-value pairs.

41. The method of claim 39, the presentation of attribute-value pairs corresponding to the current navigation state including only mutually incomparable attribute-value pairs.

42. The method of claim 39, wherein the presentation organizes the attribute-value pairs corresponding to the current navigation state by attribute.

43. The method of claim 39, wherein the presentation organizes the attribute-value pairs corresponding to the current navigation state by more general attribute-value pairs.

44. The method of claim 9, the guided search tool including a presentation of navigation options for selection from the current navigation state, the options corresponding to transitions from the current navigation state.

45. The method of claim 9, navigation options including attribute-value pairs that are refinements of the attribute-value pairs corresponding to the current navigation state.

46. The method of claim 9, wherein navigation options include a presentation of a set of lists of attribute-value pairs, each list corresponding to one of the attributes, some lists including attribute-value pairs that refine the attribute-value pairs corresponding to the current navigation state and some lists including attribute value pairs that are incomparable to the attribute-value pairs corresponding to the current navigation state.

47. The method of claim 46, wherein the presentation organizes the navigation options by attribute.

48. The method of claim 46, wherein the presentation organizes the navigation options by more general attribute-value pairs.

49. The method of claim 9, navigation options including attribute-value pairs that are incomparable to the attribute-value pairs corresponding to the current navigation state.

50. The method of claim 9, navigation options including attribute-value pairs that are generalizations of the attribute-value pairs corresponding to the current navigation state.

51. The method of claim 9, navigation options including de-selection of attribute-value pairs from the set of attribute-value pairs corresponding to the current navigation state.

52. The method of claim 9, navigation options further including a link to an associated navigation state.

53. The method of claim 52, wherein the associated navigation state is a generalization of the present navigation state.

54. The method of claim 52, wherein the associated navigation state is a refinement of the present navigation state.

55. The method of claim 52, wherein the link corresponds to a path of two or more transitions.

56. A computer program product, stored on a computer-readable storage medium, for use in providing an information navigation system for searching a set of materials having navigation states, the computer program product comprising instructions for causing a computer to:

provide information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of the materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

compute navigation states by using a computer, wherein for at least one navigation state of the computed navigation states the particular set of attribute-value pairs corresponding to the at least one navigation state includes a plurality of mutually incomparable attribute-value pairs;

wherein a first navigation state of the computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes,

wherein a second navigation state of the computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;

store the computed navigation states in a data structure in a memory;

provide an interface to the information navigation system, the interface including a free-text search tool and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state, wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states, and wherein the interface operates in an XML-based environment;

search descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accept a query to the information navigation system based at least in part on the free-text query interpretations; and

retrieve a stored navigation state from the data structure responsive to the query.

57. The computer program product of claim 56, wherein the descriptive information includes attribute-value pairs associated with the set of materials.

58. The computer program product of claim 56, wherein the descriptive information includes text distinct from attribute-value pairs associated with the set of materials.

59. A computer program product, stored on a computer-readable storage medium, for use in providing an information navigation system for searching a set of materials having navigation states, the computer program product comprising instructions for causing a computer to:

provide information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

use a data structure in a memory to permit at least some navigation states of the plurality of navigation states to be computed dynamically;

wherein a first navigation state of the computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes,

wherein a second navigation state of the computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;

provide an interface to the navigation system, the interface including a free-text search tool, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, there being more than one path between at least a third navigation state and a fourth navigation state, wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states, and wherein the interface operates in an XML-based environment;

search descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accept a query to the information navigation system based at least in part on the free-text query interpretations; and

generate a responsive navigation state using the data structure based on to the query; and

present the responsive navigation state to a user.

60. The computer program product of claim 59, wherein the descriptive information includes attribute-value pairs associated with the set of materials.

61. The computer program product of claim 59, wherein the descriptive information includes text distinct from attribute-value pairs associated with the set of materials.

62. The computer program product of claim 59, wherein the free-text search tool is used to restrict the responsive navigation state to materials matching a search entered into the free-text search tool.

63. A computer-implemented method for providing an information navigation system for searching a set of materials having navigation states, the method comprising:

providing information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

computing navigation states by using a computer, wherein for at least one navigation state of the computed navigation states the particular set of attribute-value pairs corresponding to the at least one navigation state includes a plurality of mutually incomparable attribute-value pairs;

wherein a first navigation state of the computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the information navigation system that the first attribute characterizes,

wherein a second navigation state of the computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;

storing the computed navigation states in a data structure in a memory, wherein the data structure is a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions;

providing an interface to the information navigation system, the interface including a free-text search tool, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state, and wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states;

searching, by using a computer, descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accepting a query to the navigation system based at least in part on the free-text query interpretations; and

retrieving a stored navigation state from the data structure responsive to the query.

64. A computer-implemented method for providing an information navigation system for searching a set of materials having navigation states, the method comprising:

providing information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

generating a partial set of pre-computed navigation states by using a computer;

wherein a first navigation state of the partial set of pre-computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes,

wherein a second navigation state of the partial set of pre-computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;

storing the partial set of pre-computed navigation states in a data structure in a memory, the partial set of pre-computed navigation states stored in the data structure including at least one of the first navigation state and the second navigation state, wherein the data structure is a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions;

providing an interface to the information navigation system, the interface including a free-text search tool, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state, and wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states;

searching, by using the computer, descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accepting a query to the information navigation system based at least in part on the free-text query interpretations; and

returning a responsive navigation state by retrieving a responsive pre-computed navigation state from the data structure based on the query.

65. A computer-implemented method for providing an information navigation system for searching a set of materials having navigation states, the method comprising:

providing information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

using a data structure in a memory to permit at least some navigation states of the plurality of navigation states to be computed dynamically, wherein the data structure is a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions;

wherein a first navigation state of the computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the information navigation system that the first attribute characterizes,

wherein a second navigation state of the computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;

providing an interface to the navigation system, the interface including a free-text search tool and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, there being more than one path between at least a third navigation state and a fourth navigation state, and wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states;

searching, by using a computer, descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accepting a query to the information navigation system based at least in part on the free-text query interpretations;

generating a responsive navigation state using the data structure responsive the query; and

presenting the responsive navigation state to a user.

66. A computer program product, stored on a computer-readable storage medium, for use in providing an information navigation system for searching a set of materials having navigation states, the computer program product comprising instructions for causing a computer to:

provide information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

use a data structure in a memory to permit at least some navigation states of the plurality of navigation states to be computed dynamically, wherein the data structure is a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions;

wherein a first navigation state of the computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the information navigation system that the first attribute characterizes,

wherein a second navigation state of the computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the navigation system that the third attribute characterizes;

provide an interface to the navigation system, the interface including a free-text search tool and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, there being more than one path between at least a third navigation state and a fourth navigation state, and wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states;

search, by using a computer, descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accept a query to the information navigation system based at least in part on the free-text query interpretations;

generate a responsive navigation state using the data structure responsive the query; and

present the responsive navigation state to a user.

67. A computer program product, stored on a computer-readable storage medium, for use in providing an information navigation system for searching a set of materials having navigation states, the computer program product comprising instructions for causing a computer to:

provide information including;

the set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each value of the values having an association with at least one attribute of the attributes, each association defining an attribute-value pair, and

a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of materials, wherein the particular subset of materials consists of materials in the information navigation system that are described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state, such that each material of materials in the particular subset of materials is described by every attribute-value pair in the particular set of attribute-value pairs corresponding to said each navigation state;

compute navigation states, wherein for at least one navigation state of the computed navigation states the particular set of attribute-value pairs corresponding to the at least one navigation state includes a plurality of mutually incomparable attribute- value pairs;

wherein a first navigation state of the computed navigation states includes a first attribute-value pair having a first attribute, in which the first attribute-value pair does not describe all the materials in the navigation system that the first attribute characterizes,

wherein a second navigation state of the computed navigation states includes a second attribute-value pair having the first attribute, in which the second attribute-value pair refines the first attribute-value pair, and

wherein at least one of the first navigation state and the second navigation state includes a third attribute-value pair having a third attribute, which is not the same as the first attribute, wherein the third attribute-value pair is mutually incomparable with the first attribute-value pair and is mutually incomparable with the second attribute-value pair, and the third attribute-value pair does not describe all the materials in the information navigation system that the third attribute characterizes;

store the computed navigation states in a data structure in a memory, wherein the data structure is a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions;

provide an interface to the information navigation system, the interface including a free-text search tool for searching descriptive information associated with the set of materials, and the interface providing a plurality of transitions, each transition providing a direct path, with no intervening navigation states, between two of the navigation states, wherein said each transition represents a change from a set of attribute-value pairs corresponding to an originating navigation state to the set of attribute-value pairs corresponding to a destination navigation state, wherein series of one or more transitions provides a path between any two navigation states, wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state, and wherein the interface includes a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states;

search, by using a computer, descriptive information associated with the set of materials, based at least in part on a free-text query accepted from the free-text search tool of the provided interface, to produce a set of free-text query interpretations;

accept a query to the navigation system based at least in part on the free-text query interpretations; and

retrieve a stored navigation state from the data structure responsive to the query.