Search query processing to identify search string corrections that reflect past search query submissions of users

• US 7,444,324 B2
• Filed: 11/03/2004
• Issued: 10/28/2008
• Est. Priority Date: 07/15/1998
• Status: Expired due to Fees

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Ortega, Ruben Ernesto, Bowman, Dwayne Edward
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US10/980,641
• Publication Number:
  US 20050071332A1
• Time in Patent Office: 1,455 Days
• Field of Search: 707/1, 707/2, 707/3, 707/5, 707/10, 707/6, 707/7, 707/8, 707/4, 707/102, 715/533, 715/257, 704/4, 704/5, 704/9, 709/217
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 40/226 Validation
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A search engine process predicts the correct spellings of search terms within multiple-term search queries. In one embodiment, when a user submits a multiple-term search query that includes a non-matching term and at least one matching term, a table is accessed to look up a set of terms that are “related” to the matching term or terms. A spelling comparison function is then used to determine whether any of these related terms is sufficiently similar in spelling to the non-matching term to be deemed a candidate correctly-spelled replacement. A candidate replacement term may automatically be substituted for the non-matching term, or may be suggested to the user as a replacement. The invention also includes a process for identifying terms that are related to each other based on the relatively high frequencies with which they co-occur within search queries of users, database records, and/or specific database fields.

Claims

1. A computer-implemented method of processing search query submissions, the method comprising:

receiving a search query over a computer network, said search query comprising a search string specified by a user; and

in response to the search query, programmatically identifying a corrected version of the search string specified by the user, wherein programmatically identifying the corrected version of the search string comprises taking into consideration past search query submissions of a plurality of users, said corrected version correcting a misspelling in the search string specified by the user;

wherein the method comprises performing a programmatic analysis of said past search query submissions of said plurality of users, generating a table containing data resulting from said programmatic analysis, and using the table to identify the corrected version of the search string.

2. The method of claim 1, further comprising automatically substituting the corrected version of the search string for the search string specified by the user for purposes of search query execution.

3. The method of claim 1, further comprising outputting to the user a link which is selectable to initiate a modified search using the corrected version of the search string.

4. The method of claim 1, wherein programmatically identifying the corrected version comprises taking into consideration a degree to which the search string specified by the user is similar in spelling to the corrected version of the search string.

5. The method of claim 1, wherein programmatically identifying the corrected version comprises taking into consideration post-query-submission actions performed by users with respect to search result items.

6. The method of claim 1, wherein the search string comprises multiple terms.

7. The method of claim 6, wherein programmatically identifying a corrected version of the search string comprises identifying a replacement term for one of said multiple search terms.

8. A search engine system which performs the method of claim 1.

9. The method of claim 1, wherein programmatically identifying the corrected version of the search string comprises using data automatically derived from past search activities of users to select the corrected version of the search string.

10. A computer program product embodied in computer-readable storage media, the computer program product embodying a method that comprises:

receiving a search query over a computer network, said search query comprising a search string specified by a user; and

in response to the search query, programmatically identifying a corrected version of the search string specified by the user, wherein programmatically identifying the corrected version of the search string comprises taking into consideration past search query submissions of a plurality of users, said corrected version correcting a misspelling in the search string specified by the user;

wherein the method comprises performing a programmatic analysis of said past search query submissions of said plurality of users, generating a table containing data resulting from said programmatic analysis, and using the table to identify the corrected version of the search string.

11. A system for processing search query submissions, the system comprising:

a server system configured to receive a search query over a computer network, said search query comprising a search string specified by a user, said server system comprising a processor and memory;

a spelling correction component that runs on the server system, said spelling correction component capable of using a table reflective of past search query submissions of a plurality of users to identify a corrected version of the search string specified by the user, said corrected version correcting a misspelling in the search string specified by the user and being dependent upon the past search query submissions of the plurality of users; and

a component that generates said table reflective of past search query submissions, at least in part, by analyzing recorded search query submissions of said plurality of users.

12. The system of claim 11, wherein the spelling correction component is configured to automatically substitute, for purposes of search query execution, the corrected version of the search string for the search string specified by the user.

13. The system of claim 11, wherein the server system is configured to output to the user a link which is selectable to initiate a modified search using the corrected version of the search string.

14. The system of claim 11, wherein the spelling correction component is configured to take into consideration a degree to which the search string specified by the user is similar in spelling to the corrected version of the search string.

15. The system of claim 11, wherein the table reflective of past search query submissions is additionally reflective of post-query-submission actions performed by prior users with respect to search result items.

16. The system of claim 11, wherein the spelling correction component is configured to identify the corrected version of the search string using a pre-generated mapping structure generated, at least in part, by programmatically analyzing said search query submissions of the plurality of users.

17. A system for processing search query submissions, the system comprising:

a server system configured to receive a search query over a computer network, said search query comprising a search string specified by a user, said server system comprising a processor and memory;

a spelling correction component that runs on the server system, said spelling correction component capable of using data reflective of past search query submissions of a plurality of users to identify a corrected version of the search string specified by the user, said corrected version correcting a misspelling in the search string specified by the user and being dependent upon the past search query submissions of the plurality of users; and

a table generation process capable of generating a table that is reflective of the past search query submissions of the plurality of users, wherein the spelling correction component is configured to use the table to identify the corrected version of the search string.

18. The system of claim 17, wherein the server system is configured to output a link which is selectable by the user to initiate a modified search using the corrected version of the search string.