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

• US 7,321,892 B2
• Filed: 08/11/2005
• Issued: 01/22/2008
• 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 M., Henne, Randal M., Vadon, Eric R.
• Primary Examiner(s): Vo; Tim
• Assistant Examiner(s): Morrison; Jay A
• Application Number:
  US11/202,291
• Publication Number:
  US 20070038615A1
• Time in Patent Office: 894 Days
• Field of Search: 707 2- 5, 707/10
• US Class Current: 707/767
• 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, wherein the search string spelling change events are detected, at least in part, by comparing spellings of different search strings submitted by the same user, such that each detected spelling change event is specific to a particular user;

calculating weight values for the detected search string spelling change events, each weight value representing an amount of weight to be given to a corresponding search string spelling change event;

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 of the plurality of users, and the calculated weight values for such search string spelling change events, on an aggregated basis to assess whether particular search string spelling changes are useful to users, wherein the calculated weight values are used to give different non-zero amounts of weight to different search string spelling change events; and

creating an association in computer storage between the search strings and the corresponding alternative spellings.

2. The method of claim 1, wherein calculating the weight values comprises, for a spelling change event in which a first user made a first search string submission followed by a second search string submission, calculating a weight value that depends upon how many intervening actions were performed by the first user between the first and second search string submissions.

3. The method of claim 1, wherein analyzing the detected spelling change events comprises assessing whether a particular search string, string B, is a useful alternative spelling of another particular search string, 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 calculating the weight values comprises, for a particular spelling change event of a first user, calculating a weight value that depends upon whether the first user selected a search result item after submitting the second search string.

5. The method of claim 1, wherein calculating the weight values comprises, for a spelling change event in which a first user made a first search string submission followed by a second search string submission, calculating a weight value that depends upon an amount of time between the first and second search string submissions.

6. The method of claim 1, wherein analyzing the detected spelling change events comprises, for a spelling change from a particular search string, string A to another particular search string, 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 an extent to which such users viewed a search result corresponding to string 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 the method comprises using the weight values to calculate probabilities of occurrence of particular spelling changes, and using said probabilities of occurrence to assess whether particular search string spelling changes are useful to users.

11. The method of claim 1, further comprising adjusting the weight values according to a time decay function such that greater weight is generally given to recent spelling change events than to older spelling change events.

12. The method of claim 1, wherein calculating the weight values 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 the method comprises giving more weight to recent spelling change events than to older spelling change events.

14. The method of claim 1, wherein creating the association comprises 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. The method of claim 1, wherein the method comprises assessing a usefulness of each alternative spelling based on actions of multiple users.

49. The method as in claim 1, wherein analyzing the detected spelling change events comprises assessing whether a particular search string, string B, is a useful alternative spelling of another particular search string, string A, such that the assessment takes into consideration both weighted spelling change events from string A to string B, and weighted spelling change events from string B to string A.

50. The method as in claim 1, wherein analyzing the detected spelling change events comprises assessing whether a particular search string, string B, is a useful alternative spelling of another particular search string, string A, at least in part by comparing a frequency of occurrence of spelling change events from string A to string B to a frequency of occurrence of spelling change events from string B to string A.

51. The method of claim 50, wherein comparing said frequencies of occurrence comprises giving different non-zero amounts of weight to different spelling change events between string A and string B.

52. The method of claim 50, wherein comparing said frequencies of occurrence comprises calculating a first value representing a probability of a spelling change from string A to string B;

calculating a second value representing a probability of a spelling change from string B to string A, and comparing the first and second values.

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;

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 string are similar in spelling, and (2) detected spelling changes made to the first search string by each of a plurality of users, wherein the programmatic assessment comprises giving different non-zero amounts of weight to different detected spelling change events, at least some of said amounts of weight being dependent upon user actions performed during browsing sessions in which the corresponding spelling change events occurred, each detected spelling change event being specific to a particular user; and

storing a result of the programmatic assessment in computer storage.

19. The method of claim 18, wherein giving different amounts of weight to different detected spelling change events comprises, for a detected spelling change event of a user between the first search string and the second search string, calculating a weight value that depends upon an amount of time between submission by the user of the first search string and submission by the user of the second search string.

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 frequently 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 the 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 18, wherein giving different amounts of weight to different detected spelling change events comprises, for a detected spelling change event of a user between the first search string and the second search string, calculating a weight value that depends upon how many intervening actions were performed by the user between submitting the first search string and submitting the second search string.

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 assigning a respective weight value to each of a plurality of spelling change events from the first search string to the second search string, and combining said weight values.

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 users who submitted the second search string accessed corresponding search results.

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. The method of claim 18, wherein programmatically assessing whether the second search string represents a useful alternative spelling of the first search string comprises comparing a frequency of occurrence of spelling changes from the first search string to the second search string to a frequency of occurrence of spelling changes from the second search string to the first search string.

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 further taking into consideration weight values generated for particular spelling change events, each spelling change event and each weight value being specific to a particular user, each weight value being dependent upon one or more actions performed by the user to which the weight value corresponds, and representing a non-zero amount of weight to be given to a corresponding spelling change event; and

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

(a) suggesting the alternative search string to the user, (b) executing a search with the alternative search string, and outputting a result of the search to the user.

31. The method of claim 30, wherein the method comprises accessing a mapping table to look up the alternative search 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 data reflective of whether users who transition from the first search string to the alternative search string tend to select search results produced with the alternative search string.

33. The method of claim 30, wherein the alternative search string is selected based on a result of a programmatic assessment of whether the alternative search string is useful to users who submit the first search string, said programmatic assessment being based at least partly on search string spelling changes made by a plurality different users who submitted the first search string.

34. The method of claim 33, wherein the programmatic assessment is based in part upon search result viewing activity of users who submitted the alternative search string.

35. A computer-implemented method comprising:

generating spelling change event data descriptive of detected spelling changes made by each of a plurality of computer users, wherein generating the spelling change event data comprises calculating weights that represent amounts of weight to be given to corresponding spelling change events, each spelling change event being user-specific;

aggregating the spelling change event data, at least in part, by combining weights of like spelling change events;

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

when, 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;

wherein aggregating the spelling change event data comprises giving different non-zero amounts of weight to different spelling change events, such that some spelling change events are given more weight than others during the programmatic analysis of the aggregated spelling change event data.

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 generating the 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.

42. The method of claim 35, wherein the first and second strings are search strings submitted to a search engine, and wherein assessing whether the second string represents a useful alternative spelling of the first string comprises analyzing search result viewing activity of users who conducted a search using the second string.

43. The method of claim 35, wherein assessing whether the second string represents a useful alternative spelling of the first string comprises taking into consideration both spelling changes made by users from the first string to the second string, and spelling changes made by users from the second string to the first string.

44. The method of claim 35, wherein assessing whether the second string represents a useful alternative spelling of the first string comprises comparing a frequency of occurrence of spelling changes from the first string to the second string to a frequency of occurrence of spelling changes from the second string to the first string.

45. The method of claim 44, wherein comparing said frequencies of occurrence comprises giving more weight to some spelling change events than others.

46. The method of claim 44, wherein comparing said frequencies of occurrence comprises calculating a first value representing a probability of a spelling change from the first string to the second string;

calculating a second value representing a probability of a spelling change from the second string to the first string; and

comparing the first and second values.

47. The method of claim 35, wherein at least one of said weights corresponds to a search string spelling change event in which a user submitted a first search string and subsequently submitted a second search string, and is dependent upon one or more intervening actions performed by said user after submitting the first search string and before submitting the second search string.

48. The method of claim 35, wherein the steps of programmatically analyzing at least the aggregated spelling change event data and generating the mapping are performed in an off-line processing mode, and the method further comprises using the mapping to suggest the second string to users who submit the first string.

53. A computer-implemented method of detecting and analyzing search string spelling changes made by users, comprising:

identifying a first search string submission event in which a user submitted a first search string to search an electronic repository;

identifying a second search string submission event in which the user submitted a second search string to search the electronic repository, said second search string submission event representing a transition by the user from the first search string to the second search string;

determining that the first and second search strings are sufficiently similar in spelling to treat the transition as a search string spelling change event;

identifying one or more intervening events initiated by the user subsequent to the first search string submission event but prior to the second search string submission event;

calculating a weight for the search string spelling change event, said weight being dependent upon the one or more intervening events and representing a non-zero amount of weight to give to the search string spelling change event;

using said weight, in combination with weights corresponding to other search string spelling change events, to perform an assessment of whether the second search string represents a useful alternative spelling of the first search string, wherein each of said search string spelling change events is specific to a particular user, and at least some of the search string spelling change events correspond to different users than other search string spelling change events; and

storing a result of said assessment in computer storage.

54. The method of claim 53, wherein calculating the weight comprises taking into consideration the number of said one or more intervening events that occurred between the first and second search string submission events.

55. The method of claim 53, wherein calculating the weight comprises taking into consideration an amount of time between the first and second search string submission events.

56. The method of claim 53, wherein calculating the weight comprises taking into consideration a type of an intervening event that occurred between the first and second search string submission events.

57. The method of claim 53, wherein calculating the weight comprises taking into consideration whether the user selected a search result item after submitting the second search string.

58. The method of claim 53, wherein the method comprises using said weights to calculate a probability of occurrence of a spelling change from the first search string to the second search string, and using the probability of occurrence to assess whether the second search string represents a useful alternative spelling of the first search string.

59. The method of claim 53, wherein the weight value reflects a degree of nexus between the first and second search string submission events.