Scalable hierarchical data-driven navigation system and method for information retrieval

• US 20020051020A1
• Filed: 09/21/2001
• Published: 05/02/2002
• 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, Gourley, David, Tunkelang, Daniel, Walter, John, Ferrari, Adam, Knabe, Frederick, Lau, Andrew, Mohta, Vinay
• Granted Patent: US 7,617,184 B2
• Time in Patent Office: Days
• US Class Current: 715/854
• 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/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 navigation system and method enable search 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 navigation system that employs this navigation mode. The navigation system of the present invention includes features of an 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. A data-driven, hierarchical information navigation system and method enable this navigation mode by associating terms with the materials, defining a set of hierarchical relationships among the terms, and providing a guided search mechanism based on the relationship between the terms. In another aspect of the invention, implementations of the invention may be scalable through parallel or distributed computation. Implementations of the invention may employ master and slave servers in a hierarchical configuration.

Claims

1. A navigation system for a set of materials, comprising:

a plurality of attributes characterizing the materials;

a plurality of values describing the materials, wherein each of the values has an association with at least one of the attributes and each association defines an attribute-value pair, and wherein some of the attribute-value pairs refine other of the attribute-value pairs;

a plurality of navigation states, wherein each navigation state corresponds to a particular expression of attribute-value pairs and to a particular subset of the materials; and

an interface, the interface providing a plurality of transitions, each transition providing a direct path between two of the navigation states, wherein each transition represents a change from the expression of attribute-value pairs corresponding to an originating navigation state to the expression 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, there being more than one path between at least a first of the navigation states and a second of the navigation states.

2. The navigation system of claim 1, wherein at least one navigation state corresponds to an expression of attribute-value pairs that relates at least one attribute value pair conjunctively.

3. The navigation system of claim 1, wherein at least one navigation state corresponds to an expression of attribute-value pairs that relates at least one attribute value pair disjunctively.

4. The navigation system of claim 1, wherein at least one navigation state corresponds to an expression of attribute-value pairs that relates at least one attribute value pair negationally.

5. The navigation system of claim 1, 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 attribute-value pairs in the corresponding expression of attribute-value pairs for the originating navigation state.

6. The navigation system of claim 1, 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 attribute-value pairs in the corresponding expression of attribute-value pairs for the originating navigation state.

7. The navigation system of claim 1, wherein at least one of the transitions from an originating navigation state to a destination navigation state represents a deselection of the attribute of one of the attribute-value pairs in the corresponding expression of attribute-value pairs for the originating navigation state.

8. The navigation system of claim 1, 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.

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

10. The navigation system of claim 1, wherein at least one of the transitions from an originating navigation state to a destination navigation state represents disjunctive relation of an attribute-value pair to the expression of attribute-value pairs for the originating navigation state.

11. The navigation system of claim 1, wherein at least one of the transitions from an originating navigation state to a destination navigation state represents negational relation of an attribute-value pair to the expression of attribute-value pairs for the originating navigation state.

12. The navigation system of claim 1, wherein an originating navigation state corresponds to 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.

13. The navigation system of claim 1, wherein the values associated with at least one of the plurality of attributes are defined explicitly.

14. The navigation system of claim 1, wherein the values associated with at least one of the plurality of attributes are defined implicitly.

15. The navigation system of claim 1, wherein, for attribute-value pairs sharing a common attribute, no attribute-value pair refines a plurality of mutually incomparable attribute-value pairs.

16. The navigation system of claim 1, wherein, for attribute-value pairs sharing a common attribute, at least one attribute-value pair refines a plurality of mutually incomparable attribute-value pairs.

17. The navigation system of claim 1, wherein no attribute-value pair refines a plurality of mutually incomparable attribute-value pairs.

18. The navigation system of claim 1, wherein at least one attribute-value pair refines a plurality of mutually incomparable attribute-value pairs.

19. The navigation system of claim 1, wherein, for any two attribute-value pairs corresponding to different attributes, the two attribute-value pairs are incomparable.

20. The navigation system of claim 1, wherein the set of materials includes materials related to a single subject area.

21. The navigation system of claim 1, wherein the set of materials includes materials related to a plurality of subject areas.

22. The navigation system of claim 1, wherein the set of materials includes a subset of the materials, the subset being integrally navigable, a portion of the materials in the set of materials being assigned to the subset.

23. The navigation system of claim 22, wherein the interface is adapted to provide a plurality of transitions related to the subset of materials.

24. The navigation system of claim 22, 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.

25. The navigation system of claim 1, further including a profile for each of the materials in the set of materials, the profile including a set of attribute-value pairs.

26. The navigation system of claim 25, the profile further including descriptive information.

27. The navigation system of claim 1, the interface including a human user interface.

28. The navigation system of claim 1, the interface including an applications program interface.

29. The navigation system of claim 1, wherein the interface is operable in a World Wide Web-based environment.

30. The navigation system of claim 1, wherein the interface is operable in an XML-based environment.

31. The navigation system of claim 1, wherein the interface supplements the functionality of an independent data-oriented program.

32. The navigation system of claim 1, the interface including a guided search tool for enabling navigation from a current navigation state based on the plurality of transitions among the plurality of navigation states.

33. The navigation system of claim 32, the interface including a free-text search tool for searching the attributes.

34. The navigation system of claim 32, the interface including a free-text search tool for searching the values.

35. The navigation system of claim 32, further including a profile for each of the materials in the set of materials, the profile including descriptive information, the interface including a free-text search tool for searching the descriptive information in the profiles.

36. The navigation system of claim 32, the interface including access to the materials in the set of materials.

37. The navigation system of claim 32, the interface including a presentation of attribute-value pairs corresponding to the current navigation state.

38. The navigation state of claim 37, 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.

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

40. The navigation system of claim 37, wherein the presentation organizes the attribute-value pairs corresponding to the current navigation state by attribute.

41. The navigation system of claim 37, wherein the presentation organizes the attribute-value pairs corresponding to the current navigation state by more general attribute-value pairs.

42. The navigation system of claim 32, 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.

43. The navigation system of claim 42, the navigation options including attribute-value pairs that are refinements of the attribute-value pairs corresponding to the current navigation state.

44. The navigation system of claim 43, wherein the 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.

45. The navigation system of claim 42, the navigation options including disjunctive selection of attribute-value pairs.

46. The navigation system of claim 45, wherein the disjunctive selection options include a second attribute-value pair that corresponds to an attribute for which a first corresponding attribute-value has previously been selected, the second attribute-value pair being mutually incomparable to the first.

47. The navigation system of claim 42, the navigation options including negational selection of attribute-value pairs.

48. The navigation system of claim 42, wherein the presentation organizes the navigation options by attribute.

49. The navigation system of claim 42, wherein the presentation organizes the navigation options by more general attribute-value pairs.

50. The navigation system of claim 42, the navigation options including attribute-value pairs that are incomparable to the attribute-value pairs corresponding to the current navigation state.

51. The navigation system of claim 42, the navigation options including attribute-value pairs that are generalizations of the attribute-value pairs corresponding to the current navigation state.

52. The navigation system of claim 42, the navigation options including deselection of attribute-value pairs from the expression of attribute-value pairs corresponding to the current navigation state.

53. The navigation system of claim 42, the navigation options further including a link to an associated navigation state.

54. The navigation system of claim 53, wherein the associated navigation state is a generalization of the present navigation state.

56. The navigation system of claim 53, wherein the associated navigation state is a refinement of the present navigation state.

57. The navigation system of claim 53, wherein the link corresponds to a path of two or more transitions.

58. A method for enabling a user to browse a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, some of the attribute-value pairs refining other of the attribute-value pairs, comprising the steps of:

defining a plurality of navigation states, each navigation state corresponding to a particular expression of attribute-value pairs and to a particular subset of the materials;

providing an interface, the interface providing a plurality of transitions, each transition providing a direct path between two of the navigation states, wherein each transition represents a change from the expression of attribute-value pairs corresponding to an originating navigation state to the expression 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, there being more than one path between at least a first of the navigation states and a second of the navigation states;

providing a display of transitions for selection;

accepting a selection of a transition;

obtaining a result navigation state associated with the selected transition; and

providing a revised display of transitions in the result navigation state for selection.

59. The method of claim 58, wherein the step of providing a display of transitions for selection includes at least one transition that corresponds to conjunctive selection of an attribute-value pair.

60. The method of claim 58, wherein the step of providing a display of transitions for selection includes at least one transition that corresponds to disjunctive selection of an attribute-value pair.

61. The method of claim 58, wherein the step of providing a display of transitions for selection includes at least one transition that corresponds to negational selection of an attribute-value pair.

62. The method of claim 58, wherein the step of providing a display of transitions for selection includes providing a display of attribute-value pairs, wherein attribute-value pairs in the display can be related by Boolean operators.

63. The method of claim 62, wherein the step of providing a display includes organizing the attribute-value pairs by attribute.

64. The method of claim 58, wherein the step of accepting a selection of a transition includes accepting a selection of an attribute-value pair.

65. The method of claim 64, wherein the step of accepting the selection of an attribute-value pair triggers the step of obtaining a result navigation state.

66. The method of claim 58, wherein the step of providing a revised display of transitions includes providing a display of a revised set of attribute-value pairs, wherein attribute-value pairs in the revised set can be related by conjunction, disjunction, and negation.

67. The method of claim 66, wherein the step of providing a display of a revised set of attribute-value pairs includes providing a display of, for the previously selected attribute-value pair, a set of refining attribute-value pairs.

68. The method of claim 66, wherein the step of providing a display of a revised set of attribute-value pairs includes organizing the attribute-value pairs by more general attribute-value pairs.

69. The method of claim 66, wherein the step of providing a revised display includes adding an attribute previously unrepresented in the display.

70. The method of claim 58, further including the steps of accepting an additional selected attribute-value pair and obtaining an additional result navigation state associated with the selected attribute-value pair and the additional selected attribute-value pair.

71. The method of claim 70, wherein the additional selected attribute-value pair is associated with a different attribute than the selected attribute-value pair.

72. The method of claim 58, further including the step of displaying a list of previously selected attribute-value pairs.

73. The method of claim 72, further including the steps of accepting the deselection of a selected attribute-value pair and obtaining a revised result navigation state.

74. A method for enabling a user to browse a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, some of the attribute-value pairs refining other of the attribute-value pairs, a plurality of navigation states, each navigation state corresponding to an expression of particular attribute-value pairs and to a particular subset of materials, an interface providing a plurality of transitions, each transition providing a direct path between two of the navigation states, wherein each transition represents a change from the expression of attribute-value pairs corresponding to an originating navigation state to the expression 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, there being more than one path between at least a first of the navigation states and a second of the navigation states, comprising the steps of:

displaying a free-text search box;

accepting a search term entered in the free-text search box;

determining the attribute-value pairs that match the search term;

displaying the matching attribute-value pairs for the search term;

accepting a selection of a matching attribute-value pair; and

entering a navigation state having a corresponding expression that relates to the selection of the matching attribute-value pair.

75. A method for providing an information navigation system, the information navigation system including a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, some of the attribute-value pairs refining other of the attribute-value pairs, a plurality of navigation states, each navigation state corresponding to a particular expression of attribute-value pairs and to a particular subset of the materials, comprising the steps of:

computing the navigation states;

storing the navigation states in a data structure;

providing an interface to the information navigation system, the interface providing a plurality of transitions, each transition providing a direct path between two of the navigation states, wherein each transition represents a change from the expression of attribute-value pairs corresponding to an originating navigation state to the expression 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, there being more than one path between at least a first of the navigation states and a second of the navigation states;

accepting a query to the navigation system; and

returning a responsive navigation state by retrieving a responsive precomputed navigation state or computing a responsive navigation state.

76. The method of claim 75, wherein the data structure is a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions.

77. A method of providing an information navigation system, the information navigation system including a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, some of the attribute-value pairs refining other of the attribute-value pairs, a plurality of navigation states, each navigation state corresponding to a particular expression of attribute-value pairs and to a particular subset of the materials, comprising the steps of:

generating a partial set of pre-computed navigation states;

storing the partial set of pre-computed navigation states;

providing an interface to the information navigation system, the interface providing a plurality of transitions, each transition providing a direct path between two of the navigation states, wherein each transition represents a change from the expression of attribute-value pairs corresponding to an originating navigation to the expression 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, there being more than one path between at least a first of the navigation states and a second of the navigation states;

accepting a query to the navigation system; and

returning a responsive navigation state by retrieving a responsive precomputed navigation state or computing a responsive navigation state.

78. The method of claim 77, wherein the step of returning a responsive navigation state includes returning a navigation state computed by a plurality of servers acting in parallel.

79. The method of claim 78, further including the step of partitioning the materials among the plurality of servers.

80. The method of claim 79, wherein the plurality of servers are nested hierarchically.

81. The method of claim 80, wherein a root server of the plurality of servers acts as a master server and some of the plurality of servers act as slave servers, further including the steps of the master server distributing a request for a navigation state on to a plurality of slave servers, the slave servers computing navigation states for those requests and returning the results to the master server, and the master server combining the results from the slave servers to obtain a navigation state corresponding to the request.

82. The method of claim 81, wherein the combining step includes computing least common ancestors of attribute-value pairs corresponding to the navigation states returned by the slave servers.

83. A method of providing an information navigation system, the information navigation system including a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, some of the attribute-value pairs refining other of the attribute-value pairs, a plurality of navigation states, each navigation state corresponding to a particular expression of attribute-value pairs and to a particular subset of the materials, comprising the steps of:

storing the navigation states in an implicit representation;

providing an interface to the navigation system, the interface providing a plurality of transitions, each transition providing a direct path between two of the navigation states, wherein each transition represents a change from the expression of attribute-value pairs corresponding to an originating navigation state to the expression 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, there being more than one path between at least a first of the navigation states and a second of the navigation states;

accepting a query to the navigation system;

generating a responsive navigation state from the implicit representation; and

presenting the responsive navigation state.

84. The method of claim 83, wherein the step of generating a responsive navigation state includes computing a responsive navigation state using a plurality of servers acting in parallel.

85. The method of claim 84, further including the step of partitioning the materials among the plurality of servers.

86. The method of claim 85, wherein the plurality of servers are nested hierarchically.

87. The method of claim 86, wherein a root server of the plurality of servers acts as a master server and some of the plurality of servers act as slave servers, further including the steps of the master server distributing a request for a navigation state on to a plurality of slave servers, the slave servers computing navigation states for those requests and returning the results to the master server, and the master server combining the results from the slave servers to obtain a navigation state corresponding to the request.

88. The method of claim 87, wherein the combining step includes the computation of least common ancestors of attribute-value pairs corresponding to the navigation states returned by the slave servers.

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

90. A method for profiling a user of a navigation system, comprising the steps of:

providing a navigation system, the navigation system including a set of materials, a plurality of attributes characterizing the materials, a plurality of values describing the materials, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, some of the attribute-value pairs refining other of the attribute-value pairs, a plurality of navigation states, each navigation state corresponding to a particular expression of attribute-value pairs and to a particular subset of the materials, and an interface providing a plurality of transitions, each transition providing a direct path between two of the navigation states, wherein each transition represent a change from the expression of attribute-value pairs corresponding to an originating navigation state, wherein a series of one or more transitions provides a path between any two navigation states, there being more than one path between at least a first of the navigation states and a second of the navigation states, the transitions being selectable by attribute-value pairs;

accepting the user'"'"'s selection of attribute-value pairs to navigate through the plurality of navigation states; and

tracking the user'"'"'s selection of attribute-value pairs.

91. The method of claim 90, further including the step of developing a user profile based on the user'"'"'s selection of attribute-value pairs.

92. The method of claim 91, wherein the step of developing a user profile further includes the step of supplementing the user profile based on the attribute-value pairs corresponding to the navigation states visited by the user.

93. A computer program product, residing on a computer readable medium, for use in navigating a set of materials, in which the materials are characterized by a plurality of attributes, and the materials are described by a plurality of values, each of the values having an association with at least one of the attributes, each association defining an attribute-value pair, some of the attribute-value pairs refining other of the attribute value pairs, the computer program product comprising instructions for causing a computer to:

define a plurality of navigation states, each navigation state corresponding to a particular expression of attribute-value pairs and to a particular subset of the materials;

provide an interface, the interface providing a plurality of transitions, each transition providing a direct path between two of the navigation states, wherein each transition represents a change from the expression of attribute-value pairs corresponding to an originating navigation state to the expression 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, there being more than one path between at least a first of the navigation states and a second of the navigation states;

accept a selection of a transition; and

provide a result navigation state associated with the selected transition.