System and method for correcting spelling errors in search queries using both matching and non-matching search terms

• US 6,401,084 B1
• Filed: 03/02/2000
• Issued: 06/04/2002
• Est. Priority Date: 07/15/1998
• Status: Expired due to Term

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: Amazon.com Holdings LLC (Amazon.com, Inc.)
• Inventors: Ortega, Ruben Ernesto, Bowman, Dwayne Edward
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/517,786
• Time in Patent Office: 824 Days
• Field of Search: 707/1-6, 704/9, 704/4, 704/5
• US Class Current: 707/706
• 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 is disclosed for predicting the correct spelling 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 predicting a correct spelling of a non-matching term in a multiple-term search query, the method comprising:

identifying a plurality of additional terms that are related to at least one matching term within the multiple-term search query; and

comparing a spelling of the non-matching term to spellings of the additional terms to determine whether any of the additional terms is sufficiently similar in spelling to the non-matching term to be deemed a candidate correctly-spelled replacement term for the non-matching term;

whereby both matching and non-matching terms within the multiple-term search query are used to predict spelling corrections.

2. The method as in claim 1, wherein comparing the spelling of the non-matching term to spellings of the additional terms comprises using a spelling comparison function which generates a score that indicates a degree of similarity between two character strings.

3. The method as in claim 2, wherein comparing the spelling further comprises comparing a score generated by the spelling comparison function to a threshold value to determine whether a corresponding additional term is a candidate replacement term, wherein the threshold value is dependent upon a number of characters in the non-matching term.

4. The method as in claim 1, wherein identifying a plurality of additional terms comprises identifying terms that, based on an analysis of prior search query submissions from multiple users, have appeared in combination with the at least one matching term within prior search query submissions.

5. The method as in claim 4, wherein identifying a plurality of additional terms comprises selecting terms based at least upon a frequency with which such terms have occurred in combination with the at least one matching term within prior search query submissions.

6. The method as in claim 4, wherein identifying terms that have appeared in combination with the at least one matching term within prior search query submissions comprises ignoring past queries that produced a null search result.

7. The method as in claim 4, wherein identifying terms that have appeared in combination with the at least one matching term within prior search query submissions comprises applying a time-based biasing function to a query log to favor recent search query submissions over aged search query submissions, so that spelling correction predictions tend to reflect current interests of users.

8. The method as in claim 7, wherein applying a time-based biasing function comprises ignoring prior search query submissions that fall outside a sliding time window.

9. The method as in claim 1, wherein identifying a plurality of additional terms comprises identifying terms that appear in combination with the at least one matching term within a database to which the search query is directed.

10. The method as in claim 9, wherein identifying terms that appear in combination with the at least one matching term within the database comprises identifying terms that appear together within at least one of the following database elements:

an item record, an item title, and an item description.

11. The method as in claim 1, further comprising, when at least one of the additional terms is determined to be a candidate replacement term for the non-matching term, replacing the non-matching term with an additional term that is a candidate replacement term, and then executing the search query as modified, without requesting input from a user.

12. The method as in claim 1, further comprising presenting a user that submitted the search query with a list of the candidate correctly-spelled replacement terms for selection.

13. A computer-implemented method of predicting a correct spelling of a misspelled term in a multiple-term search query, the method comprising:

identifying a plurality of additional terms that are related to at least one correctly-spelled term within the multiple-term search query; and

comparing the misspelled term to the additional terms to determine whether any of the additional terms is sufficiently similar to the misspelled term to be deemed a candidate correctly-spelled replacement term for the misspelled term;

whereby at least one correctly-spelled term in the multiple-term search query is used to predict a correct spelling of the misspelled term.

14. The method as in claim 13, wherein comparing the misspelled term to the additional terms comprises using a spelling comparison function which generates a score that indicates a degree of similarity between two character strings.

15. The method as in claim 14, wherein comparing the misspelled term to the additional terms further comprises comparing a score generated by the spelling comparison function to a threshold value to determine whether a corresponding additional term is a candidate replacement term, wherein the threshold value is dependent upon a number of characters in the misspelled term.

16. The method as in claim 13, wherein identifying a plurality of additional terms comprises identifying terms that, based on an analysis of prior search query submissions from multiple users, have appeared in combination with the at least one correctly-spelled term within prior search query submissions.

17. The method as in claim 16, wherein identifying a plurality of additional terms comprises selecting terms based at least upon a frequency with which such terms have occurred in combination with the at least one correctly-spelled term within prior search query submissions.

18. The method as in claim 16, wherein identifying terms that have appeared in combination with the at least one correctly-spelled term within prior search query submissions comprises ignoring past queries that produced a null search result.

19. The method &

a in claim 16, wherein identifying terms that have appeared in combination with the at least one correctly-spelled term within prior search query submissions comprises applying a time-based biasing function to a query log to favor recent search query submissions over aged search query submissions.

20. The method as in claim 13, wherein identifying a plurality of additional terms comprises identifying terms that appear in combination with the at least one correctly-spelled term within a database to which the search query is directed.

21. The method as in claim 20, wherein identifying terms that appear in combination with the at least one correctly-spelled term within the database comprises identifying terms that appear together within at least one of the following elements of the database:

an item record, an item title, and an item description.

22. The method as in claim 13, further comprising, when at least one of the additional terms is a candidate replacement for the misspelled term, replacing the misspelled term with an additional term that is a candidate replacement, and then executing the search query as modified, without requesting input from a user.

23. The method as in claim 13, further comprising presenting a user that submitted the search query with a list of the candidate correctly-spelled replacement terms for selection.

24. A computer-implemented method of predicting a correct spelling of a non-matching term within a multiple-term search query, comprising:

identifying a matching term within the multiple-term search query;

identifying an additional term that is related to the matching term; and

comparing the non-matching term to the additional term to determine whether the additional term is sufficiently similar in spelling to the non-matching term to be deemed a candidate correctly-spelled replacement term for the non-matching term;

whereby both the matching term and the non-matching term are used to predict the correct spelling of the non-matching term.

25. The method as in claim 24, wherein comparing the non-matching term to the additional term comprises using a spelling comparison function which generates a score that indicates a degree of similarity between two character strings.

26. The method as in claim 25, wherein comparing the non-matching term to the additional term further comprises comparing a score generated by the spelling comparison function to a threshold value to determine whether the additional term is a candidate correctly-spelled replacement term, wherein the threshold value is dependent upon a number of characters in the non-matching term.

27. The method as in claim 24, wherein identifying an additional term comprises identifying a term that, based on an analysis of prior search query submissions from multiple users, has appeared in combination with the matching term within prior search query submissions.

28. The method as in claim 27, wherein identifying an additional term comprises selecting the additional term based at least upon a frequency with which the additional term has occurred in combination with the matching term within prior search query submissions.

29. The method as in claim 27, wherein identifying an additional term that has appeared in combination with the matching term within prior search query submissions comprises ignoring past queries that produced a null search result.

30. The method as in claim 27, wherein identifying an additional term tat has appeared in combination with the matching term within prior search query submissions comprises applying a time-based biasing function to a query log to favor recent search query submissions over aged search query submissions.

31. The method as in claim 30, wherein applying a time-based biasing function comprises ignoring prior search query submissions that fall outside a sliding time window.

32. The method as in claim 24, wherein identifying an additional term comprises identifying a term that appears in combination with the matching term within a database to which the search query is directed.

33. The method as in claim 32, wherein identifying an additional term that appears in combination with the matching term within the database comprises identifying terms that appear together within at least one of the following elements of the database:

an item record, an item title, and an item description.

34. The method as in claim 24, further comprising replacing the non-matching term with the additional term, and then executing the search query as modified, without requesting input from a user.

35. The method as in claim 24, further comprising displaying the additional term to a user that submitted the search query.

36. The method as in claim 24, wherein identifying an additional term comprises accessing a data structure to retrieve a related terms list for the matching term.