Identifying alternative spellings of search strings by analyzing self-corrective searching behaviors of users

• US 20070038615A1
• Filed: 08/11/2005
• Published: 02/15/2007
• Est. Priority Date: 08/11/2005
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Whitman, Ronald, Vadon, Eric, Henne, Randal
• Granted Patent: US 7,321,892 B2
• Time in Patent Office: Days
• 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 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

Abstract

A computer-implemented process identifies useful alternative spellings of search strings submitted to a search engine. The process takes into consideration spelling changes made by users, as detected by programmatically analyzing search string submissions of a population of search engine users. In one embodiment, an assessment of whether a second search string represents a useful alternative spelling of a first search string takes into consideration (1) an edit distance between the first and second search strings, and (2) a likelihood that a user who submits the first search string will thereafter submit the second search string, as determined by monitoring and analyzing actions of users.

Claims

1. A computer-implemented method, comprising:

analyzing search string submissions of each of a plurality of users to detect search string spelling change events, each search string spelling change event being an event in which a user submits a first search string to a search engine, and subsequently submits to the search engine a second search string which is similar in spelling to, but different in spelling from, the first search string; and

for each of a plurality of search strings included in the search string submissions, identifying one or more alternative spellings of the respective search strings, wherein the alternative spellings are identified, at least in part, by analyzing the detected search string spelling change events.

2. The method of claim 1, wherein analyzing the detected spelling change events comprises assessing whether string B is a useful alternative spelling of string A, at least in part, by evaluating whether spelling changes from string A to string B occur significantly more frequently than spelling changes from string B to string A.

3. The method of claim 1, wherein analyzing the detected spelling change events comprises assessing whether string B is a useful alternative spelling of string A, taking into consideration how frequently users who make a spelling change to string A do so by submitting string B.

4. The method of claim 1, wherein analyzing the search string submissions comprises calculating edit distances between search strings submitted by a particular user of said plurality of users.

5. The method of claim 1, wherein the spelling change events include events in which a user conducts one or more intervening searches between the submission of the first search string and the submission of the second search string.

6. The method of claim 1, wherein analyzing the detected spelling change events comprises, for a spelling change from string A to string B, analyzing actions of users who submitted string A and string B to assess a usefulness of string B to users who submit string A.

7. The method of claim 6, wherein assessing the usefulness of string B to users who submit string A comprises analyzing browsing actions of users who submitted string B to evaluate whether such users were satisfied with a search result corresponding to sting B.

8. The method of claim 6, wherein assessing the usefulness of string B to users who submit string A comprises taking into consideration an edit distance between string A and string B.

9. The method of claim 6, wherein assessing the usefulness of string B to users who submit string A comprises taking into consideration whether spelling changes from string A to string B are more likely to occur than spelling changes from string B to string A.

10. The method of claim 1, wherein analyzing the detected spelling change events comprises assigning different weights to different spelling change events, said weights being dependent upon other user actions performed in browsing sessions in which the corresponding spelling change events occurred.

11. The method of claim 10, wherein analyzing the detected spelling change events further comprises, for a particular spelling change, combining the weights of a plurality of events involving the particular spelling change to generate a weight for the spelling change.

12. The method of claim 1, wherein analyzing the detected spelling change events comprises weighting a spelling change event based, at least in part, on other user actions performed as part of a browsing session in which the spelling change event occurred.

13. The method of claim 1, wherein analyzing the detected spelling change events comprises giving more weight to recent spelling change events than to older spelling change events.

14. The method of claim 1, further comprising generating, in computer storage, a mapping of particular search strings of said plurality of search strings to corresponding alternative search strings.

15. The method of claim 14, further comprising using the mapping to suggest alternative search string spellings to users.

16. The method of claim 14, further comprising using the mapping to automatically correct spelling errors in search strings submitted by users.

17. A computer program that embodies the method of claim 1, represented in computer storage.

18. A computer implemented method, comprising:

identifying a first search string and a second search string that were separately submitted to a search engine by at least one user; and

programmatically assessing whether the second search string represents a useful alternative spelling of the first search string, taking into consideration at least (1) a degree to which the first search string and the second search strings are similar in spelling, and (2) detected spelling changes made to the first search string by each of a plurality of users.

19. The method of claim 18, wherein degree to which the first search string and the second search strings are similar in spelling is determined, at least in part, by calculating an edit distance between the first and second search strings.

20. The method of claim 18, further comprising detecting said spelling changes made to the first search string by detecting, for each of said plurality of users, a submission of the first search string followed by a submission of a similarly spelled search string.

21. The method of claim 18, wherein programmatically assessing whether the second search string represents a useful alternative spelling of the first search string comprises taking into consideration how frequenly users who make corrections to the first search string do so by submitting the second search string.

22. The method of claim 18, wherein programmatically assessing whether the second search string represents a useful alternative spelling of the first search string comprises taking into consideration whether transitions from first search string to the second search string occur more frequently than transitions from the second search string to the first search string.

23. The method of claim 22, wherein the method comprises giving different amounts of weight to different transitions between the first and second search strings.

24. The method of claim 18, wherein programmatically assessing whether the second search string represents a useful alternative spelling of the first search string comprises taking into consideration detected transitions from the second search string to the first search string.

25. The method of claim 18, wherein the method comprises treating the second search string as a useful alternative spelling of the first search string only if spelling changes from the first search string to the second search string have occurred substantially more frequently than spelling changes from the second search string to the first search string.

26. The method of claim 18, wherein programmatically assessing whether the second search string represents a useful alternative spelling of the first search string comprises taking into consideration an extent to which search result browsing actions of users who submitted the second search string reveal that users were satisfied with a search result generated using the second search string.

27. The method of claim 18, further comprising, in response to determining that the second search string represents a useful alternative spelling of the first search string, generating, in computer storage, a mapping of the first search string to the second search string.

28. The method of claim 18, further comprising, in response to determining that the second search string represents a useful alternative spelling of the first search string, suggesting the second search string to users who submit the first search string to a search engine.

29. A computer program that embodies the method of claim 18, represented in computer storage.

30. A computer-implemented method of processing search string submissions, the method comprising:

receiving a first search string submitted to a search engine by a user who is conducting a search;

selecting an alternative search string that represents an alternative spelling of the first search string, taking into consideration detected spelling changes made by prior users who have submitted the first search string, said spelling changes detected automatically by comparing search string submissions of users; and

in response to receiving the first search string, doing at least one of following;

(a) suggesting the alternative search string to the user, (b) automatically replacing the first search string with the alternative search string.

31. The method of claim 30, wherein the method comprises accessing a mapping table to look up the alternative string, said mapping table generated based, at least in part, on an analysis of detected spelling changes made by a plurality of users of the search engine.

32. The method of claim 30, wherein the selection of the alternative search string further takes into consideration an edit distance between the first search string and the alternative search string.

33. A search engine system that performs the method of claim 30.

34. A computer program that embodies the method of claim 30, represented in computer storage.

35. A computer-implemented method comprising:

aggregating spelling change event data descriptive of spelling changes made by each of a plurality of computer users;

programmatically analyzing at least the aggregated spelling change event data to assess, for at least a first string and a second string, whether the second string represents a useful alternative spelling of the first string; and

if, as a result of said assessment, the second string is identified as a useful alternative spelling of the first string, generating, in computer storage, a mapping of the first string to the second string.

36. The method of claim 35, wherein programmatically analyzing the aggregated spelling change event data comprises taking into consideration whether spelling changes from the first string to the second string occur significantly more frequently than spelling changes from the second string to the first string.

37. The method of claim 35, wherein programmatically analyzing the aggregated spelling change event data comprises taking into consideration how frequently users who make a spelling change to the first string do so by transitioning to the second string.

38. The method of claim 35, wherein programmatically analyzing the aggregated spelling change event data comprises taking into consideration an edit distance between the first string and the second string.

39. The method of claim 35, wherein aggregating spelling change event data comprises monitoring spelling changes made by users via document spell checking programs.

40. The method of claim 35, wherein the spelling change event data comprises data descriptive of spelling changes made by users to search strings submitted to a search engine.

41. The method of claim 35, further comprising using said mapping to programmatically suggest the second string to a user who enters the first string.