System and method for mining of temporal data

• US 20060195444A1
• Filed: 02/28/2005
• Published: 08/31/2006
• Est. Priority Date: 02/28/2005
• Status: Active Grant

• Current Assignee: GM Global Technology Operations LLC (General Motors Company)
• Original Assignee: GM Global Technology Operations Incorporated (Motors Liquidation Co. GUC Trust)
• Inventors: Laxman, Srivatsan, Sastry, P. S., Unnikrishnan, K. P.
• Granted Patent: US 7,644,078 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data

Abstract

A method, system, and apparatus for temporal data mining is disclosed. The method includes receiving as input a temporal data series comprising events with start times and end times, a set of allowed dwelling times, and a threshold frequency. The method also includes finding all frequent principal episodes of a particular length in the temporal data series having dwelling times within the allowed dwelling times. The method includes steps executed in successive passes through the temporal data series. The steps include incrementing the particular length to generate an increased length, combining frequent principal episodes to create combined episodes of the increased length, creating a set of candidate episodes from the combined episodes by removing combined episodes which have non-frequent sub-episodes, identifying one or more occurrences of a candidate episode in the temporal data series, incrementing a count for each identified occurrence, determining frequent principal episodes of the increased length, and setting the particular length to the increased length.

Claims

1. A method for temporal data mining, comprising:

receiving as input a temporal data series comprising events with start times and end times, a set of allowed dwelling times, and a threshold frequency;

finding all frequent principal episodes of a particular length in the temporal data series having dwelling times, as determined by the start and end times, within the allowed dwelling times;

in successive passes through the temporal data series;

incrementing the particular length to generate an increased length;

combining frequent principal episodes to create combined episodes of the increased length;

creating a set of candidate episodes from the combined episodes by removing combined episodes which have non-frequent sub-episodes;

identifying one or more occurrences of a candidate episode in the temporal data series;

incrementing a count for each identified occurrence;

determining frequent principal episodes of the increased length; and

setting the particular length to the increased length; and

producing an output for frequent principal episodes;

wherein a frequent principal episode is a principal episode whose count of occurrences results in a frequency meeting or exceeding the threshold frequency.

2. The method of claim 1, wherein the identifying comprises identifying whether a non-overlapping occurrence of a candidate episode occurs in the temporal data series.

3. The method of claim 1, wherein the identifying comprises identifying whether a non-interleaved occurrence of a candidate episode occurs in the temporal data series.

4. The method of claim 1, further comprising

generating a plurality of automata adapted to track whether an occurrence of a candidate episode occurs in the temporal data series;

wherein the identifying comprises tracking, with the plurality of automata, whether an occurrence of a candidate episode occurs in the temporal data series.

5. The method of claim 4, wherein the plurality of automata are adapted to track a non-overlapping occurrence of a candidate episode.

6. The method of claim 4, wherein the plurality of automata are adapted to track a non-interleaved occurrence of a candidate episode.

7. The method of claim 1, further comprising:

receiving as input an expiry time;

wherein the expiry time provides a criterion for occurrence of an episode.

8. A system for temporal data mining, comprising:

an input module for receiving a temporal data series comprising events with start times and end times, a set of allowed dwelling times, and a threshold frequency;

a candidate identification and tracking module for identifying one or more occurrences in the temporal data series of a candidate episode having dwelling times, as determined by the start and end times, within the allowed dwelling times, and for incrementing a count for each identified occurrence; and

an output module for producing an output for those episodes which are principal and whose count of occurrences results in a frequency exceeding the threshold frequency.

9. The system of claim 8, wherein the candidate identification and tracking module identifies whether a non-overlapping occurrence of a candidate episode occurs in the temporal data series.

10. The system of claim 8, wherein the candidate identification and tracking module identifies whether a non-interleaved occurrence of a candidate episode occurs in the temporal data series.

11. The system of claim 8, further comprising

an automata generation module for generating a plurality of automata adapted to track whether an occurrence of a candidate episode occurs in the temporal data series;

wherein the identifying comprises identifying, with the plurality of automata, whether an occurrence of a candidate episode occurs in the temporal data series.

12. The system of claim 11, wherein the plurality of automata are adapted to track a non-overlapping occurrence of a candidate episode.

13. The system of claim 11, wherein the plurality of automata are adapted to track a non-interleaved occurrence of a candidate episode.

14. The system of claim 8, wherein the input module receives an expiry time for providing a criterion for occurrence of an episode.

15. An apparatus for temporal data mining, comprising:

a processor for executing instructions;

a memory device including instructions comprising;

input instructions for receiving a temporal data series comprising events with start times and end times, a set of allowed dwelling times, and a threshold frequency;

candidate identification and tracking instructions for identifying one or more occurrences in the temporal data series of a candidate episode having dwelling times, as determined by the start and end times, within the allowed dwelling times, and for incrementing a count for each identified occurrence; and

output instructions for producing an output for those episodes which are principal and whose count of occurrences results in a frequency exceeding the threshold frequency.

16. The apparatus of claim 15, wherein the candidate identification and tracking instructions comprise instructions for identifying whether a non-overlapping occurrence of a candidate episode occurs in the temporal data series.

17. The apparatus of claim 15, wherein the candidate identification and tracking instructions comprise instructions for identifying whether a non-interleaved occurrence of a candidate episode occurs in the temporal data series.

18. The apparatus of claim 15, further comprising

instructions for generating a plurality of automata adapted to track whether an occurrence of a candidate episode occurs in the temporal data series;

wherein the identifying comprises identifying, with the plurality of automata, whether an occurrence of a candidate episode occurs in the temporal data series.

19. The apparatus of claim 18, wherein the plurality of automata are adapted to track a non-overlapping occurrence of a candidate episode.

20. The apparatus of claim 18, wherein the plurality of automata are adapted to track a non-interleaved occurrence of a candidate episode.