System and method for budgeted generalization search in hierarchies
First Claim
Patent Images
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.
9 Assignments
0 Petitions
Accused Products
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.
-
Citations
22 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
Specification