Methods and systems for efficient query rewriting

• US 7,840,547 B1
• Filed: 03/31/2004
• Issued: 11/23/2010
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Jackson, Eric, Tucker, Paul, Singhal, Amit
• Primary Examiner(s): BETIT, JACOB F
• Application Number:
  US10/812,901
• Time in Patent Office: 2,428 Days
• Field of Search: 707/3, 707/5, 707/706, 707/759, 707/772
• US Class Current: 707/706
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Methods and systems for efficient query rewriting and the like are described here. One such described method comprises: offline mapping frequently-seen search queries to rewritten queries that may be better for searching; offline caching the mapping in a cache memory; and upon receiving a search query from a user similar to one of the mapped search queries, obtaining a corresponding rewritten query from the mapping in the cache memory based on predetermined conditions, and issuing a search of the rewritten query to the backend data system in order to avoid having to issue a search query to the backend data system twice while the user is online.

Claims

1. A method comprising:

populating a computer memory, by receiving a plurality of first search queries from a first plurality of computer users at a computer system, rewriting the plurality of first search queries into modified search queries, and mapping ones of the plurality of first search queries to corresponding modified search queries to produce a mapping in computer memory that correlates ones of the plurality of first search queries with corresponding ones of the rewritten search queries;

wherein rewriting the plurality of first search queries into the modified search queries comprises;

determining a phrase or term that is more common or popular than content of a first one of the plurality of first search queries; and

rewriting the first one of the plurality of first search queries into a first one of the modified search queries such that the first one of the modified search queries includes the determined phrase or term in place of the content of the first one of the plurality of first search queries;

providing search results for the rewritten search queries to the plurality of computer users;

subsequently processing a second search query received from a user who is different than the first plurality of computer users, by determining whether a portion of content from the second query matches a portion of content from at least one of the plurality of first search queries, and executing, based on a determination of whether a portion of the content from the second query matches a portion of content from at least one of the plurality of first search queries, (i) a computerized search using one of the rewritten queries that corresponds to the query from the plurality of first search queries that includes the matching portion of content in place of the second search query, or (ii) a search using information corresponding to the received second search query or a modified version of the second search query; and

providing search results from processing the second search query to the second user.

2. The method of claim 1, wherein the memory comprises a look-up table for the mapping.

3. The method of claim 1, wherein the search of the one of the rewritten queries that corresponds to the query from the plurality of first search queries that includes the matching portion of content in place of the second search query is executed by a backend data system.

4. The method of claim 3, wherein the backend data system is physically apart from the memory and comprises one or more databases having data to be searched.

5. The method of claim 3, wherein the memory comprises a look-up table mapping the plurality of first search queries to the modified search queries;

and

wherein the backend data system is physically apart from the memory and comprises one or more databases having data to be searched.

6. The method of claim 1, wherein mapping is performed offline prior to receiving the second search query;

and executing the search is performed online upon receiving the second search query.

8. The method of claim 1, wherein the plurality of first queries and the second search query are received at a first system of a search site, and the search of the modified search query is issued by a search engine in the first system.

9. The method of claim 8, wherein the first system of the search site comprises cache memory.

10. The method of claim 8, wherein the memory is physically apart from the first system of the search site.

11. The method of claim 8, wherein rewriting is performed by the first system of the search site.

12. The method of claim 11, wherein the steps of mapping and determining are performed by the first system of the search site.

13. The method of claim 11, wherein the memory is a database in a memory system of the search site, and the steps of mapping and determining are performed by the memory system.

14. The method of claim 8, wherein the memory is a database in a memory system of the search site, and rewriting is performed with the memory system.

15. The method of claim 14, wherein the steps of mapping and determining are performed by the memory system.

16. The method of claim 14, wherein the steps of mapping and determining are performed by the first system of the search site.

17. The method of claim 1, wherein the memory comprises a memory chip.

18. The method of claim 1, wherein the memory comprises a disk-storage memory device.

19. The method of claim 1, wherein rewriting the plurality of first search queries into the modified search queries further comprises:

determining an additional phrase or term for content of a first one of the first plurality of search queries; and

augmenting the first one of the plurality of first search queries to include the additional phrase or term.

7. A method comprising:

populating a computer memory, by receiving a plurality of first search queries from a first plurality of computer users at a computer system, rewriting the plurality of first search queries into modified search queries, and mapping ones of the plurality of first search queries to corresponding modified search queries to produce a mapping in computer memory that correlates ones of the plurality of first search queries with corresponding ones of the rewritten search queries;

wherein rewriting the plurality of first search queries into the modified search queries comprises;

determining that a first one of the plurality of first search queries is frequently received;

issuing the first one of the plurality of first search queries to the backend data system to find information related to the first one of the plurality of first search queries;

determining additional content for the first one of the plurality of first search queries based on the related information; and

rewriting the first one of the plurality of first search queries into a corresponding first one of the modified search queries such that the corresponding first one of the modified search queries includes the additional content;

providing search results for the rewritten search queries to the plurality of computer users;

subsequently processing a second search query received from a user who is different than the first plurality of computer users, by determining whether a portion of content from the second query matches a portion of content from at least one of the plurality of first search queries, and executing, based on a determination of whether a portion of the content from the second query matches a portion of content from at least one of the plurality of first search queries, (i) a computerized search using one of the rewritten queries that corresponds to the query from the plurality of first search queries that includes the matching portion of content in place of the second search query, or (ii) a search using information corresponding to the received second search query or a modified version of the second search query; and

providing search results from processing the second search query to the second user.

20. A computer-readable storage device having computer-executable instructions contained therein for performing a method, the method comprising:

populating a computer memory, by receiving a plurality of first search queries from a first plurality of computer users at a computer system, rewriting the plurality of first search queries into modified search queries, and mapping ones of the plurality of first search queries to corresponding modified search queries to produce a mapping in computer memory that correlates ones of the plurality of first search queries with corresponding ones of the rewritten search queries;

wherein rewriting the plurality of first search queries into the modified search queries comprises;

determining a phrase or term that is more common or popular than content of a first one of the plurality of first search queries; and

rewriting the first one of the plurality of first search queries into a first one of the modified search queries such that the first one of the modified search

queries includes the determined phrase or term in place of the content of the first one of the plurality of first search queries;

providing search results for the rewritten search queries to the plurality of computer users;

subsequently processing a second search query received from a user who is different than the first plurality of computer users, by determining whether a portion of content from the second query matches a portion of content from at least one of the plurality of first search queries, and executing, based on a determination of whether a portion of the content from the second query matches a portion of content from at least one of the plurality of first search queries, (i) a computerized search using one of the rewritten queries that corresponds to the query from the plurality of first search queries that includes the matching portion of content in place of the second search query, or (ii) a search using information corresponding to the received second search query or a modified version of the second search query; and

providing search results from processing the second search query to the second user.

21. The computer-readable storage device of claim 20, wherein the method further comprises:

issuing a search of the received second search query to the backend search system in response to the portion of the content from the second query not matching any portion of content from the plurality of first search queries.

22. The computer-readable storage device of claim 20, wherein mapping the plurality of first search queries to the modified search queries in the memory comprises generating a look-up table for the mapping.

23. The computer-readable storage device of claim 20, wherein the mapping is configured to run offline prior to the step of receiving the second search query;

and the issuing the search is configured to run online upon receiving the second search query.

25. The computer-readable storage device of claim 20, wherein rewriting the plurality of first search queries into the modified search queries further comprises:

determining an additional phrase or term for content of a first one of the first plurality of search queries; and

augmenting the first one of the plurality of first search queries to include the additional phrase or term.

24. A computer-readable storage device having computer-executable instructions contained therein for performing a method, the method comprising:

populating a computer memory, by receiving a plurality of first search queries from a first plurality of computer users at a computer system, rewriting the plurality of first search queries into modified search queries, and mapping ones of the plurality of first search queries to corresponding modified search queries to produce a mapping in computer memory that correlates ones of the plurality of first search queries with corresponding ones of the rewritten search queries;

wherein rewriting the plurality of first search queries into the modified search queries comprises;

determining that a first one of the plurality of first search queries is frequently received;

issuing the first one of the plurality of first search queries to the backend data system to find information related to the first one of the plurality of first search queries;

determining additional content for the first one of the plurality of first search queries based on the related information; and

rewriting the first one of the plurality of first search queries into a corresponding first one of the modified search queries such that the corresponding first one of the modified search queries includes the additional content;

providing search results for the rewritten search queries to the plurality of computer users;

subsequently processing a second search query received from a user who is different than the first plurality of computer users, by determining whether a portion of content from the second query matches a portion of content from at least one of the plurality of first search queries, and executing, based on a determination of whether a portion of the content from the second query matches a portion of content from at least one of the plurality of first search queries, (i) a computerized search using one of the rewritten queries that corresponds to the query from the plurality of first search queries that includes the matching portion of content in place of the second search query, or (ii) a search using information corresponding to the received second search query or a modified version of the second search query; and

providing search results from processing the second search query to the second user.

26. A method comprising:

populating a computer memory, wherein populating the computer memory comprises;

receiving at a computer system search interface a plurality of instances of a first search query having a first plurality of search terms forming a phrase;

determining an indicator of frequency with which the first search query has been received at the search interface;

when the first search query is determined, based on the indicator of frequency, to be among a group of most frequently received queries relative to other queries received at the search interface that are different than the first search query, rewriting the first search query, based on the phrase, into a modified search query having a second plurality of search terms that are different in content or order than the first plurality of search terms, and mapping, with the computer system, the first search query to the modified search query in the memory to produce a mapping stored in the memory that correlates the first search query to the modified search query; and

subsequently processing a second search query including;

receiving the second search query;

determining that at least one portion of the second query matches one or more of the first plurality of search terms; and

executing, based on the determination of whether at least one portion of the second query matches one or more of the first plurality of search terms, (i) a computerized search of the modified search query in place of the at least one portion of the second search query, or (ii) a search using information corresponding to the second search query or a modified version of the second search query, and returning one or more corresponding search results as responsive to the received second search query,

wherein the at least one portion of the second query that matches the one or more of the first plurality of search terms is replaced by the modified search query.