ASSOCIATION RULE MINING WITH THE MICRON AUTOMATA PROCESSOR

• US 20170091287A1
• Filed: 09/30/2015
• Published: 03/30/2017
• Est. Priority Date: 09/30/2015
• Status: Active Grant

• Current Assignee: University of Virginia Patent Foundation (University of Virginia)
• Original Assignee: University of Virginia Patent Foundation (University of Virginia)
• Inventors: Wang, Ke, Skadron, Kevin
• Granted Patent: US 10,445,323 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24569 Query processing with adaptation to specific hardware, e.g. adapted for using GPUs or SSDs
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

The present invention discloses a heterogeneous computation framework, of Association. Rule Mining (ARM) using Micron'"'"'s Autotmata Processor (AP). This framework is based on the Apriori algorithm. Two Automaton designs are proposed to match and count the individual itemset. Several performance improvement strategies are proposed including minimizing the number of reporting vectors and reduce reconfiguration delays. The experiment results show up to 94× speed ups of the proposed AP-accelerated Apriori on six synthetic and real-world datasets, when compared with the Apriori single-core CPU implementation. The proposed AP-accelerated Apriori solution also outperforms the state-of-the-art multicore and GPU implementations of Equivalence Class Transformation (Eclat) algorithm on big datasets.

Claims

1. A processor for discovering a pattern of frequently associated items in large datasets, the processor comprises functional elements comprising:

a plurality of state transition elements based on memory columns implemented in DRAM (Dynamic Random-Access Memory) memory technology;

a plurality of counters; and

a plurality of boolean elements,

wherein the processor is capable of fast replacement of symbol sets of the plurality of state transition elements and threshold values of the plurality of counters,

wherein the plurality of counters and the plurality of boolean elements are designed to work with the plurality of state transition elements to increase space efficiency of automata implementation, and

wherein the pattern includes sets, continuous sequences, and discontinuous sequences in the large datasets.

2. The processor according to claim 1, wherein the processor is implemented in PCRAM (Phase-Change Random-Access Memory), STTRAM (Spin-Transfer Torque Random-Access Memory), or RRAM (Resistive Random-Access Memory).

3. The processor according to claim 1, wherein each of the plurality of state transition elements is configured to match a set of any multiple-bit signals.

4. The processor according to claim 1, wherein a group of the plurality of state transition elements is connected to implement a non-deterministic finite automaton (NFA) to match the pattern in the large datasets.

5. The processor according to claim 1, wherein the plurality of counters are configured to connect to a finite automaton to count occurrences of the pattern in the datasets and make reports or activate the functional elements when a predetermined threshold is reached.

6. The processor according to claim 5, wherein the finite automaton is accommodated on a chip and is capable of matching and counting a plurality of patterns in parallel.

7. The processor according to claim 1, wherein the processor takes input streams of multiple-bit signals and is capable of processing a plurality of data streams concurrently.

8. The processor according to claim I, wherein any of the functional elements are configured as a reporting element, wherein the reporting element generates a one-bit or multiple-bit signals when the functional elements match with input streams of multiple-bit signals.

9. An automaton design method of discovering a pattern of frequently associated items in large datasets by a processor, the method comprising steps of:

applying Apriori algorithm framework for reducing a search space in the datasets;

preprocessing an input data set for making it compatible with a working interface of the processor; and

designing automata for implementing matching and counting of the pattern in the datasets,

wherein the pattern includes sets, continuous sequences, and discontinuous sequences in the large datasets.

10. The automaton design method according to claim 9, wherein the matching is implemented by a finite automaton.

11. The automaton design method according to claim 9, wherein the matching is capable of capturing the patterns in the datasets.

12. The automaton design method according to claim 10, wherein the pattern is represented by a linearly connected array of states of automata with one or more states of automata grouped together to match one multiple-bit signal from input streams of multiple-bit signals.

13. The automaton design method according to claim 11, wherein one or more self-activating states of automata connect to one group of states of automata for multiple-bit signals to hold a position within a potential pattern sequence when a mismatching of multiple-bit signals is seen, and hold this position until an end of an transaction, in order to deal with the discontinuous sequences.

14. The automaton design method according to claim 9, wherein the sets are converted to the to discontinuous sequences by sorting items of each transaction with a predefined order.

15. The automaton design method according to claim 9, wherein on-chip Boolean logic components are utilized to discover occurrence of every item of a given associated item set and to identify a superset of the given set.

16. The automaton design method according to claim 15, wherein one or more self-activating states of automata connect to one group of states of automata for multiple-bit signals to hold a position within a potential pattern sequence when a mismatching of multiple-bit signals is seen, and hold this position until an end of an transaction, in order to deal with the discontinuous sequences.

17. The automaton design method according to claim 9, wherein the counting uses an on-chip counter of the processor to calculate a frequency of the pattern associated items in the datasets.

18. The automaton design method according to claim 9, wherein the method further comprises steps of minimizing an output from the processor by delaying reporting of events to a final processing cycle.

19. The automaton design method according to claim 9, wherein the preprocessing of the input data set in the datasets further comprises steps of:

filtering out infrequent items from the input data set;

encoding the filtered items into multiple-bit signals; and

sorting the encoded items within one transaction with a given order.

20. The automaton design method according to claim 19, the preprocessing of the input data set is iterated to explore all sets of the frequently associated items in the large datasets.

21. An electronic automaton device for discovering a pattern of frequently associated items in large datasets comprising:

a finite automaton; and

a counter element,

wherein the electronic automaton device recognizes the pattern and creates a signal when occurrence of the pattern exceeds a given threshold, and

wherein the pattern includes sets, continuous sequences, and discontinuous sequences in the large datasets.

22. The electronic automaton device according to claim 21, wherein the pattern is represented by a linearly connecting array of states of automata with one or more states of automata grouped together to match one multiple-bit signal from input streams of multiple-bit signals,

23. The electronic automaton device according to claim 22, wherein one or more self-activating states of automata connected to one group of states of automata for multiple-bit signals to hold a position within a potential pattern sequence when a mismatching of multiple-bit signals is seen, and hold this position until an end of an transaction, in order to deal with the discontinuous sequences.

24. The electronic automaton device according to claim 21, wherein the sets are converted to the discontinuous sequences by sorting items of each transaction with a predefined order.

25. The electronic automaton device according to claim 21, wherein on-chip Boolean logic components are utilized to discover occurrence of every item of a given associated item set and to identify a superset of the given set.

26. The electronic automaton device according to claim 21, wherein one or more self-activating states of automata connect to one group of states of automata for multiple-bit signals to hold a position within a potential pattern sequence when a mismatching of multiple-bit signals is seen, and hold this position until an end of an transaction, in order to deal with the discontinuous sequences.

27. The electronic automaton device according to claim 21, wherein the counter element is connected to a pattern matching automaton to calculate a frequency of the pattern in the datasets.