System, method, and service for matching pattern-based data

• US 20070005596A1
• Filed: 07/02/2005
• Published: 01/04/2007
• Est. Priority Date: 07/02/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Brown, Paul, Myllymaki, Jussi
• Granted Patent: US 7,487,150 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• 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

Abstract

A pattern-based data matching system matches pattern-based data. The data matching system generates a regular expression pattern for input datasets and describes similarity measures between the generated patterns. The data matching system analyzes an input dataset in terms of symbol classes, generalizing input values into a general pattern to allow identification or extrapolation of overlap between input datasets, aiding in matching fields in databases that are being merged and in learning a pattern for an input dataset. For each sequence of data values, the present system computes a compact pattern describing the sequence. Embodiments of the data matching system comprise noise reduction and repetitive pattern discovery in the input dataset and calculation of recall and precision of the generated pattern.

Claims

1. A method of matching pattern-based data, comprising:

deriving a first pattern from a first input set of values and a second pattern from a second input set of values;

computing a similarity of the first pattern and the second pattern; and

matching the first input set of values with the second input set of values based on the similarity computation.

2. The method of claim 1, further comprising generalizing the first derived pattern and the second derived pattern by representing symbols appearing in given positions in the values from the first and second sets of values with symbol classes.

3. The method of claim 2, wherein generalizing a pattern further comprises choosing symbol classes that minimize the expansion of symbols appearing in given positions in the values with members of the symbol classes.

4. The method of claim 2, further comprising partitioning symbol ranges into subsets;

and

wherein each subset is generalized separately to a symbol class.

5. The method of claim 1, further comprising identifying and removing delimiters from the first derived pattern and the second derived pattern.

6. The method of claim 1, further comprising identifying and removing noise from the first derived pattern and the second derived pattern.

7. The method of claim 6, wherein identifying noise further comprises computing the relative frequency of symbol occurrences appearing in given positions in values and selecting symbol occurrences whose frequency value is below a predetermined threshold.

8. The method of claim 1, further comprising discovering repetitive symbol sequences in the first derived pattern and the second derived pattern;

and

replacing repetitive symbol sequences with repetitive patterns.

9. The method of claim 8, wherein discovering a repetitive symbol sequence further comprises determining a minimum length of the repetitive sequence;

and

determining a maximum length of the repetitive sequence.

10. The method of claim 1, further comprising calculating a recall value for the first derived pattern and the second derived pattern by measuring the amount of noise removed from the first input set of values and the second input set of values.

11. The method of claim 3, further comprising calculating a precision value for the first derived pattern and the second derived pattern by measuring the total expansion of the first pattern and the second pattern.

12. The method of claim 1, wherein calculating the similarity of the first derived pattern and the second derived pattern comprises measuring the rate of convergence of the first derived pattern and the second derived pattern to a universal pattern.

13. The method of claim 1, wherein matching the first input set of values and the second input set of values comprises comparing the similarity of the first derived pattern and the second derived pattern to a threshold;

and

declaring the first set of input values and the second set of input values as a match if the similarity exceeds a predetermined threshold.

14. A system for matching pattern-based data, comprising:

a pattern construction module for deriving a first pattern from a first input set of values and a second pattern from a second input set of values;

a similarity computation module for computing a similarity of the first pattern and the second pattern; and

a matching module for matching the first input set of values with the second input set of values based on the similarity computation.

15. The system of claim 14, wherein the pattern construction module generalizes the first derived pattern and the second derived pattern by representing symbols appearing in given positions in the values from the first and second sets of values with symbol classes.

16. The system of claim 15, wherein the pattern construction module generalizes a pattern by choosing symbol classes that minimize the expansion of symbols appearing in given positions in the values with members of the symbol classes.

17. The system of claim 15, further comprising a controlled classification module for partitioning symbol ranges into subsets;

and

wherein each subset is generalized separately to a symbol class.

18. The system of claim 14, further comprising a delimiter removal module for identifying and removing delimiters from the first derived pattern and the second derived pattern.

19. A computer program product having a plurality of executable instruction codes that are stored on a computer-readable medium, for matching pattern-based data, comprising:

a first set of instruction codes for deriving a first pattern from a first input set of values and a second pattern from a second input set of values;

a second set of instruction codes for computing a similarity of the first pattern and the second pattern; and

a third set of instruction codes for matching the first input set of values with the second input set of values based on the similarity computation.

20. A method for providing a matching pattern-based data service, comprising:

receiving a first input set of values and a second input set of values;

invoking a hardware configuration utility, wherein the first input set of values and the second input set of values are made available to the automatic hardware configuration utility for derivation; and

matching derivation values from the hardware configuration utility based on similarity computation.