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

• US 7,617,184 B2
• Filed: 09/21/2001
• Issued: 11/10/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: Gourley, David, Walter, John, Ferrari, Adam, Knabe, Frederick, Lau, Andrew, Mohta, Vinay, Johnson, Keith, Tunkelang, Daniel
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US09/961,131
• Publication Number:
  US 20020051020A1
• Time in Patent Office: 2,972 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/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 method for presenting materials corresponding to a navigation state, the method comprising:

receiving a user selection of an expression of attribute-value pairs;

producing a plurality of refinement options and a plurality of ancestors by processing, in each server of a plurality of servers, the expression of attribute-value pairs to produce at least one refinement option and at least one ancestor;

combining the plurality of refinement options and plurality of ancestors to form combined refinement options, the combined refinement options including at least one refinement navigation state;

determining the navigation state associated with the expression of attribute-value pairs;

providing materials associated with the navigation state; and

providing the combined refinement options,

wherein the combining comprises;

taking a union of the plurality of refinement options, determining a set of ancestors for each refinement option of the plurality of refinement options, from the plurality of ancestors produced in the plurality of servers, to form sets of ancestors, computing an intersection of all of the sets of ancestors, and computing the combined refinement options based on terms in the intersection of all sets of ancestors, including identifying at least two related terms among the plurality of refinement options, and computing, for the at least two related terms, a least common ancestor of the related terms, and

wherein a first server of the plurality of servers acts as a master server and some of the plurality of servers act as slave servers, the method further comprising the master server distributing a request for a navigation state to a plurality of slave servers, the slave servers computing navigation states for requests and returning 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, wherein the combining of the results is based on the combining of the plurality of refinement options and plurality of ancestors.

2. The method of claim 1, wherein the least common ancestor is defined by a partial order among the related terms.

3. The method of claim 1, wherein computing the least common ancestor of the related terms comprises storing all non-leaf terms on at least one server.

4. The method of claim 3, wherein the at least one server is a master server.

5. The method of claim 1, wherein the plurality of servers are slave servers, and wherein combining the plurality of refinement options includes storing a plurality of the attribute-value pairs on a master server.

6. The method of claim 1, wherein combining the plurality of refinement options is performed whether the plurality of refinement options are conjunctive, disjunctive, or negational.

7. The method of claim 1, wherein combining the plurality of refinement options comprises combining the plurality of refinement options as a disjoint union.

8. The method of claim 1, wherein the expression of attribute-value pairs is processed on a different partition of a collection of materials for different ones of the plurality of servers.

9. The method of claim 1, further comprising storing the attribute-value pairs in a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions.

10. The method of claim 1, further comprising partitioning the materials and other materials among the plurality of servers.

11. The method of claim 10, further comprising nesting the plurality of servers hierarchically.

12. The method of claim 1, further comprising storing the navigation state in a cache.

37. The method of claim 1, further comprising storing at least a portion of the plurality of ancestors produced in the plurality of servers in a cache.

38. The method of claim 37, wherein at least one of the sets of ancestors is determined from the plurality of ancestors stored in the cache.

13. A computer-readable storage medium storing computer-executable instructions that, when executed by a computer, cause the computer to perform a method for presenting materials corresponding to a navigation state, the method comprising:

receiving a user selection of an expression of attribute-value pairs;

producing a plurality of refinement options and a plurality of ancestors by processing, in each server of a plurality of servers, the expression of attribute-value pairs to produce at least one refinement option and at least one ancestor;

combining the plurality of refinement options and plurality of ancestors to form combined refinement options, the combined refinement options including at least one refinement navigation state;

determining the navigation state associated with the expression of attribute-value pairs;

providing materials associated with the navigation state; and

providing the combined refinement options,

wherein the combining comprises;

taking a union of the plurality of refinement options, determining a set of ancestors for each refinement option of the plurality of refinement options, from the plurality of ancestors produced in the plurality of servers, to form sets of ancestors, computing an intersection of all of the sets of ancestors, and computing the combined refinement options based on terms in the intersection of all sets of ancestors, including identifying at least two related terms among the plurality of refinement options, and computing, for the at least two related terms, a least common ancestor of the related terms, and

wherein a first server of the plurality of servers acts as a master server and some of the plurality of servers act as slave servers, the method further comprising the master server distributing a request for a navigation state to a plurality of slave servers, the slave servers computing navigation states for requests and returning 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, wherein the combining of the results is based on the combining of the plurality of refinement options and plurality of ancestors.

14. The computer-readable storage medium of claim 13 wherein the least common ancestor is defined by a partial order among the related terms.

15. The computer-readable storage medium of claim 13, wherein computing the least common ancestor of the related terms comprises storing all non-leaf terms on at least one server.

16. The computer-readable storage medium of claim 15, wherein the at least one server is a master server.

17. The computer-readable storage medium of claim 13, wherein the plurality of servers are slave servers, and wherein combining the plurality of refinement options includes storing a plurality of the attribute-value pairs on a master server.

18. The computer-readable storage medium of claim 13, wherein combining the plurality of refinement options is performed whether the plurality of refinement options are conjunctive, disjunctive, or negational.

19. The computer-readable storage medium of claim 13, wherein combining the plurality of refinement options comprises combining the plurality of refinement options as a disjoint union.

20. The computer-readable storage medium of claim 13, wherein the expression of attribute-value pairs is processed on a different partition of a collection of materials for different ones of the plurality of servers.

21. The computer-readable storage medium of claim 13, wherein the method further comprises storing the attribute-value pairs in a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions.

22. The computer-readable storage medium of claim 13, wherein the method further comprises partitioning the materials and other materials among the plurality of servers.

23. The computer-readable storage medium of claim 22, wherein the method further comprises nesting the plurality of servers hierarchically.

24. The computer-readable storage medium of claim 13, wherein the method further comprises storing the navigation state in a cache.

39. The computer-readable storage medium of claim 13, further comprising storing at least a portion of the plurality of ancestors produced in the plurality of servers in a cache.

40. The computer-readable storage medium of claim 39, wherein at least one of the sets of ancestors is determined from the plurality of ancestors stored in the cache.

25. A system for presenting materials corresponding to a navigation state, comprising:

at least one server that includes a computer readable storage medium for storing the materials, wherein the at least one server;

receives a user selection of an expression of attribute-value pairs; and

produces at least one refinement option by processing the expression of attribute-value pairs;

at least one other server that;

receives a user selection of an expression of attribute-value pairs;

produces at least one refinement option by processing the expression of attribute-value pairs, wherein the at least one refinement option produced by the at least one server and the at least one refinement option produced by the at least one other served form a plurality of refinement options;

combines the plurality of refinement options and plurality of ancestors to form combined refinement options, the combined refinement options including at least one refinement navigation state;

determines the navigation state associated with the expression of attribute-value pairs;

provides materials associated with the navigation state; and

provides the combined refinement options, wherein when the at least one server combines the plurality of refinement options, the at least one server;

takes a union of the plurality of refinement options,

determines a set of ancestors for each refinement option of the plurality of refinement options, from the plurality of ancestors produced in the plurality of servers, to form sets of ancestors,

computes an intersection of all of the sets of ancestors, and computes the combined refinement options based on terms in the intersection of all sets of ancestors, including identifying at least two related terms among the plurality of refinement options, and computing, for the at least two related terms, a least common ancestor of the related terms, and

wherein at least one of at least one other servers acts as a master server;

the at least one server includes a plurality of servers, and the plurality of servers act as slave servers;

the master server distributes a request for a navigation state to the slave servers;

the slave servers compute navigation states for requests and return results to the master server based on the combining; and

the master server combines the results from the plurality of slave servers to obtain a navigation state corresponding to the request, wherein the combining of the results is based on the combining of the plurality of refinement options and plurality of ancestors.

26. The system of claim 25, wherein the least common ancestor is defined by a partial order among the related terms.

27. The system of claim 25, wherein computing the least common ancestor of the related terms comprises storing all non-leaf terms the at least one of the at least one server and the at least one other server.

28. The system of claim 27, wherein the at least one of the at least one server and the at least one other server is a master server.

29. The system of claim 25, wherein the at least one server is a slave server, and wherein combining the plurality of refinement options includes storing a plurality of the attribute-value pairs on a master server.

30. The system of claim 25, wherein combining the plurality of refinement options is performed whether the plurality of refinement options are conjunctive, disjunctive, or negational.

31. The system of claim 25, wherein combining the plurality of refinement options comprises combining the plurality of refinement options as a disjoint union.

32. The system of claim 25, wherein the expression of attribute-value pairs is processed on a different partition of a collection of materials for different ones of the at least one server and the at least one other server.

33. The system of claim 25, wherein the attribute-value pairs are stored in a graph data structure including nodes and edges between nodes, the nodes representing navigation states, the edges representing transitions.

34. The system of claim 25, wherein the materials and other materials are partitioned among the at least one server and the at least one other server.

35. The system of claim 34, wherein the at least one server and the at least one other server are nested hierarchically.

36. The system of claim 25, further comprising storing the navigation state in a cache.

41. The system of claim 25, wherein the at least one server stores at least a portion of the plurality of ancestors produced in the plurality of servers in a cache.

42. The system of claim 25, wherein at least one of the sets of ancestors is determined from the plurality of ancestors stored in cache.