System and method for information retrieval from object collections with complex interrelationships

• US 20070106658A1
• Filed: 11/10/2005
• Published: 05/10/2007
• Est. Priority Date: 11/10/2005
• Status: Active Grant

• Current Assignee: Oracle OTC Subsidiary LLC (Oracle Corporation)
• Original Assignee: Endeca Technologies Incorporated (Oracle Corporation)
• Inventors: Tunkelang, Daniel, Wang, Joyce, Walter, John, Ferrari, Adam, Knabe, Frederick, Mohta, Vinay, Myatt, Jason, Scarlet, Benjamin
• Granted Patent: US 8,019,752 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/908 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A data-driven information navigation system and method enable search and analysis of a set of objects or other materials by certain common attributes that characterize the materials, as well as by relationships among the materials. The invention includes several aspects of a data-driven information navigation system that employs this navigation mode. The navigation system of the present invention includes features of a knowledge base, a navigation model that defines and enables computation of a collection of navigation states, a process for computing navigation states that represent incremental refinements relative to a given navigation state, and methods of implementing the preceding features.

Claims

1. A computer program product, residing on a computer-readable medium, for use in navigating through information associated with a plurality of objects, the computer program product comprising instructions for causing a computer to:

access a stored plurality of objects and a stored plurality of relationships between pairs of objects from the plurality of objects;

compute a first navigation state in response to a first query, the first navigation state corresponding to a first set of objects from the plurality of objects, wherein each object in a first subset of the first set of objects has at least one of the stored plurality of relationships with one or more objects in a second set of objects;

present at least one possible refinement to the first navigation state, a first possible refinement corresponding to a third set of objects, the third set of objects being a subset of the second set of objects; and

compute a second navigation state that refines the first navigation state, the second navigation state corresponding to a fourth set of objects from the plurality of objects, wherein each object in a subset of the fourth set of objects has at least one of the stored plurality of relationships with one or more objects in the third set of objects.

2. The computer program product of claim 1, wherein the instructions for causing a computer to present at least one possible refinement include instructions for causing a computer to present at least one possible refinement based at least in part on a text-based query.

3. The computer program product of claim 1, wherein the instructions for causing a computer to present at least one possible refinement include instructions for causing a computer to present at least one possible refinement based at least in part on a range-based query.

4. The computer program product of claim 1, wherein the instructions for causing a computer to present at least one possible refinement include instructions for causing a computer to present at least one possible refinement based at least in part on an aggregation of objects.

5. The computer program product of claim 1, wherein the third set of objects results from a negation operation.

6. The computer program product of claim 1, wherein the instructions for causing a computer to present at least one possible refinement to the first navigation state include instructions to present a set of possible refinements using profile information regarding a user querying the information associated with the plurality of objects.

7. The computer program product of claim 1, wherein the instructions for causing a computer to present at least one possible refinement to the first navigation state include instructions to execute a set of candidate queries and select the at least one possible refinement from the results of executing the set of candidate queries.

8. The computer program product of claim 1, wherein the instructions for causing a computer to present at least one possible refinement to the first navigation state include instructions to compute a set of possible refinements based on analyzing an enumeration of at least some of the objects corresponding to the first navigation state.

9. The computer program product of claim 1, wherein the instructions for causing a computer to present at least one possible refinement to the first navigation state include instructions to:

execute a set of candidate queries and analyze an enumeration of at least some of the objects corresponding to the first navigation state; and

select the at least one possible refinement from the results of executing the set of candidate queries and of analyzing the enumeration of at least some of the objects.

10. The computer program product of claim 1, wherein the first subset of the first set of objects coincides with the first set of objects.

11. A computer program product residing on a computer-readable medium, for use in navigating through information associated with a plurality of objects, the computer program product comprising instructions for causing a computer to:

access a stored plurality of objects and a stored plurality of relationships between pairs of objects from the plurality of objects;

compute a first navigation state in response to a first query, the first navigation state corresponding to a first set of objects from the plurality of objects, wherein each object in a first subset of the first set of objects has at least one of the stored plurality of relationships with one or more objects in a second set of objects;

present at least one possible refinement to the first navigation state, a first possible refinement corresponding to a third set of objects, the second set of objects being a subset of the third set of objects; and

compute a second navigation state that refines the first navigation state, the second navigation state corresponding to a fourth set of objects from the plurality of objects, wherein each object in a subset of the fourth set of objects has at least one of the stored plurality of relationships with one or more objects in the third set of objects.

12. The computer program product of claim 11, wherein the instructions for causing a computer to present at least one possible refinement include instructions for causing a computer to present at least one possible refinement based at least in part on a union of the second set of objects and a fifth set of objects, wherein each object in a second subset of the first set of objects has at least one of the stored plurality of relationships with one or more objects in the fifth set of objects.

13. A method for navigating through information comprising:

storing a plurality of objects and a plurality of relationships between pairs of objects from the plurality of objects;

computing a first navigation state in response to a first query, the first navigation state corresponding to a first set of objects from the plurality of objects, wherein each object in a subset of the first set of objects has at least one of the stored plurality of relationships with one or more objects in a second set of objects;

presenting a possible refinement to the first navigation state, the possible refinement corresponding to a third set of objects, the third set of objects being a subset of the second set of objects; and

computing a second navigation state that refines the first navigation state, the second navigation state corresponding to a fourth set of objects from the plurality of objects, wherein each object in a subset of the fourth set of objects has at least one of the stored plurality of relationships with one or more objects in the third set of objects.

14. The method of claim 13, wherein the plurality of objects include objects of a plurality of types.

15. The method of claim 13, further comprising storing a plurality of facet-value pairs associated with the plurality of objects, wherein each of a plurality of values has an association with at least one of a plurality of facets characterizing the objects.

16. The method of claim 15, wherein the values associated with a first facet include a hierarchy of values.

17. The method of claim 16, wherein at least one value has more than one direct parent value.

18. The method of claim 15, wherein some of the plurality of values are numerical values.

19. The method of claim 15, wherein some of the plurality of values are categorical values.

20. The method of claim 15, wherein some of the plurality of values are textual values.

21. The method of claim 15, wherein the values associated with a first facet consist of an enumerated set of values.

22. The method of claim 15, wherein the values associated with a first facet consist of values corresponding to a data type.

23. The method of claim 15, wherein the plurality of objects include objects of a plurality of types and one of the facets has values corresponding to the types.

24. The method of claim 15, wherein a first facet-value pair is associated with the second set of objects and a second facet-value pair is associated with the third set of objects, and wherein the value of the first facet-value pair is a parent of the value of the second facet-value pair.

25. The method of claim 15, wherein storing a plurality of objects and a plurality of relationships between pairs of objects, and storing a plurality of facet-value pairs, collectively includes storing on a plurality of servers.

26. The method of claim 15, further comprising presenting at least some of the first set of objects and/or the fourth set of objects sorted according to one or more precomputed facet values.

27. The method of claim 15, further comprising presenting at least some of the first set of objects and/or the fourth set of objects sorted according to one or more dynamically computed facet values.

28. The method of claim 15, further comprising presenting at least some of the fourth set of objects sorted using a function based on aggregate statistics applied to values associated with a first facet characterizing the third set of objects.

29. The method of claim 15, further comprising presenting at least some of the fourth set of objects sorted using a function based on aggregate statistics applied to values associated with a first facet characterizing the fourth set of objects.

30. A method for navigating through information comprising:

storing a plurality of objects and a plurality of relationships between pairs of objects from the plurality of objects;

computing a first navigation state in response to a first query, the first navigation state corresponding to a first set of objects from the plurality of objects, wherein each object in a subset of the first set of objects has at least one of the stored plurality of relationships with one or more objects in a second set of objects;

presenting a possible refinement to the first navigation state, the possible refinement corresponding to a third set of objects, the second set of objects being a subset of the third set of objects; and

computing a second navigation state that refines the first navigation state, the second navigation state corresponding to a fourth set of objects from the plurality of objects, wherein each object in a subset of the fourth set of objects has at least one of the stored plurality of relationships with one or more objects in the third set of objects.

31. The method of claim 30, wherein a first facet-value pair is associated with the second set of objects and a second facet-value pair is associated with the third set of objects, and wherein the value of the first facet-value pair is a child of the value of the second facet-value pair.

32. The method of claim 30, wherein a first facet-value pair and a second facet-value pair are associated with the second set of objects, the first facet-value pair is associated with the third set of objects, and the second facet-value pair is not associated with the third set of objects.