System and method for budgeted generalization search in hierarchies

• US 20080010251A1
• Filed: 07/07/2006
• Published: 01/10/2008
• 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
• Granted Patent: US 7,991,769 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 computer system for searching a collection of objects having textual content, comprising:

a query processor for providing services for querying the collection of objects having textual content, a plurality of the objects being associated with one or more locations in a plurality of taxonomies;

a budgeted search analysis engine operably coupled to the query processor for finding response objects matching one or more keywords of the query and matching the one or more locations in the plurality of taxonomies within a budgeted cost; and

a cover set analysis engine operably coupled to the budgeted search analysis engine for determining sets of points covering an area within a hierarchy of the plurality of taxonomies bounded by the one or more locations.

2. The system of claim 1 further comprising a cost cover set analysis engine operably coupled to the cover set analysis engine for determining an optimal cost cover set for the area of the hierarchy of the plurality of taxonomies bounded by the one or more locations.

3. The system of claim 1 further comprising a weighted set cover analysis engine operably coupled to the cover set analysis engine for determining a weighted cover set for the area of the hierarchy of the plurality of taxonomies bounded by the one or more locations.

4. The system of claim 1 further comprising a generalization search driver for directing the search through levels of the hierarchy of the plurality of taxonomies to find response objects matching the one or more keywords of the query and matching the one or more locations in the taxonomies.

5. A computer-readable medium having computer-executable components comprising the system of claim 1.

6. A computer-implemented method for searching a collection of objects having textual content, comprising:

receiving a query and one or more locations within a plurality of taxonomies, the one or more locations having at least one associated response object;

determining sets of points covering an area within a hierarchy of the plurality of taxonomies bounded by the one or more locations;

finding a set of points having a total cost no greater than a budgeted cost within the sets of points covering the area within the hierarchy of the plurality of taxonomies bounded by the one or more locations; and

outputting a list of response objects associated with the one or more locations within the set of points having the total cost no greater than the budgeted cost.

7. The method of claim 6 further comprising determining an area within the hierarchy of the plurality of taxonomies bounded by the one or more locations.

8. The method of claim 6 further comprising ranking the list of response objects associated with the one or more locations within the set of points having the total cost no greater than the budgeted cost.

9. The method of claim 8 wherein ranking the list of response objects associated with the one or more locations within the set of points having the cost no greater than the budgeted cost comprises scoring the response objects using a text score for matching the one or more keywords of the query and using a generalization cost for matching the one or more locations within the set of points.

10. The method of claim 6 wherein determining the sets of points covering the area within the hierarchy of the plurality of taxonomies bounded by the one or more locations comprises determining a set of rectangles covering a simplex within the hierarchy of the plurality of taxonomies bounded by the one or more locations.

11. The method of claim 10 wherein finding a set of points having a total cost no greater than a budgeted cost within the sets of points covering the area within the hierarchy of the plurality of taxonomies bounded by the one or more locations comprises applying dynamic programming to iteratively determine a minimal-cost cover for the set of rectangles covering the simplex within the hierarchy of the plurality of taxonomies bounded by the one or more locations.

12. The method of claim 6 wherein determining the sets of points covering the area within the hierarchy of the plurality of taxonomies bounded by the one or more locations comprises determining a weighted set cover for a multi-dimensional grid of points within the hierarchy of the plurality of taxonomies bounded by the one or more locations.

13. The method of claim 12 wherein determining the weighted set cover for the multi-dimensional grid of points within the hierarchy of the plurality of taxonomies bounded by the one or more locations comprises assigning a weight representing a cost to one or more points in the multi-dimensional grid.

14. The method of claim 13 wherein finding the set of points having the total cost no greater than the budgeted cost within the sets of points covering the area within the hierarchy of the plurality of taxonomies bounded by the one or more locations comprises applying a greedy algorithm to adaptively determine a minimal weight set cover for the multi-dimensional grid of points within the hierarchy of the plurality of taxonomies bounded by the one or more locations.

15. A computer-readable medium having computer-executable instructions for performing the method of claim 6.

16. A computer system for searching a collection of objects having textual content, comprising:

means for receiving a query and one or more locations within a plurality of taxonomies, the one or more locations having at least one associated response object;

means for finding a set of points having a total cost no greater than a budgeted cost within sets of points covering an area within a hierarchy of the plurality of taxonomies bounded by the one or more locations; and

means for outputting a list of response objects associated with the one or more locations within the set of points having the total cost no greater than the budgeted cost.

17. The computer system of claim 16 further comprising means for determining the sets of points covering the area within the hierarchy of the plurality of taxonomies bounded by the one or more locations.

18. The computer system of claim 16 wherein means for finding the set of points having the total cost no greater than the budgeted cost within the sets of points covering the area within the hierarchy of the plurality of taxonomies bounded by the one or more locations comprises means for applying dynamic programming to iteratively determine a minimal-cost cover for a set of rectangles covering a simplex within the hierarchy of the plurality of taxonomies bounded by the one or more locations.

19. The computer system of claim 16 wherein means for finding the set of points having the total cost no greater than the budgeted cost within the sets of points covering the area within the hierarchy of the plurality of taxonomies bounded by the one or more locations comprises means for applying a greedy algorithm to determine a minimal weight set cover for a multi-dimensional grid of points within the hierarchy of the plurality of taxonomies bounded by the one or more locations.

20. The computer system of claim 16 further comprising means for ranking the list of response objects associated with the one or more locations within the set of points having the total cost no greater than the budgeted cost.