Query string matching method and apparatus

• US 20040141354A1
• Filed: 01/28/2003
• Published: 07/22/2004
• Est. Priority Date: 01/18/2003
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Carnahan, John M.
• Granted Patent: US 7,734,565 B2
• Time in Patent Office: Days
• US Class Current: 365/145
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

In one implementation, a method is provided for increasing relevance of database search results. The method includes receiving a subject query string and determining a trained edit distance between the subject query string and a candidate string using trained cost factors derived from a training set of labeled query transformations. A trained cost factor includes a conditional probability for mutations in labeled non-relevant query transformations and a conditional probability for mutations in labeled relevant query transformations. The candidate string is evaluated the for selection based on the trained edit distance. In some implementations, the cost factors may take into account the context of a mutation. As such, in some implementations multi-dimensional matrices are utilized which include the trained cost factors.

Claims

1. A method for increasing relevance of database search results, the method comprising:

receiving a subject query string;

determining a trained edit distance between the subject query string and at least one candidate string using trained cost factors derived from a training set of labeled query transformations such that a trained cost factor comprises a sum of a conditional probability for mutations in labeled non-relevant query transformations and a conditional probability for mutations in labeled relevant query transformations; and

evaluating the at least one candidate string for selection based on the trained edit distance.

2. The method of claim 1 wherein determining the trained edit distance comprises using at least one of:

(a) a substitutions matrix, (b) an insertions matrix, (c) a deletions matrix, or (d) a transpositions matrix.

3. The method of claim 2 wherein determining the trained edit distance comprises using trained cost factors associated with a context of a mutation.

4. The method of claim 3 wherein determining the trained edit distance comprises using trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

5. The method of claim 1 wherein determining the trained edit distance comprises using trained cost factors associated with a context of a mutation.

6. The method of claim 5 wherein determining the trained edit distance further comprises using trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

7. The method of claim 1 wherein determining the trained edit distance comprises using a multi-dimensional transition matrix comprising the trained cost factors.

8. The method of claim 7 wherein determining the trained edit distance comprises using trained cost factors associated with a context of a mutation.

9. The method of claim 8 wherein determining the trained edit distance comprises using a multi-dimensional transition matrix comprising trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

10. The method of claim 1 selecting at least one candidate string corresponding to the subject query string based on the trained edit distance.

11. The method of claim 10 wherein selecting the at least one candidate string comprises selecting a candidate string that is an approximate match with the subject query string.

12. The method of claim 11 providing a search result based on the selected candidate string.

13. The method of claim 10 wherein selecting the at least one candidate string comprises selecting a candidate string that is an exact match with the subject query string.

14. The method of claim 13 providing a search result based on the selected candidate string.

15. The method of claim 1 further comprising:

providing a list of candidate strings; and

wherein determining the trained edit distance comprises using the list of candidate strings.

16. The method of claim 1 further comprising:

providing an abbreviated list of candidate strings from a group of candidate strings; and

wherein determining the trained edit distance comprises using the abbreviated list of candidate strings.

17. The method of claim 16 wherein providing the abbreviated list of candidate strings comprises providing candidate strings within a uniform edit distance of the subject query string.

18. The method of claim 17 wherein providing the abbreviated list of candidate strings comprises providing candidate strings within an edit distance based on a character length of the subject query string.

19. The method of claim 16 further comprising determining whether the subject query string has an exact match within the group of candidate strings prior to providing the abbreviated list of candidate strings.

20. The method of claim 1 further comprising:

searching for an exact match for the subject query string prior to determining the trained edit distance; and

determining the trained edit distance if an exact match for the subject query string is not found.

21. A method for increasing relevance of database search results, the method comprising:

receiving a subject query string;

determining a trained edit distance between the subject query string and at least one candidate string using multi-dimensional matrices comprising trained cost factors derived from a training set; and

evaluating the at least one candidate string for selection based on the trained edit distance.

22. The method of claim 21 wherein determining the trained edit distance comprises using multi-dimensional matrices derived from labeled query transformations such that a trained cost factor comprises a sum of a conditional probability for mutations in labeled non-relevant query transformations and a conditional probability for mutations in labeled relevant query transformations.

23. The method of claim 21 wherein determining the trained edit distance comprises using at least one of:

(a) a multi-dimensional substitutions matrix, (b) a multi-dimensional insertions matrix, (c) a multi-dimensional deletions matrix, or (d) a multi-dimensional transpositions matrix.

24. The method of claim 23 wherein determining the trained edit distance comprises using a multi-dimensional transition matrix comprising trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

25. The method of claim 21 wherein determining the trained edit distance comprises using a multi-dimensional transition matrix comprising trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

26. The method of claim 21 further comprising:

selecting at least one candidate string corresponding to the subject query string based on the trained edit distance, wherein selecting the at least one candidate string comprises selecting a candidate string that is one of;

(a) an exact match;

or (b) an approximate match with the subject query string; and

providing a search result based on the selected candidate string.

27. The method of claim 21 further comprising searching for an exact match for the subject query string in a group of candidate strings prior to determining the trained edit distance and performing one of:

(a) selecting an exact match for the subject query string from the group of candidate strings, or (b) selecting at least one candidate string from the group of candidate strings based on the trained edit distance.

28. The method of claim 21 wherein determining the trained edit distance comprises using a list of candidate strings.

29. The method of claim 21 wherein determining the trained edit distance comprises using an abbreviated list of candidate strings within a uniform edit distance of the subject query string.

30. A method for estimating edit distance costs comprising calculating and combining conditional probabilities that a selected mutation will result in non-relevant transformations and that the selected mutation will result in relevant transformations based on a training set of labeled string pairs.

31. The method of claim 30 further comprising evaluating a context of the selected mutation.

32. The method of claim 31 wherein evaluating a context of the selected mutation comprises evaluating at least one of:

(a) a position of a mutation in a string, (b) a size of a string, (c) at least one other mutation within a string, (d) a character in a string, or (e) character combinations within a string.

33. The method of claim 30 further comprising:

obtaining a training set comprising query string pairs, each pair comprising at least one mutation;

evaluating each query string pair and assigning a relevancy label to each query string pair;

determining a conditional probability for the selected mutation in labeled non-relevant transformations;

determining a conditional probability for the selected mutation in labeled relevant transformations; and

combining the conditional probability for the selected mutation in labeled non-relevant transformations and the conditional probability for the selected mutation in labeled relevant transformations so as to provide an estimated edit distance cost for the selected mutation.

34. The method of claim 33 further comprising evaluating a context of the selected mutation.

35. The method of claim 34 wherein evaluating a context of the selected mutation comprises evaluating at least one of:

(a) a position of a mutation in a string, (b) a size of a string, (c) at least one other mutation within a string, (d) a character in a string, or (e) character combinations within a string.

36. A method for increasing relevance of database search results, the method comprising:

receiving a subject query string;

determining a trained edit distance between the subject query string and at least one candidate string using multi-dimensional matrices comprising trained cost factors derived from a training set of labeled query transformations such that the trained cost factors each comprise a sum of a conditional probability for mutations in labeled non-relevant query transformations and a conditional probability for mutations in labeled relevant query transformations and such that the trained cost factors each include at least one of;

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string; and

selecting a candidate string that is one of (a) an approximate match with the subject query string, or (b) an exact match with the subject query string based an evaluation of the trained edit distance of the at least one candidate string.

37. The method of claim 36 further comprising:

providing a list of candidate strings; and

wherein determining the trained edit distance comprises using the list of candidate strings.

38. The method of claim 36 further comprising:

providing an abbreviated list of candidate strings from a group of candidate strings; and

wherein determining the trained edit distance comprises using the abbreviated list of candidate strings.

39. The method of claim 38 wherein providing the abbreviated list of candidate strings comprises providing candidate strings within a uniform edit distance of the subject query string.

40. The method of claim 36 further comprising:

searching for an exact match for the subject query string prior to determining the trained edit distance; and

determining the trained edit distance and evaluating for selection if an exact match for the subject query string is not found.

41. A system for improved database searching, the system comprising:

a computer adapted to receive a subject query string for searching a searchable database;

a processor associated with the computer, the processor being programmed to;

determine a trained edit distance between the subject query string and at least one candidate string from the searchable database using trained cost factors derived from a training set of labeled query transformations such that a trained cost factor comprises a sum of a conditional probability for mutations in labeled non-relevant query transformations and a conditional probability for mutations in labeled relevant query transformations; and

perform an evaluation of the at least one candidate string for selection based on the trained edit distance; and

return a search result based on the evaluation.

42. The system of claim 41 wherein the processor is programmed to determine the trained edit distance using at least one of:

(a) a substitutions matrix, (b) an insertions matrix, (c) a deletions matrix, or (d) a transpositions matrix.

43. The method of claim 42 wherein the processor is programmed to determine the trained edit distance using trained cost factors associated with a context of a mutation.

44. The system of claim 43 wherein the processor is programmed to determine the trained edit distance using trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

45. The system of claim 41 wherein the processor is programmed to determine the trained edit distance using trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

46. The system of claim 41 wherein the processor is programmed to determine the trained edit distance using a multi-dimensional transition matrix comprising the trained cost factors.

47. The system of claim 46 wherein the processor is programmed to determine the trained edit distance using a multi-dimensional transition matrix comprising trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

48. The system of claim 46 wherein the processor is programmed to determine the trained edit distance using at least one of:

(a) a multi-dimensional substitutions matrix, (b) a multi-dimensional insertions matrix, (c) a multi-dimensional deletions matrix, or (d) a multi-dimensional transpositions matrix.

49. The system of claim 41 wherein the processor is programmed to:

provide a list of candidate strings; and

determine the trained edit distance using the list of candidate strings.

50. The system of claim 41 wherein the processor is programmed to:

provide an abbreviated list of candidate strings from a group of candidate strings; and

determine the trained edit distance using the abbreviated list of candidate strings.

51. The system of claim 50 wherein the processor is programmed to provide the abbreviated list of candidate strings within a uniform edit distance of the subject query string.

52. The system of claim 50 wherein the processor is programmed to determine whether the subject query string has an exact match within the group of candidate strings prior to providing the abbreviated list of candidate strings.

53. The system of claim 41 wherein the processor is programmed to:

search for an exact match for the subject query string prior to determining the trained edit distance; and

determine the trained edit distance if an exact match for the subject query string is not found.

54. A computer readable medium comprising computer-executable instructions for performing query string matching, the method comprising:

receiving a subject query string;

determining a trained edit distance between the subject query string and at least one candidate string using cost factors comprising conditional probabilities that a selected mutation will result in non-relevant transformations and that the selected mutation will result in relevant transformations based on a training set of labeled string pairs; and

evaluating the at least one candidate string for selection based on the trained edit distance.

55. The medium of claim 54 wherein the method comprises:

determining the trained edit distance between the subject query string and the at least one candidate string using trained cost factors derived from a training set of labeled query transformations such that a trained cost factor comprises a sum of a conditional probability for mutations in labeled non-relevant query transformations and a conditional probability for mutations in labeled relevant query transformations.

56. The medium of claim 54 wherein the method comprises using at least one of:

(a) a substitutions matrix, (b) an insertions matrix, (c) a deletions matrix, or (d) a transpositions matrix.

57. The method of claim 54 wherein the method comprises using at least one multi-dimensional transition matrix comprising the relative cost factor.

58. The method of claim 57 wherein the method comprises using trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.

59. The method of claim 54 wherein the method comprises using trained cost factors associated with a context of a mutation.

60. The method of claim 59 wherein estimating edit distance costs comprises using trained cost factors including at least one of:

(a) trained costs based on a position of a mutation in a string, (b) trained costs of a mutation based on a size of a string, (c) trained costs of a mutation considering at least one other mutation within a string, (d) trained costs of a mutation in view of a character in a string, or (e) trained costs of a mutation in view of character combinations within a string.