US 10,474,690 B2 · Disjunctive rule mining with finite automaton hardware

Abstract

The present invention introduces the development of a flexible CPU-AP (Computer Processing Unit-Automata Processor) computing infrastructure for mining hierarchical patterns based on Apriori algorithm. A novel automaton design strategy, called linear design, is described to generate automata for matching and counting hierarchical patterns and apply it on SPM (Sequential Pattern Mining). In addition, another novel automaton design strategy, called reduction design, is described for the disjunctive rule matching (DRM) and counting. The present invention shows performance improvement of AP SPM and DRM solutions and broader capability over multicore and GPU (Graphics Processing Unit) implementations of GSP SPM, and shows that AP SPM and DRM solutions outperform state-of-the-art SPM algorithms SPADE and PrefixSpan (especially for larger datasets).

Claims14

Dependent claims

A processor for mining a plurality of patterns in large datasets, the processor comprises a plurality of functional element comprising:

a plurality of state transition elements;
a plurality of counters;
and
a plurality of Boolean elements,
wherein the processor is configured to implement non-deterministic finite automata (NFA) with a reduction design method,
wherein the reduction design method is used for disjunctive rule mining (DRM) with an Apriori-based algorithm, and
wherein the disjunctive rule mining comprises the steps of:
generating candidates;
and
matching and counting d-rules,
wherein in the DRM, a d-rule is defined as a set of disjunctive items (d-items), yi={ds1, ds2, . . . , dsl}.

8 more elements

A method for mining a plurality of patterns in large datasets by a processor, the method comprising the steps of:

implementing non-deterministic finite automata (NFA) with a reduction design method on the processor, the processor comprising:
a plurality of state transition elements;
a plurality of counters;
and
a plurality of Boolean elements,
wherein the reduction design method is used for disjunctive rule mining (DRM) with an Apriori-based algorithm, and
wherein the disjunctive rule mining comprises the steps of:
generating candidates;
and
matching and counting d-rules,
wherein in the DRM, a d-rule is defined as a set of disjunctive items (d-items), yi={ds1, ds2, . . . , dsl}.

8 more elements

Dependencies are inferred from the claim text.

Disjunctive rule mining with finite automaton hardware

Life of this patent

Disjunctive rule mining with finite automaton hardware

Life of this patent

Abstract

Claims14