Query rewriting with entity detection

• US 8,521,764 B2
• Filed: 07/14/2011
• Issued: 08/27/2013
• Est. Priority Date: 03/31/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pfleger, Karl
• Primary Examiner(s): HASAN, SYED HAROON
• Application Number:
  US13/183,192
• Publication Number:
  US 20110270863A1
• Time in Patent Office: 775 Days
• Field of Search: None
• US Class Current: 707/768
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system determines whether a received search query includes an entity name, determines whether to rewrite the received search query based on information relating to prior searches involving the entity name, and rewrites the received search query when it is determined that the received search query should be rewritten. The system further determines whether to provide a suggestion of rewriting the received search query, as a rewriting suggestion, based on information relating to prior searches involving the entity name when it is determined that the received search query should not be rewritten. The system also generates the rewriting suggestion when it is determined that the rewriting suggestion should be provided. The system performs a search based on one of the received search query and the rewritten search query to obtain search results, presents the search results, and presents the rewriting suggestion when it is determined that the rewriting suggestion should be provided.

Claims

1. A method comprising:

identifying, using one or more server devices, a plurality of search queries, where each of the plurality of search queries includes a same variation of an entity name;

identifying, using the one or more server devices, a plurality of entity identifiers, where each of the plurality of entity identifiers is associated with a document that was selected, from a plurality of search result documents, based on a corresponding search query of the identified plurality of search queries;

determining, using the one or more server devices, that a total quantity of selections of the document associated with a particular entity identifier, of the plurality of entity identifiers, is greater than a total quantity of selections of each of the documents associated with other ones of the plurality of entity identifiers; and

storing, in response to the determining, the same variation of the entity name in a memory that is used to rewrite search queries.

2. The method of claim 1, further comprising:

determining whether one or more terms, included in a received search query, match a variation of a particular entity name in the memory; and

rewriting, using the memory, the received search query into a rewritten search query,

where rewriting the received search query includes;

rewriting, using the memory, the received search query into the rewritten search query by replacing the one or more terms with an entity identifier, from the memory, associated with the variation of the particular entity name, when the one or more terms match the variation of the particular entity name in the memory; and

performing a search based on the rewritten search query.

3. The method of claim 2, where rewriting the received search query includes:

rewriting the received search query to be restricted to a domain associated with the entity identifier that is associated with the variation of the particular entity name,

the method further comprising;

presenting a result of the performed search concurrently with a link to the received search query,

where selection of the link to the received search query causes a search to be performed using the received search query.

4. The method of claim 1, further comprising:

determining whether the total quantity of selections of the document associated with the particular entity identifier is greater than a threshold; and

determining whether the total quantity of selections of the document associated with the particular entity identifier is greater than the total quantity of selections of each of the documents associated with the other ones of the plurality of entity identifiers, when the total quantity of selections of the document associated with the particular entity identifier is greater than the threshold,

where the same variation of the entity name is stored in the memory, when the total quantity of selections of the document associated with the particular entity identifier is greater than the total quantity of selections of each of the documents associated with the other ones of the plurality of entity identifiers.

5. The method of claim 1, further comprising:

generating candidate strings corresponding to variations of at least one of the entity name or the particular entity identifier, the generated candidate strings including the same variation of the entity name; and

selecting the same variation of the entity name, from the generated candidate strings, to determine whether to store the same variation of the entity name in the memory.

6. The method of claim 5, where generating the candidate strings includes:

modifying the entity name or the particular entity identifier by at least one of;

replacing “

and”

with “

&

,”

replacing “

&

”

with “

and,”

removing “

and” and

“

&

,”

removing “

www.,”

removing “

.com,”

or treating periods with no spaces on either side of the periods as spaces or deleting the periods.

7. The method of claim 1, further comprising:

determining that the total quantity of selections of the document associated with the particular entity identifier is statistically peaked relative to the total quantity of selections of each of the documents associated with the other ones of the plurality of entity identifiers; and

storing the same variation of the entity name in the memory based on determining that the total quantity of selections of the document associated with the particular entity identifier is statistically peaked relative to the total quantity of selections of each of the documents associated with the other ones of the plurality of entity identifiers.

8. A system comprising:

one or more server devices to;

identify entity identifiers, where each of the entity identifiers is associated with a document that was selected, from a plurality of documents, based on a search query including a same variation of an entity name;

determine whether a total quantity of selections of the document associated with a particular entity identifier, of the entity identifiers, is greater than a total quantity of selections of each of the documents associated with other ones of the entity identifiers; and

store, based on a result of the determining, the same variation of the entity name in a first memory that is used for rewriting search queries or a second memory that is used for suggesting rewritten search queries,

where the same variation of the entity name is stored in the second memory when the total quantity of selections of the document associated with the particular entity identifier is greater than the total quantity of selections of each of the documents associated with the other ones of the entity identifiers, and

where the same variation of the entity name is stored in the first memory when the total quantity of selections of the document associated with the particular entity identifier is substantially greater than the total quantity of selections of each of the documents associated with the other ones of the entity identifiers.

9. The system of claim 8, where the one or more server devices are further to:

determine whether the total quantity of selections of the document associated with the particular entity identifier is greater than a threshold,

where the one or more server devices are to determine whether the total quantity of selections of the document associated with the particular entity identifier is greater than the total quantity of selections of each of the documents associated with the other ones of the entity identifiers, when the total quantity of selections of the document associated with the particular entity identifier is greater than the threshold.

10. The system of claim 8, where, when determining whether the total quantity of selections of the document associated with the particular entity identifier is greater than the total quantity of selections of each of the documents associated with the other ones of the entity identifiers, the one or more server devices are to:

determine whether the total quantity of selections of the document associated with the particular entity identifier is peaked with respect to the total quantity of selections of each of the documents associated with the ones of the entity identifiers, and

where the one or more server devices are further to;

store the same variation of the entity name in the first memory when the total quantity of selections of the document associated with the particular entity identifier is peaked; and

store the same variation of the entity name in the second memory, when the total quantity of selections of the document associated with the particular entity identifier is not peaked.

11. The system of claim 8, where the one or more server devices are further to:

evaluate a second variation of the entity name,

where, when evaluating the second variation, the one or more server devices are to;

identify second entity identifiers, each of the second identifiers being associated with a second document that was selected based on a particular search query including the second variation, and

determine whether a total quantity of selections of the second document associated with a particular second entity identifier, of the second entity identifiers, exceeds a threshold;

determine whether to store the second variation in one of the first memory or the second memory when the total quantity of selections of the second document associated with the particular second entity identifier exceeds the threshold; and

discard the second variation of the entity name, from further consideration, when the total quantity of selections of the second document associated with the particular second entity identifier does not exceed the threshold.

12. The system of claim 8, where the one or more server devices are to:

rewrite a search query using one of the first memory or the second memory,

where, when rewriting the search query, the one or more server devices are further to;

determine whether a term, included in the search query, matches a variation of a particular entity name stored in the first memory;

rewrite, using the first memory, the search query into a rewritten search query that includes an entity identifier, in the first memory, associated with the variation of the particular entity name when the term matches the variation of the particular entity name in the first memory; and

perform a search based on the rewritten search query instead of performing a search based on the search query.

13. The system of claim 8, where the one or more server devices are to:

rewrite a search query using one of the first memory or the second memory,

where, when rewriting the search query, the one or more server devices are further to;

determine whether one or more terms, of the search query, match a particular variation of a particular entity name stored in the second memory when the one or more terms do not match a plurality of entries in the first memory;

rewrite the search query into a rewritten search query that includes an entity identifier, in the second memory, associated with the particular variation of the particular entity name when the one or more terms match the particular variation;

perform a search based on the search query to generate search results; and

present a link to the rewritten search query along with the search results,

where selection of the link to the rewritten search query causes a search to be performed using the rewritten search query.

14. The system of claim 8, where the one or more server devices are further to:

generate variations of the entity name,

where, when generating the variations of the entity name, the one or more server devices are to;

modify the entity name by at least one of;

removing modifiers, replacing spaces with hyphens or underscores, replacing hyphens or underscores with spaces, removing apostrophes, replacing “

and”

with “

&

,”

replacing “

&

”

with “

and,”

or removing “

and” and

“

&

.”

15. A computer-readable memory device including instructions, executable by a processor, to perform a method, the method comprising:

determining, for each of a plurality of entity identifiers, a total quantity of selections of a document associated the entity identifier, where the document was selected, from a plurality of documents, based on a search query including a same variation of an entity name;

determining whether a particular entity identifier, of the plurality of entity identifiers, is a most-selected entity identifier, of the plurality of entity identifiers, based on the determined total quantity of selections of each of the documents associated with the plurality of entity identifiers; and

storing, based on a result of determining whether the particular entity identifier is the most-selected entity identifier, the same variation of the entity name in a first memory that is used for suggesting rewritten search queries or a second memory that is used for rewriting search queries,

where the same variation of the entity name is stored in the first memory when the particular entity identifier is the most-selected entity identifier, and

where the same variation of the entity name is stored in the second memory, when the particular entity identifier is the most-selected entity identifier and based on determining whether the determined total quantity of selections of the document associated with the particular entity identifier is peaked with respect to the determined total quantity of selections of each of the documents associated with other ones of the plurality of entity identifiers.

16. The computer-readable memory device of claim 15, where determining whether the particular entity identifier is the most-selected entity identifier includes:

determining that the particular entity identifier is the most-selected entity identifier; and

determining whether the determined total quantity of selections of the document associated with the particular entity identifier is peaked with respect to the determined total quantity of selections of each of the documents associated with the other ones of the entity identifiers, after determining that the particular entity identifier is the most-selected entity identifier,

the method further comprising;

storing, based on determining whether the determined total quantity of selections of the document associated with the particular entity identifier is peaked, the same variation of the entity name in the first memory or the second memory.

17. The computer-readable memory device of claim 16, the method further comprising:

storing the same variation of the entity name in the first memory, when the particular entity identifier is the most-selected entity identifier and when the determined total quantity of selections of the document associated with the particular entity identifier is not peaked; and

storing the same variation of the entity name in the second memory when the particular entity identifier is the most-selected entity identifier and when the determined total quantity of selections of the document associated with the particular entity identifier is peaked.

18. The computer-readable memory device of claim 15, where storing the same variation of the entity name in the first memory or the second memory includes:

storing the same variation of the entity name in the first memory or the second memory further based on information that includes at least one of an amount of time a user spent accessing the plurality of documents or whether a conversion occurred based on accessing the plurality of documents.

19. The computer-readable memory device of claim 18, where storing the same variation of the entity name in the first memory or the second memory includes:

assigning a first weight to the determined total quantity of selections of the document associated with the particular entity identifier;

assigning a second weight, different than the first weight, to the at least one of the amount of time the user spent accessing the plurality of documents or whether the conversion occurred based on accessing the plurality of documents; and

storing the same variation of the entity name in the first memory or the second memory based on the first weight and the second weight.

20. The computer-readable memory device of claim 15, the method further comprising:

rewriting, using the first memory or the second memory, a search query into a rewritten search query that includes the particular entity identifier when a term, included in the search query, matches the same variation of the entity name;

presenting search results, obtained by performing a search based on the search query, and a link to the rewritten search query when the same variation of the entity name is stored in the first memory,

where selection of the link to the rewritten search query causes a search to be performed using the rewritten search query; and

presenting search results, obtained by performing a search based on the rewritten search query, and a link to the search query when the same variation of the entity name is stored in the second memory,

where selection of the link to the search query causes a search to be performed using the search query.