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

• US 8,019,752 B2
• Filed: 11/10/2005
• Issued: 09/13/2011
• 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: Tucker, Michael, Walter, John S., Tunkelang, Daniel, Myatt, Jason Paul, Wang, Joyce, Scarlet, Benjamin S., Mohta, Vinay Seth, Knabe, Frederick C., Ferrari, Adam J.
• Primary Examiner(s): Vo; Tim T
• Assistant Examiner(s): GORTAYO, DANGELINO N
• Application Number:
  US11/271,036
• Publication Number:
  US 20070106658A1
• Time in Patent Office: 2,133 Days
• Field of Search: 707/1, 707/2, 707/3, 707/5, 707/100, 707/102, 707/200, 707/763, 707/765, 707/774, 707/706, 707/722, 707/776, 707/796
• US Class Current: 707/722
• 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, wherein each of the stored plurality of objects comprises an object identifier and a set of attribute-value pairs that characterize the object, wherein each value of the set of attribute-value pairs describes its respective object, and wherein at least one of the set of the attribute-value pairs includes a reference that identifies at least one respective relationship to another object of the stored plurality of objects, wherein the reference is stored as a value of the at least one of the set of the attribute-value pairs, wherein the another object is one of the stored plurality of objects, and the another object comprises a respective object identifier and a set of attribute-value pairs that characterize the another object, at least one of the set of attribute-value pairs including a reference that identifies at least one respective relationship to an object of the stored plurality of objects wherein the reference is stored as a value of the at least one of the set of the attribute-value pairs;

compute a first navigation state in response to a first query, the first navigation state corresponding to a first set of objects from the stored plurality of objects, wherein each object of the first set of objects includes the attribute-value pairs that characterize the object and the at least one respective relationship;

define, a first subset of objects from the first set of objects, wherein at least one object in the first subset includes the reference that identifies the at least one respective relationship to one or more objects in a second set of objects, wherein each object of the second set of objects includes the attribute-value pairs that characterize the object and the at least one respective relationship, and wherein at least one object in the second set of objects is distinct from the first subset of objects;

access, responsive to a user request to determine at least one possible refinement to the first navigation state, at least one object in the second set of objects, based on the reference that identifies the at least one respective relationship to another object, and obtain at least one attribute-value pair that characterizes the at least one object in the second set of objects; and

present in a user interface, the at least one possible refinement to the first navigation state based on the at least one attribute-value pair that characterizes the at least one object in the second 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 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.

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 execute a set of candidate queries and select the at least one possible refinement from the results of executing the set of candidate queries.

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 compute a set of possible refinements based on analyzing an enumeration of at least some of the objects corresponding to the first navigation state.

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:

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.

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

10. The computer program product of claim 1, wherein the instructions for causing the computer to present the at least one possible refinement include instructions for causing the computer to:

define a third set of objects that is a subset of the second set of objects, wherein each object in the third set of objects includes the at least one attribute value-pair that characterizes the at least one object in the second set of objects; and

present the at least one possible refinement based on the third set of objects.

11. The computer program product of claim 10, wherein the instructions for causing the computer to 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 a fourth set of objects is defined from a fifth set of objects, the fifth set of objects being a subset of the fourth set of objects, wherein each object in the fifth set is referenced by the third set of objects.

12. The computer program product of claim 1, wherein the instructions for causing the computer to present the at least one possible refinement include instructions for causing the computer to 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 the fourth set of objects is defined from a fifth set of objects, the fifth set of objects being a subset of the fourth set of objects, and wherein each object in the fifth set is referenced by the at least one object in the second set of objects having the at least one attribute-value pair.

13. The computer program product of claim 1, wherein the first set of objects is different from the second set of objects.

14. The computer program product of claim 1, wherein the value for at least one of the attribute-value pairs is null.

15. 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, each of the objects having associated attribute-value pairs that characterize the object wherein each value of the associated attribute-value pairs describes its respective object, wherein, for each relationship between a pair of objects, an attribute-value pair of a first object of the pair of objects includes a reference that identifies a respective relationship to a second object of the pair of objects, wherein the reference is stored as a value of the attribute-value pair, wherein the first and second objects are from the stored 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 stored plurality of objects, wherein the objects in the first set of objects include the attribute-value pairs that characterize the objects, and at least one respective relationship;

define a first subset of the first set of objects, wherein at least one object in the first subset includes the reference that identifies the at least one respective relationship to one or more objects in a second set of objects;

access, responsive to a user request to determine at least one possible refinement to the first navigation state, at least one object in the second set of objects, based on the reference that identifies the at least one respective relationship to the one or more objects in the second set of objects and obtain at least one attribute-value pair associated with the at least one object in the second set of objects;

present in a user interface, responsive to the user request, at least one possible refinement to the first navigation state based on the at least one attribute-value pair associated with the at least one object in the second set of objects, 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 each object in the third set of objects including a reference that identifies at least one respective relationship to at least one object in the second set of objects, wherein the third set of objects includes a least one object distinct from the first subset 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 respective relationship to one or more objects in the third set of objects.

16. The computer program product of claim 15, 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 respective relationship to one or more objects in the fifth set of objects.

17. A computer implemented 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, each of the objects having associated attribute-value pairs that characterize the object wherein each value of the associated attribute-value pairs describes its respective object, wherein, for each relationship between a pair of objects, an attribute-value pair of a first object of the pair of objects includes a reference that identifies a respective relationship to a second object of the pair of objects, wherein the reference is stored as a value of the attribute-value pair, wherein the first and second objects are from the stored 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 stored plurality of objects, wherein the objects in the first set of objects include the attribute-value pairs that characterize the objects, and at least one respective relationship;

defining a subset of the first set of objects, wherein at least one object in the subset includes the reference that identifies the at least one respective relationship to one or more objects in a second set of objects;

accessing, responsive to a user request to determine at least one possible refinement to the first navigation state, at least one object in the second set of objects, based on the reference that identifies the at least one respective relationship to the one or more objects in the second set of objects and obtaining at least one attribute-value pair associated with the at least one object in the second set of objects;

presenting in a user interface, responsive to the user request, at least one possible refinement to the first navigation state based on the at least one attribute-value pair associated with the at least one object in the second set of objects, wherein the second set of objects includes at least one object distinct from the subset of objects, 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 each object in the third set of objects including a reference identifies at least one respective relationship to at least one object in 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 respective relationship to one or more objects in the third set of objects.

18. The method of claim 17, wherein the plurality of objects include objects of a plurality of types.

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

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

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

22. The method of claim 19, wherein at least one of the plurality of values is a numerical value.

23. The method of claim 19, wherein at least one of the plurality of values is a categorical value.

24. The method of claim 19, wherein at least one of the plurality of values is a textual value.

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

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

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

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

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

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

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

32. The method of claim 19, further comprising presenting at least one 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.

33. The method of claim 19, further comprising presenting at least one 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.

34. 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, each of the objects having associated attribute-value pairs that characterize the object, wherein each value of the associated attribute-value pairs describes its respective object, wherein, for each relationship between a pair of objects, a value of an attribute-value pair of a first object of the pair of objects refers to a second object of the pair of objects, wherein the first and second objects are from the stored 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 stored plurality of objects, wherein the objects in the first set of objects include the attribute-value pairs that characterize the objects, and the attribute-value pairs include at least one relationship between a pair of objects;

defining a subset of the first set of objects, wherein at least one object in the subset includes the at least one of the stored plurality of relationships as the value of attribute-value pair that refers to one or more objects in a second set of objects;

accessing, responsive to a user request to determine at least one possible refinement to the first navigation state, at least one object in the second set of objects, based on the at least one of the stored plurality of relationships stored as the value of attribute-value pair that refers to one or more objects in a second set of objects and obtaining at least one attribute-value pair associated with the at least one object in the second set of objects;

presenting in a user interface, responsive to the user request, a possible refinement to the first navigation state based on the at least one attribute-value pair associated with the at least one object in the second set of objects, 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 each object in the third set of objects being characterized by the at least one attribute-value pair with a value that refers to the at least one object in the second set of objects, wherein the third set of objects includes at least one object distinct from the first subset 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 as the value of attribute-value pair that refers to one or more objects in the third set of objects.

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

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