System and method for budgeted generalization search in hierarchies

• US 7,991,769 B2
• Filed: 07/07/2006
• Issued: 08/02/2011
• Est. Priority Date: 07/07/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Olston, Christopher, Ravikumar, Shanmugasundaram, Tomkins, Andrew, Josifovski, Vanja, Fontoura, Marcus Felipe
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Rahman; Mohammad N
• Application Number:
  US11/483,048
• Publication Number:
  US 20080010251A1
• Time in Patent Office: 1,852 Days
• Field of Search: 707/718, 707/719, 707/722, 707/728, 707/713
• US Class Current: 707/719
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

An improved system and method is provided for searching a collection of objects that may be located in hierarchies of auxiliary information for retrieval of response objects. A framework to perform a generalization search in hierarchies may be used to generalize a search by moving up to a higher level in a hierarchy of taxonomies or to specialize a search by moving down to a lower level in the hierarchy of taxonomies. Once the system may decide to enumerate response objects at a particular level of generalization, a budgeted generalization search may be used for enumerating a set of response objects within a budgeted cost.

Claims

1. A method comprising:

receiving a query identifying auxiliary information comprising independent taxonomies arranged as trees;

generating a plurality of queries from the received query;

retrieving a plurality of documents having both textual content and located within hierarchies of the auxiliary information to retrieve response objects matching at least one keyword of the query and matching at least one location in first and second trees, wherein the at least one location is associated with at least one response object;

annotating each of the plurality of the documents with a generalization cost of performing the query; and

performing a budgeted generalization search by;

executing the plurality of queries on the plurality of documents to locate response objects by directing a search through levels of hierarchies of the taxonomies to find the response objects matching keywords of the query and also matching the taxonomies of the first and the second trees;

listing the response objects having the generalization cost falling within a budgeted cost; and

ranking the response objects by the generalization cost;

wherein the method is performed by one or more processors.

2. The method of claim 1, wherein the generalization cost is based on a first metric and a second metric, the first metric describing a distance between two nodes in the first tree, the second metric describing a distance between two nodes in the second tree.

3. The method of claim 2, wherein the two nodes of the first tree have a parent child relationship.

4. The method of claim 2, wherein the plurality of queries include a first query and a second query, the first query identifying the two nodes of the first tree, the second query identifying the two nodes of the second tree.

5. The method of claim 1, wherein generating the plurality of queries comprises:

identifying a plurality of nodes along a path between the two nodes of the first tree, the plurality of nodes including the two nodes;

for each of the plurality of nodes, identifying a corresponding node in the second tree that, when combined in a query with one of the two nodes from the first tree, produces a query with the generalization cost equal to the budgeted cost.

6. The method of claim 2, wherein the first metric is a weighted metric.

7. The method of claim 1, wherein generating the plurality of queries comprises performing a standard greedy algorithm.

8. The method of claim 1, wherein ranking the response objects further comprises ranking each of the documents based on a static score, a text score and the generalization cost.

9. The method of claim 1, wherein the generalization cost corresponding to a particular document in the plurality of documents corresponds to the generalization cost of a particular node containing the particular document.

10. The method of claim 1, wherein the plurality of documents includes documents corresponding to nodes in both the first and second trees.

11. The method of claim 1, wherein the retrieving step further comprises initializing a level in the hierarchies from which to retrieve the plurality of the documents.

12. A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, causes the processors to perform:

receiving a query identifying auxiliary information comprising independent taxonomies arranged as trees;

generating a plurality of queries from the received query;

retrieving a plurality of documents having both textual content and located in hierarchies of the auxiliary information to retrieve response objects matching at least one keyword of the query and matching at least one location in first and second trees, wherein the at least one location is associated with at least one response object;

annotating each of the plurality of the documents with a generalization cost of performing the query;

performing a budgeted generalization search by;

executing the plurality of queries on the plurality of documents to locate response objects by directing the budgeted generalization search through levels of hierarchies of the taxonomies to find the response objects matching keywords of the query and also matching the taxonomies of the first and the second trees;

listing only the response objects having the generalization cost falling within a budgeted cost; and

ranking the response objects by the generalization cost.

13. The non-transitory computer-readable medium of claim 12 wherein the generalization cost is based on a first metric and a second metric, the first metric describing a distance between two nodes in the first tree, the second metric describing a distance between two nodes in the second tree.

14. The non-transitory computer-readable medium of claim 13, wherein the two nodes of the first tree have a parent child relationship.

15. The non-transitory computer-readable medium of claim 13, wherein the plurality of queries include a first query and a second query, the first query identifying the two nodes of the first tree, the second query identifying the two nodes of the second tree.

16. The non-transitory computer-readable medium of claim 12, wherein generating the plurality of queries comprises:

identifying a plurality of nodes along a path between the two nodes of the first tree, the plurality of nodes including the two nodes;

for each of the plurality of nodes, identifying a corresponding node in the second tree that, when combined in a query with one of the two nodes from the first tree, produces a query with a generalization cost equal to the budgeted cost.

17. The non-transitory computer-readable medium of claim 13, wherein the first metric is a weighted metric.

18. The non-transitory computer-readable medium of claim 12, wherein generating the plurality of queries comprises performing a standard greedy algorithm.

19. The non-transitory computer-readable medium of claim 12, wherein ranking the response objects comprises ranking each of the documents in the plurality of documents, wherein a particular document in the plurality of documents is ranked based on a static score for the particular document, a text score for the particular document and the generalization cost for the particular document.

20. The non-transitory computer-readable medium of claim 12, wherein the generalization cost corresponding to a particular document in the plurality of documents corresponds to the generalization cost of a particular node containing the particular document.

21. The non-transitory computer-readable medium of claim 12, wherein the plurality of documents includes documents corresponding to nodes in both the first and second trees.

22. The non-transitory computer-readable medium of claim 12, wherein the retrieving step further comprises initializing a level in the hierarchies from which to retrieve the plurality of the documents.