Identifying superphrases of text strings
AssigneeYahoo! Inc.
InventorsJignashu Parikh, Narayan L. Bhamidipati, Rajesh Parekh
Life of this patent
Estimating the term…
Abstract
Methods and apparatus are described by which “superphrases” of “seed phrases” representing basic concepts may be identified without having to compare all possible pairs of seed and candidate phrases. According to one class of embodiments, a data structure similar to an inverted index is used for indexing phrases. The elimination of seed and candidate phrase pairs is enabled by building and traversing the index in a particular manner.
Claims23
A computer-implemented method for identifying superphrases in a set of candidate phrases with reference to a set of seed phrases, each of the candidate phrases comprising one or more candidate phrase words, and each of the seed phrases comprising one or more seed phrase words, the method comprising:
- sorting all distinct ones of the seed phrase words in the set of seed phrases;
- indexing each seed phrase in the set of seed phrases by sorting the corresponding seed phrase words, and indexing the seed phrase with reference to the sorted distinct seed phrase words;
- and
- determining whether each candidate phrase is a superphrase of one or more of the seed phrases by sorting only the corresponding candidate phrase words included among the distinct seed phrase words, and determining whether all of the seed phrase words of any of the indexed seed phrases are included among the sorted candidate phrase words.
A computer-implemented method for rewriting search queries with reference to a set of seed queries, comprising:
- determining whether a first search query includes one or more of the seed queries;
- where the first search query includes a first one of the seed queries, reformulating the first search query as a rewritten search query, wherein the rewritten search query represents different matching requirements for corresponding subsets of terms included in the rewritten search query;
- and
- generating search results with reference to the rewritten search query in response to the first search query.
A computer-implemented method for responding to search queries, comprising facilitating presentation of search results in an interface in response to a first search query, the search results having been generated with reference to a rewritten search query which corresponds to a reformulation of the first search query, the rewritten search query representing different matching requirements for corresponding subsets of terms included in the rewritten search query, a first one of the subsets of terms included in the rewritten search query corresponding to a seed query contained within the first search query.
A computer program product for identifying superphrases in a set of candidate phrases with reference to a set of seed phrases, each of the candidate phrases comprising one or more candidate phrase words, and each of the seed phrases comprising one or more seed phrase words, the computer program product comprising at least one computer-readable medium having computer program instructions stored therein configured to enable at least one computing device to:
- sort all distinct ones of the seed phrase words in the set of seed phrases;
- index each seed phrase in the set of seed phrases by sorting the corresponding seed phrase words, and indexing the seed phrase with reference to the sorted distinct seed phrase words;
- and
- determine whether each candidate phrase is a superphrase of one or more of the seed phrases by sorting only the corresponding candidate phrase words included among the distinct seed phrase words, and determining whether all of the seed phrase words of any of the indexed seed phrases are included among the sorted candidate phrase words.
A computer program product for rewriting search queries with reference to a set of seed queries, the computer program product comprising at least one computer-readable medium having computer program instructions stored therein configured to enable at least one computing device to:
- determine whether a first search query includes one or more of the seed queries;
- where the first search query includes a first one of the seed queries, reformulate the first search query as a rewritten search query, wherein the rewritten search query represents different matching requirements for corresponding subsets of terms included in the rewritten search query;
- and
- generate search results with reference to the rewritten search query in response to the first search query.
A system for rewriting search queries with reference to a set of seed queries, the system comprising at least one computing device configured to:
- determine whether a first search query includes one or more of the seed queries;
- where the first search query includes a first one of the seed queries, reformulate the first search query as a rewritten search query, wherein the rewritten search query represents different matching requirements for corresponding subsets of terms included in the rewritten search query;
- and
- generate search results with reference to the rewritten search query in response to the first search query.
Dependencies are inferred from the claim text.