COMPUTER SYSTEM PROGRAMMED TO IDENTIFY COMMON SUBSEQUENCES IN LOGS

• US 20170091190A1
• Filed: 09/29/2015
• Published: 03/30/2017
• 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
• Granted Patent: US 10,664,481 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 associated with the first tokenized object, 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;

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;

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 length of a constant sequence within an associated pattern.

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

8. The method of claim 1, wherein the popularity metric comprises a hit count.

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

10. A method comprising:

using a computer, managing a size of a pattern database that stores a plurality of patterns 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;

identifying, based on the ranking and from the subset, a pattern for deletion;

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

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

11. The method of claim 10, wherein the size is between 25 and 1000 patterns.

12. The method of claim 10, 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.

13. The method of claim 10, wherein the quality metric comprises a function of a length of a constant sequence within an associated pattern.

14. The method of claim 10, wherein the popularity metric comprises a hit count.

15. 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 associated with the first tokenized object, and storing the first pattern in a pattern database that comprises a plurality of patterns, wherein the plurality of patterns comprises a set of hierarchical patterns;

using the computer, receiving an indication from an application that the set of hierarchical patterns matched an input, wherein a pattern from the set of hierarchical patterns with a largest hit count is selected as a hit;

increasing, in the pattern database, in response to the indication, a hit count associated with each pattern of the set of hierarchical patterns;

when deleting a pattern of the set of hierarchical patterns from the pattern database;

deleting a more specific pattern of the set of hierarchical patterns when the more specific pattern comprises a first hit count below a first threshold relative to a second hit count of a more general pattern of the set of hierarchical patterns and the second hit count is below a second threshold relative to a total sum of all hit counts in the pattern database;

deleting the more general pattern if the more specific pattern is not deleted;

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

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

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

18. The method of claim 15, wherein the first threshold is half of the second hit count.

19. The method of claim 15, wherein the second threshold is sixty percent of the total sum of all hit counts in the pattern database.

20. The method of claim 15, wherein the plurality of objects are not pre-defined.

21. A method comprising:

using a computer, receiving an indication from an application that the set of hierarchical patterns matched an input, wherein a pattern from the set of hierarchical patterns with a largest hit count is selected as a hit;

increasing, in the pattern database, in response to the indication, a hit count associated with each pattern of the set of hierarchical patterns;

when deleting a pattern of the set of hierarchical patterns from the pattern database;

deleting a more specific pattern of the set of hierarchical patterns when the more specific pattern comprises a first hit count below a first threshold relative to a second hit count of a more general pattern of the set of hierarchical patterns and the second hit count is below a second threshold relative to a total sum of all hit counts in the pattern database;

deleting the more general pattern if the more specific pattern is not deleted;

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

22. The method of claim 21, wherein the first threshold is half of the second hit count.

23. The method of claim 21, wherein the second threshold is sixty percent of the total sum of all hit counts in the pattern database.