Computer system programmed to identify common subsequences in logs

• US 10,664,481 B2
• Filed: 09/29/2015
• Issued: 05/26/2020
• Est. Priority Date: 09/29/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Attias, Roberto, Prieto, Alberto Gonzalez
• Primary Examiner(s): Mackes, Kris E
• Assistant Examiner(s): Lin, Allen S
• Application Number:
  US14/869,859
• Publication Number:
  US 20170091190A1
• Time in Patent Office: 1,701 Days
• Field of Search: 707727
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: G06F 16/1727 Details of free space management performed by the file system saving storage space on storage systems G06F3/0608; management of blocks in storage devices G06F3/064
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 17/40 Data acquisition and logging for input to computer G06F3/00
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A data processing method includes receiving a stream of digital data with a plurality of objects and, in response to receiving an object, tokenizing the object to create a tokenized object, and storing the tokenized object in a token database. The method further includes comparing the tokenized object to a plurality of other tokenized objects stored in the token database, computing a pattern associated with the tokenized object, storing the pattern in a pattern database, and managing a size of the pattern database by identifying, a subset of patterns that are eligible for deletion from the pattern database based on an age of each pattern, ranking each pattern of the subset based on a quality and a popularity metric, identifying, based on the ranking and from the subset, a second pattern and deleting the second pattern from the pattern database to produce an updated database.

Claims

1. A method comprising:

using a computer, receiving a stream of digital data comprising a plurality of objects;

using programmed tokenizer instructions executed using the computer, in response to receiving a first object of the plurality of objects, tokenizing the first object to create a first tokenized object and electronically digitally storing the first tokenized object in a token database that comprises a plurality of other tokenized objects and using an electronic digital storage device;

using the computer, comparing the first tokenized object to the plurality of other tokenized objects stored in the token database, computing a first pattern including the first tokenized object having a constant sequence placed within characters of the first tokenized object, wherein the constant sequence identifies a subsequence of characters in at least two objects of the plurality of objects that are different, and storing the first pattern in a pattern database that comprises a plurality of patterns;

using the computer, managing a size of the pattern database by;

identifying, from the plurality of patterns, a subset of patterns that are eligible for deletion from the pattern database based on an age of each pattern and storing in computer memory data identifying the subset of patterns;

ranking each pattern of the subset based on a quality metric and a popularity metric, by marking the data identifying the subset of patterns with rank values, wherein the popularity metric is a hit count of an associated pattern, and wherein the quality metric comprises a function of a length of the constant sequence placed within characters of a tokenized object of an associated pattern;

identifying a lowest ranked pattern from the subset for deletion including determining a longest length of the constant sequence placed within characters of a tokenized object of an associated pattern; and

repeating the tokenizing, comparing and storing using the updated database;

wherein the method is executed using one or more computing devices.

2. The method of claim 1, wherein the token database is a fixed size circular buffer.

3. The method of claim 1, wherein the first pattern is computed using a longest subsequence match algorithm.

4. The method of claim 1, wherein the size is between 25 and 1000 patterns.

5. The method of claim 1, wherein the age further comprises a grace period based on the size of the pattern database and a number of new patterns added to the pattern database after a pattern associated with the age, wherein the pattern associated with the age is not eligible for deletion during the grace period.

6. The method of claim 1, wherein the quality metric comprises a function of a ratio of the constant sequence length and a total length of a pattern.

7. The method of claim 1, wherein the plurality of objects are not pre-defined.

8. A method comprising:

using a computer, managing a size of a pattern database that stores a plurality of patterns, each pattern of the plurality of patterns including a tokenized object having a constant sequence placed within characters of the first tokenized object, wherein the constant sequence identifies a subsequence of characters in at least two objects that are different, by;

identifying, from the plurality of patterns, a subset of patterns that are eligible for deletion from the pattern database based on an age of each pattern and storing in computer memory data identifying the subset of patterns;

ranking each pattern of the subset based on a quality metric and a popularity metric, by marking the data identifying the subset of patterns with rank values, wherein the popularity metric is a hit count of an associated pattern, and wherein the quality metric comprises a function of a length of the constant sequence placed within characters of a tokenized object of an associated pattern;

identifying a lowest ranked pattern from the subset for deletion including determining a longest length of the constant sequence placed within characters of a tokenized object of an associated pattern; and

deleting the pattern from the pattern database to produce an updated database;

wherein the method is executed using one or more computing devices.

9. The method of claim 8, wherein the size is between 25 and 1000 patterns.

10. The method of claim 8, wherein the age further comprises a grace period based on the size of the pattern database and an amount of new patterns added to the pattern database after a pattern associated with the age, wherein the pattern associated with the age is not eligible for deletion during the grace period.

11. A computing device comprising:

one or more processors; and

one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to;

receive a stream of digital data comprising a plurality of objects;

in response to receiving a first object of the plurality of objects, tokenize the first object to create a first tokenized object and electronically digitally store the first tokenized object in a token database that comprises a plurality of other tokenized objects and using an electronic digital storage device;

compare the first tokenized object to the plurality of other tokenized objects stored in the token database, computing a first pattern including the first tokenized object having a constant sequence placed within characters of the first tokenized object, wherein the constant sequence identifies a subsequence of characters in at least two objects of the plurality of objects that are different, and storing the first pattern in a pattern database that comprises a plurality of patterns;

manage a size of the pattern database by;

identifying, from the plurality of patterns, a subset of patterns that are eligible for deletion from the pattern database based on an age of each pattern and storing in computer memory data identifying the subset of patterns;

ranking each pattern of the subset based on a quality metric and a popularity metric, by marking the data identifying the subset of patterns with rank values, wherein the popularity metric is a hit count of an associated pattern, and wherein the quality metric comprises a function of a length of the constant sequence placed within characters of a tokenized object of an associated pattern;

identifying a lowest ranked pattern from the subset for deletion including determining a longest length of the constant sequence placed within characters of a tokenized object of an associated pattern; and

repeating the tokenizing, comparing and storing using the updated database.

12. The computing device of claim 11, wherein the token database is a fixed size circular buffer.

13. The computing device of claim 11, wherein the first pattern is computed using a longest subsequence match algorithm.

14. The computing device of claim 11, wherein the size is between 25 and 1000 patterns.

15. The computing device of claim 11, wherein the age further comprises a grace period based on the size of the pattern database and a number of new patterns added to the pattern database after a pattern associated with the age, wherein the pattern associated with the age is not eligible for deletion during the grace period.

16. The computing device of claim 11, wherein the quality metric comprises a function of a ratio of the constant sequence length and a total length of a pattern.

17. The computing device of claim 11, wherein the plurality of objects are not pre-defined.