Efficient data pattern matching

Patent metadata

Field	Value
Publication number	US-10318397-B2
Application number	US-201313863196-A
Country	US
Kind code	B2
Filing date	Apr 15, 2013
Priority date	Apr 15, 2013
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

Abstract

Exemplary methods, apparatuses, and systems parse data with a plurality of pattern matching rules. Pattern matching rules are applied in an ordered sequence and a first rule is applied to the data before a second rule is applied to the data. In response to determining the second rule matches the data, the sequence is reordered to apply the second rule prior to the first rule.

First claim

What is claimed is:

1. A computer-implemented method of parsing data using a plurality of pattern matching rules, the method comprising:
receiving, by a network computer, data as input to be parsed;
determining a classification of each of a plurality of pattern matching rules, wherein a first rule of the plurality of pattern matching rules is classified as a parent rule, a second rule of the plurality of pattern matching rules is classified as an independent rule, and a third rule of the plurality of pattern matching rules is classified as a child rule of the first rule, wherein a parent rule encompasses a matching scope of a child rule of the parent rule, and wherein an independent rule is neither a parent rule of another rule nor a child rule of another rule, and wherein the first rule includes a constant text string and one or more regular expression operators that define variable patterns of characters that occur prior to or following the text string in order to satisfy the first rule;
determining, by a processing resource, a predicted amount of time respective pattern matching rules among the plurality of pattern matching rules will take to be executed by the processing resource; and
ordering the plurality of pattern matching rules based, at least in part, on the predicted amount of time respective pattern matching rules among the plurality of pattern matching rules will take to be executed by the processing resource, such that the rules are to be applied in an ordered sequence such that the first rule is applied to the data before the second rule is applied to the data in response to determining the first rule is a parent rule and the second rule is an independent rule;
parsing the data based upon the ordered sequence by applying the first rule;
determining the first rule finds no match in the data; and
bypassing an application of the third rule to the data based upon determining the first rule finds no match in the data.

2. The method of claim 1 , further comprising:
bypassing application of one or more additional rules related to the first rule in response to determining the first rule is unable to match the data.

3. The method of claim 1 , further comprising:
reordering the sequence to apply one or more rules related to the second rule prior to the first rule in response to determining the second rule matches the data.

4. The method of claim 1 , wherein the data is unstructured data combined from a plurality of different data sources.

5. The method of claim 1 , wherein the ordering of the plurality of pattern matching rules includes ordering parent rules within the plurality of pattern matching rules based upon a number of child rules each parent rule has.

6. The method of claim 1 , the method further comprising:
determining the second rule matches the data; and
reordering the sequence to apply the second rule prior to the first rule in response to determining the second rule matches the data.

7. The method of claim 6 , further comprising:
bypassing all remaining pattern matching rules in the sequence to apply upon determining the second rule matches the data.

8. A non-transitory computer-readable medium storing instructions, which when executed by a processing device, cause the processing device to perform method comprising:
receiving, by a server computer, data as input to be parsed;
determining a classification of each of a plurality of pattern matching rules, wherein a first rule of the plurality of pattern matching rules is classified as a parent rule, a second rule of the plurality of pattern matching rules is classified as an independent rule, and a third rule of the plurality of pattern matching rules is classified as a child rule of the first rule, wherein a parent rule encompasses a matching scope of a child rule of the parent rule, and wherein an independent rule is neither a parent rule of another rule nor a child rule of another rule, and wherein the first rule includes a constant text string and one or more regular expression operators that define variable patterns of characters that occur prior to or following the text string in order to satisfy the first rule;
determining, by a processing resource, a predicted amount of time respective pattern matching rules among the plurality of pattern matching rules will take to be executed by the processing resource;
ordering the plurality of pattern matching rules based, at least in part, on the predicted amount of time respective pattern matching rules among the plurality of pattern matching rules will take to be executed by the processing resource, such that the rules are to be applied in an ordered sequence such that the first rule is applied to the data before the second rule is applied to the data in response to determining the first rule is a parent rule and the second rule is an independent rule;
parsing the data based upon the ordered sequence by applying the first rule;
determining the first rule finds no match in the data; and
bypassing an application of the third rule to the data based upon determining the first rule finds no match in the data.

9. The medium of claim 8 , the method further comprising:
bypassing application of one or more additional rules related to the first rule in response to determining the first rule is unable to match the data.

10. The medium of claim 8 , the method further comprising:
reordering the sequence to apply one or more rules related to the second rule prior to the first rule in response to determining the second rule matches the data.

11. The medium of claim 8 , wherein the data is unstructured data combined from a plurality of different data sources.

12. The medium of claim 8 , wherein the ordering of the plurality of pattern matching rules includes ordering parent rules within the plurality of pattern matching rules based upon a number of child rules each parent rule has.

13. The medium of claim 8 , the method further comprising:
determining the second rule matches the data; and
reordering the sequence to apply the second rule prior to the first rule in response to determining the second rule matches the data.

14. The medium of claim 13 , the method further comprising:
bypassing all remaining pattern matching rules in the sequence to apply upon determining the second rule matches the data.

15. An apparatus comprising:
a processing device, wherein the processing device executes instructions that cause a computer to:
receive data as input to be parsed;
determine a classification of each of a plurality of pattern matching rules, wherein a first rule of the plurality of pattern matching rules is classified as a parent rule, a second rule of the plurality of pattern matching rules is classified as an independent rule, and a third rule of the plurality of pattern matching rules is classified as a child rule of the first rule, wherein a parent rule encompasses a matching scope of a child rule of the parent rule, and wherein an independent rule is neither a parent rule of another rule nor a child rule of another rule, and wherein the first rule includes a constant text string and one or more regular expression operators that define variable patterns of characters that occur prior to or following the text string in order to satisfy the first rule;
determine, by the processing device, a predicted amount of time respective pattern matching rules among the plurality of pattern matching rules will take to be executed by the processing resource;
order the plurality of pattern matching rules based, at least in part, on the predicted amount of time respective pattern matching rules among t

Assignees

• Vmware Inc

Inventors

• Huang Chengdu
• Li Zhenmin
• Xanthos Spiros

Classifications

• G06F11/3086

  where the reporting involves the use of self describing data formats, i.e. metadata, markup languages, human readable formats · CPC title

• G06F11/0706

  the processing taking place on a specific hardware platform or in a specific software environment · CPC title

• G06F11/3072 Primary

  where the reporting involves data filtering, e.g. pattern matching, time or event triggered, adaptive or policy-based reporting · CPC title

• G06F11/0751

  Error or fault detection not based on redundancy (power supply failures G06F1/30; network fault management H04L41/06) · CPC title