Similarity string filtering

• US 7,283,999 B1
• Filed: 12/19/2003
• Issued: 10/16/2007
• Est. Priority Date: 12/19/2003
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Ramesh, Bhashyam, Watzke, Michael W.
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Vy; Hung Tran
• Application Number:
  US10/740,780
• Time in Patent Office: 1,397 Days
• Field of Search: 707 1- 6, 707100-102, 370/401, 382/310
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method, computer program and system for optimizing similarity string filtering are disclosed. A first data string comprising one or more data characters and selecting a second data string comprising one or more data characters are selected. At least one of a defined set of shapes is applied to the first data string to generate one or more patterns associated with the first data string. At least one of the defined set of shapes is applied to the second data string to generate one or more patterns associated with the second data string. The one or more patterns associated with the first data string are compared with the one or more patterns associated with the second data string to determine if one or more matching patterns exist. The first data string and the second data string are linked if one or more matching patterns exist.

Claims

1. A method for optimizing similarity string filtering, the method comprising:

selecting a first data string comprising one or more data characters;

selecting a second data string comprising one or more data characters;

applying at least one of a defined set of shapes to the first data string to generate one or more patterns associated with the first data string, each of the shapes in the defined set of shapes capable of being configured to apply an operation, where the operation is a skip operation, a transposition operation, or a stop operation;

applying at least one of the defined set of shapes to the second data string to generate one or more patterns associated with the second data string;

comparing the one or more patterns associated with the first data string with the one or more patterns associated with the second data string to determine if one or more matching patterns exist; and

linking the first data string and the second data string if one or more matching patterns exist.

2. The method of claim 1, wherein the one or more patterns associated with the first data string and the one or more patterns associated with the second data string are compared based on equality.

3. The method of claim 1, further comprising performing a similarity measure on the linked first and second data strings.

4. The method of claim 3, wherein performing a similarity measure comprises calculating an edit distance for the first and second data strings, the edit distance comprising a measure of the number of insertions, deletions, substitutions, or transpositions needed to transform the second data string into the first data string.

5. The method of claim 1, further comprising:

determining that a plurality of matching patterns exist; and

eliminating all duplicate matching patterns.

6. The method of claim 5, wherein eliminating all duplicate matching patterns comprises performing a DISTINCT function.

7. The method of claim 1, further comprising:

selecting the defined set of shapes based upon a desired error tolerance and the number of data characters in the first data string.

8. The method of claim 7, wherein each shape in the defined set of shapes comprises one or more data characters, the number of data characters in each shape related to the number of data characters in the first data string and the number of characters in the second data string.

9. The method of claim 1, wherein:

the first data string is comprised of a first number of data characters and the second data string is comprised of a second number of data characters; and

the at least one of the defined set of shapes applied to the first data string being is the same as the at least one of the defined set of shapes applied to the second data string.

10. The method of claim 9, wherein the defined set of shapes operate to embed a length filter into the one or more patterns associated with the first data string and the one or more patterns associated with the second data string.

11. The method of claim 1, wherein applying the at least one of the defined set of shapes to the first data string comprises rotating the at least one of the defined set of shapes through the first data string.

12. The method of claim 1, wherein the at least one of the defined set of shapes comprises a length of one or more characters, the length operable to generate a maximum number of unique patterns associated with the first data string when the at least one of the defined set of shapes is applied to the first data string.

13. The method of claim 12, wherein the length is operable to generate a maximum number of unique patterns associated with the second data string when the at least one of the defined set of shapes is applied to the second data string.

14. A method for optimizing similarity string filtering, the method comprising:

selecting a first set of data strings, each data string comprising one or more data characters;

applying at least one of a defined set of shapes to the first set of data strings to generate a first set of patterns associated with the first set of data strings, each of the shapes in the defined set of shapes capable of being configured to apply an operation, where the operation is a skip operation, a transposition operation, or a stop operation;

selecting a second set of data strings, each data string comprising one or more data characters;

applying at least one of the defined set of shapes to the second set of data strings to generate a second set of patterns associated with the second set of data strings;

comparing the first set of patterns with the second set of patterns to determine at least one matching pattern, a matching pattern comprising at least one pattern from the first set of patterns and at least one pattern from the second set of patterns; and

linking a first data string associated with the at least one pattern from the first set of patterns in the matching pattern and a second data string associated with the at least one pattern from the second set of patterns in the matching patterns.

15. The method of claim 14, wherein the first set of patterns associated with the first set of data strings and the second set of patterns associated with the second set of data string are compared based on equality.

16. The method of claim 14, further comprising performing a similarity measure on the linked first and second data strings.

17. The method of claim 16, wherein performing a similarity measure comprises calculating an edit distance for the linked first and second data strings, the edit distance comprising a measure of the number of insertions, deletions, substitutions, or transpositions needed to transform the second data string into the first data string.

18. The method of claim 14, further comprising:

determining that a plurality of matching patterns exist; and

eliminating all duplicate matching patterns.

19. The method of claim 18, wherein eliminating all duplicate matching patterns comprises performing a DISTINCT function.

20. The method of claim 14, further comprising:

selecting the defined set of shapes based upon a desired error tolerance and the number of data characters in each data string in the first set of data strings.

21. The method of claim 20, wherein each shape in the defined set of shapes comprises one or more data characters, the number of data characters in each shape related to the number of data characters in the each data string in the first set of data string and the number of characters in each data string in the second set of data strings.

22. The method of claim 14, wherein:

each data string in the first set of data strings is comprised of a first number of data characters and each data string in the second set of data strings is comprised of a second number of data characters; and

the at least one of the defined set of shapes applied to the first set of data strings is the same as the at least one of the defined set of shapes applied to the second set of data strings.

23. The method of claim 22, wherein the defined set of shapes operate to embed a length filter into the first and second sets of patterns.

24. The method of claim 14, wherein applying the at least one of the defined set of shapes to the first set of data strings comprises rotating the at least one of the defined set of shapes through each of data string in the first set data strings.

25. The method of claim 14, wherein the at least one of the defined set of shapes comprises a length of one or more characters, the length operable to generate a maximum number of unique patterns associated with the first set of data strings when the at least one of the defined set of shapes is applied to the first set of data strings.

26. The method of claim 25, wherein the length is operable to generate a maximum number of unique patterns associated with the second set of data strings when the at least one of the defined set of shapes is applied to the second set of data strings.

27. A computer program, stored on a tangible storage medium, for optimizing similarity string filtering, the program including executable instructions that cause a computer to:

select a first data string comprising one or more data characters;

select a second data string comprising one or more data characters;

apply at least one of a defined set of shapes to the first data string to generate one or more patterns associated with the first data string;

apply at least one of the defined set of shapes to the second data string to generate one or more patterns associated with the second data string, each of the shapes in the defined set of shapes capable of being configured to apply an operation, where the operation is a skip operation, a transposition operation, or a stop operation;

compare the one or more patterns associated with the first data string with the one or more patterns associated with the second data string to determine if one or more matching patterns exist; and

link the first data string and the second data string if one or more matching patterns exist.

28. The computer program of claim 27, wherein the one or more patterns associated with the first data string and the one or more patterns associated with the second data string are compared based on equality.

29. The computer program of claim 27, further including executable instructions that cause the computer to perform a similarity measure on the linked first and second data strings.

30. The computer program of claim 29, further including executable instructions that cause the computer to calculating an edit distance for the first and second data strings when performing a similarity measure, the edit distance comprising a measure of the number of insertions, deletions, substitutions, or transpositions needed to transform the second data string into the first data string.

31. The computer program of claim 27, further including executable instructions that cause the computer to:

determine that a plurality of matching patterns exist; and

eliminate all duplicate matching patterns.

32. The computer program of claim 31, further including executable instructions that cause the computer to perform a DISTINCT function when eliminating all duplicate matching patterns.

33. The computer program of claim 27, further including executable instructions that cause the computer to:

select the defined set of shapes based upon a desired error tolerance and the number of data characters in the first data string.

34. The computer program of claim 33, wherein each shape in the defined set of shapes comprises one or more data characters, the number of data characters in each shape related to the number of data characters in the first data string and the number of characters in the second data string.

35. The computer program of claim 27, wherein:

the first data string is comprised of a first number of data characters and the second data string is comprised of a second number of data characters; and

the at least one of the defined set of shapes applied to the first data string being is the same as the at least one of the defined set of shapes applied to the second data string.

36. The computer program of claim 35, wherein the defined set of shapes operate to embed a length filter into the one or more patterns associated with the first data string and the one or more patterns associated with the second data string.

37. The computer program of claim 27, further including executable instructions that cause the computer to rotate the at least one of the defined set of shapes through the first data string when applying the at least one of the defined set of shapes to the first data string.

38. The computer program of claim 27, wherein the at least one of the defined set of shapes comprises a length of one or more characters, the length operable to generate a maximum number of unique patterns associated with the first data string when the at least one of the defined set of shapes is applied to the first data string.

39. The computer program of claim 38, wherein the length is operable to generate a maximum number of unique patterns associated with the second data string when the at least one of the defined set of shapes is applied to the second data string.

40. A computer program, stored on a tangible storage medium, for optimizing similarity string filtering, the program including executable instructions that cause a computer to:

select a first set of data strings, each data string comprising one or more data characters;

apply at least one of a defined set of shapes to the first set of data strings to generate a first set of patterns associated with the first set of data strings, each of the shapes in the defined set of shapes capable of being configured to apply an operation, where the operation is a skip operation, a transposition operation, or a stop operation;

select a second set of data strings, each data string comprising one or more data characters;

apply at least one of the defined set of shapes to the second set of data strings to generate a second set of patterns associated with the second set of data strings;

compare the first set of patterns with the second set of patterns to determine at least one matching pattern, a matching pattern comprising at least one pattern from the first set of patterns and at least one pattern from the second set of patterns; and

link a first data string associated with the at least one pattern from the first set of patterns in the matching pattern and a second data string associated with the at least one pattern from the second set of patterns in the matching patterns.

41. The computer program of claim 40, wherein the first set of patterns associated with the first set of data strings and the second set of patterns associated with the second set of data string are compared based on equality.

42. The computer program of claim 40, further including executable instructions that cause a computer to perform a similarity measure on the linked first and second data strings.

43. The computer program of claim 42, further including executable instructions that cause a computer to calculate an edit distance for the linked first and second data strings when performing the similarity measure, the edit distance comprising a measure of the number of insertions, deletions, substitutions, or transpositions needed to transform the second data string into the first data string.

44. The computer program of claim 40, further including executable instructions that cause a computer to:

determine that a plurality of matching patterns exist; and

eliminate all duplicate matching patterns.

45. The computer program of claim 44, further including executable instructions that cause a computer to perform a DISTINCT function when eliminating all duplicate matching patterns.

46. The computer program of claim 40, further including executable instructions that cause a computer to:

select the defined set of shapes based upon a desired error tolerance and the number of data characters in each data string in the first set of data strings.

47. The computer program of claim 46, wherein each shape in the defined set of shapes comprises one or more data characters, the number of data characters in each shape related to the number of data characters in the each data string in the first set of data string and the number of characters in each data string in the second set of data strings.

48. The computer program of claim 40, wherein:

each data string in the first set of data strings is comprised of a first number of data characters and each data string in the second set of data strings is comprised of a second number of data characters; and

the at least one of the defined set of shapes applied to the first set of data strings is the same as the at least one of the defined set of shapes applied to the second set of data strings.

49. The computer program of claim 48, wherein the defined set of shapes operate to embed a length filter into the first and second sets of patterns.

50. The computer program of claim 40, further including executable instructions that cause a computer to rotating the at least one of the defined set of shapes through each of data string in the first set data strings when applying the at least one of the defined set of shapes to the first set of data strings.

51. The computer program of claim 40, wherein the at least one of the defined set of shapes comprises a length of one or more characters, the length operable to generate a maximum number of unique patterns associated with the first set of data strings when the at least one of the defined set of shapes is applied to the first set of data strings.

52. The computer program of claim 51, wherein the length is operable to generate a maximum number of unique patterns associated with the second set of data strings when the at least one of the defined set of shapes is applied to the second set of data strings.