Method for Extracting Maximal Repeat Patterns and Computing Frequency Distribution Tables
OwnerChing-Tu Wanginventor
Life of this patent
Estimating the term…
Abstract
Pattern discovery in sequential data mining is valuable for many applications, such as genomic signature (biomarker) identification, trend analysis, sequential logs analysis, user action (behavior) analysis and production line analysis. An approach can extract maximal repeat patterns from tagged sequences based on MapReduce programming model, and meanwhile compute the frequency distribution of these patterns according to the tags. Most of all, the components of sequences may be characters, words or records while the types of tags may be timestamps or classes given by users.
Claims10
A method for extracting maximal repeat patterns and computing frequency distribution tables, executed in a computing system across multiple nodes of a cluster of machines, wherein the maximal repeat patterns are extracted from sequences attached with tags, and the frequency distribution tables of candidate patterns are computed according to classes or categories derived from the tags, the method comprising the following steps:
- splitting the sequences into fixed-size partitions;
- assigning each of the partitions to a map task that is run on a worker node;
- generating suffixes of the sequences in the same partition by each of the map tasks, wherein each of the suffixes is attached with one tag belonging to a corresponding sequence;
- partitioning the suffixes into groups, wherein each of the groups contains the suffixes whose first k components are the same;
- sorting the suffixes within one group;
- assigning each of the groups to a reduce task that is run on a worker node;
- allowing each of the reducers to scan the sorted suffixes in the same group and to extract a longest common prefix of two successive suffixes as one candidate maximal repeat pattern for each of the reduce tasks;
- and
- computing a frequency distribution of the candidate maximal repeat pattern according to classes or categories derived from the tags.
Dependencies are inferred from the claim text.