System for matching pattern-based data

• US 7,912,805 B2
• Filed: 12/15/2008
• Issued: 03/22/2011
• Est. Priority Date: 07/02/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Myllymaki, Jussi Petri, Brown, Paul Geoffrey
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): BUSS, BENJAMIN J
• Application Number:
  US12/335,309
• Publication Number:
  US 20090132454A1
• Time in Patent Office: 827 Days
• Field of Search: 707/737, 707/749, 707/750, 707/776, 707/999.006, 706/20, 706/48
• US Class Current: 706/48
• 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 system for matching pattern-based data, comprising a computer which executes:

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;

a learning module, wherein the system learns the first pattern and the second pattern by constructing an automaton comprised of nodes and transitions between the nodes, and support levels are calculated for the nodes;

a delimiter removal module that removes one or more delimiters from the first pattern by calculating the support level at one of the nodes by summing support values of incoming transitions to that node;

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

an output module that outputs the similarity match to a user.

2. The system of claim 1, 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.

3. The system of claim 2, 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.

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

and

wherein each subset is generalized separately to a symbol class.

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

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

instruction codes that derive a first pattern from a first input set of values and a second pattern from a second input set of values;

instruction codes that compute a similarity of the first pattern and the second pattern;

instruction codes that perform a learning of the first pattern and the second pattern by constructing an automaton comprised of nodes and transitions between the nodes;

instruction codes that calculate support levels for the nodes;

instruction codes that remove one or more delimiters from the first pattern by calculating the support level at one of the nodes by summing support values of incoming transitions to that node;

instruction codes that match the first input set of values with the second input set of values based on the similarity computation; and

instruction codes that output the similarity match to a user.

7. 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 by using a computer processor a similarity of the first pattern and the second pattern;

performing a learning of the first pattern and the second pattern by constructing an automaton comprised of nodes and transitions between the nodes;

calculating support levels for the nodes;

removing one or more delimiters from the first pattern by calculating the support level at one of the nodes by summing support values of incoming transitions to that node;

initializing an expansion factor;

expanding a language of the first and second patterns at the expansion factor, the expanding of the language diminishing a size of the first and second patterns and decreasing a precision of the first and second patterns;

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

outputting the similarity match to a user.