Hierarchical data-driven navigation system and method for information retrieval

• US 7,035,864 B1
• Filed: 05/18/2000
• Issued: 04/25/2006
• Est. Priority Date: 05/18/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Corporation
• Original Assignee: Endeca Technologies Incorporated (Oracle Corporation)
• Inventors: Johnson, Keith, Walter, John S., Knabe, Frederick C., Ferrari, Adam J., Gourley, David, Tunkelang, Daniel
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): PHAM, HUNG Q
• Application Number:
  US09/573,305
• Time in Patent Office: 2,168 Days
• Field of Search: 707/7, 707/2, 707/10, 707/102, 707/3, 707/4, 707/5, 715/713
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/3323 using document space presentation or visualization, e.g. category, hierarchy or range presentation and selection
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: Y10S 707/962 Entity-attribute-value
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact 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.

Claims

1. A computer-implemented method for retrieving information associated with a set of materials, the method comprising:

storing a plurality of attribute-value pairs associated with the materials, wherein each of a plurality of values has an association with at least one of a plurality of attributes characterizing the materials, and

computing a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consists of those materials that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;

wherein within the plurality of computed navigation states, at least

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

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

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 that the third attribute characterizes;

storing the computed navigation states in a data structure;

providing an interface, 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 each transition represents a change from the 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 a series of one or more transitions provides a path between any two navigation states, and wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state;

accepting a query directed at the materials; and

retrieving a stored navigation state responsive to the query.

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

3. A computer-implemented method for retrieving information associated with a set of materials, the method comprising:

storing in a first data structure a plurality of attribute-value pairs associated with the materials, wherein each of a plurality of values has an association with at least one of a plurality of attributes characterizing the materials, and

wherein the first data structure allows computing dynamically a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consists of those materials in the navigation system that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;

wherein within the plurality of navigation states, at least

a first navigation state 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,

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

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;

generating a set of pre-computed navigation states;

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

providing an interface, 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 each transition represents a change from the 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, and wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state;

accepting a query directed at the materials; and

in response to the query, retrieving a stored pre-computed navigation state or dynamically computing one of the plurality of navigation states using the first data structure.

4. A computer-implemented method for retrieving information associated with a set of materials, the method comprising:

storing in a data structure a plurality of attribute-value pairs associated with the materials, wherein each of a plurality of values has an association with at least one of a plurality of attributes characterizing the materials, and

in response to a plurality of sequential queries, computing dynamically at run time a plurality of navigation states using the data structure, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consists of those materials in the navigation system that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;

wherein within the plurality of computed navigation states, at least

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

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

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 that the third attribute characterizes;

providing an interface, 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 each transition represents a change from the 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 a series of one or more transitions provides a path between any two navigation states, and wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state; and

presenting in response to each query a computed navigation state.

5. The method of claim 4, further including the step of storing the dynamically computed navigation state in a cache.

6. The method of claim 4, 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.

7. The method of claim 4, 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.

8. The method of claim 4, 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 corresponding set of attribute-value pairs for the originating navigation state.

9. The method of claim 4, 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.

10. The method of claim 4, 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.

11. The method of claim 4, 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.

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

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

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

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

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

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

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

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

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

21. The method of claim 4, 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.

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

23. The method of claim 4, 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.

24. The method of claim 4, further comprising storing a profile for each of the materials in the set of materials, the profile including a set of attribute-value pairs.

25. The method of claim 24, the profile further including descriptive information.

26. The method of claim 4, the interface including a human user interface.

27. The method of claim 4, the interface including an application program interface.

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

29. The method of claim 4, wherein the interface operates in an XML-based environment.

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

31. The method of claim 4, the interface including a free-text search tool for searching the attributes.

32. The method of claim 4, the interface including a free-text search tool for searching the values.

33. The method of claim 4, further including storing 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.

34. The method of claim 4, the interface including access to the materials in the set of materials.

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

36. The method of claim 35, 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.

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

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

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

40. The method of claim 4, 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.

41. The method of claim 40, 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.

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

43. The method of claim 41, 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.

44. The method of claim 41, wherein the presentation organizes the navigation options by attribute.

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

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

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

48. The method of claim 41, the navigation options including deselection of attribute-value pairs from the set of attribute-value pairs corresponding to the current navigation state.

49. The method of claim 41, the navigation options further including a link to an associated navigation state.

50. The method of claim 49, wherein the associated navigation state is a generalization of the present navigation state.

51. The method of claim 49, wherein the associated navigation state is a refinement of the present navigation state.

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

53. A computer program product, residing on a computer-readable medium, for use in retrieving information associated with a set of materials, the computer program product comprising instructions for causing a computer to:

store a plurality of attribute-value pairs associated with the materials, wherein each of a plurality of values has an association with at least one of a plurality of attributes characterizing the materials; and

compute a plurality of navigation states, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consists of those materials that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;

wherein within the plurality of computed navigation states, at least

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

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

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 that the third attribute characterizes;

store the computed navigation states in a data structure;

provide an interface, 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 each transition represents a change from the 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 a series of one or more transitions provides a path between any two navigation states, and wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state;

accept a query directed at the materials; and

retrieve a stored navigation state responsive to the query.

54. A computer program product, residing on a computer-readable medium, for use in retrieving information associated with a set of materials, the computer program product comprising instructions for causing a computer to:

store in a data structure a plurality of attribute-value pairs associated with the materials, wherein each of a plurality of values has an association with at least one of a plurality of attributes characterizing the materials; and

in response to a plurality of sequential queries, compute dynamically at run time a plurality of navigation states using the data structure, each navigation state corresponding to a particular set of attribute-value pairs and to a particular subset of the materials, wherein for each navigation state the particular subset of the materials corresponding to the navigation state consists of those materials that are each described by every attribute-value pair in the particular set of attribute-value pairs corresponding to that navigation state;

wherein within the plurality of navigation states, at least

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

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

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 that the third attribute characterizes;

provide an interface, 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 each transition represents a change from the 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 a series of one or more transitions provides a path between any two navigation states, and wherein the interface provides a direct path, with no intervening navigation states, between the first navigation state and the second navigation state; and

present in response to each query a computed navigation state.