Frequent pattern mining method and apparatus

Patent metadata

Field	Value
Publication number	US-10872394-B2
Application number	US-201815955879-A
Country	US
Kind code	B2
Filing date	Apr 18, 2018
Priority date	Apr 27, 2017
Publication date	Dec 22, 2020
Grant date	Dec 22, 2020

Abstract

Disclosed is a frequent pattern mining method and apparatus, the frequent pattern mining apparatus that may copy relative memory addresses of candidate itemsets, from a main memory to device memories of graphic processing units (GPUs), copy at least one same block required for calculating supports of the candidate itemsets, from the main memory to the device memories, and update the supports of the candidate itemsets by synchronizing partial supports processed by the GPUs.

First claim

What is claimed is:

1. A frequent pattern mining method, comprising:
generating blocks from bit vectors corresponding to frequent 1-itemsets, by vertically partitioning a transaction bitmap including the bit vectors, the transaction bitmap being represented by a vertical bitmap layout, wherein each bit vector describes an occurrence of a different 1-itemset of a plurality of 1-itemsets in a plurality of data transactions being mined for frequent patterns, wherein each bit of a certain bit vector indicates an occurrence of a respective 1-itemset in a specific one of said plurality of data transactions and wherein each of said generated blocks comprises a different portion, of a pre-defined size, of each of the bit vectors;
copying relative memory addresses of candidate k-itemsets, from a main memory of a central processing unit (CPU) to device memories of graphic processing units (GPUs), by:
generating the relative memory addresses of the candidate k-itemsets using a dictionary that maps a frequent 1-itemset of the transaction bitmap to a relative memory address; and
copying the generated relative memory addresses to the device memories as outer operand;

copying at least one same block required for calculating supports of the candidate k-itemsets among the blocks, from the main memory to the device memories, by copying one of the blocks to the device memories as inner operand; and
updating the supports of the candidate k-itemsets by calculating, by the GPUs, partial supports corresponding to the relative memory addresses using the copied block and the relative memory addresses; and synchronizing the partial supports corresponding to the relative memory addresses calculated by the GPUs;
wherein the generating blocks from bit vectors comprises:
generating the blocks from bit vectors based on the size of the device memories of the GPU;
wherein said 1-itemset is defined as a set containing a single item;
wherein said k-itemset is defined as a set containing a plurality of items in a count of k; and
wherein said support is defined as a number of occurrences.

2. The frequent pattern mining method of claim 1 , wherein the copying of the relative memory addresses comprises:
copying a relative memory address of a first candidate k-itemset to a device memory of a first GPU; and
copying a relative memory address of a second candidate k-itemset to a device memory of a second GPU,
wherein the copying of the at least one same block comprises:
copying a first block of the blocks to the device memory of the first GPU; and
copying the first block to the device memory of the second GPU.

3. The frequent pattern mining method of claim 1 , wherein the generating of the relative memory addresses comprises:
identifying frequent 1-itemsets included in a candidate k-itemset; and
generating a relative memory address of the candidate k-itemset by combining relative memory addresses of the identified frequent 1-itemsets.

4. The frequent pattern mining method of claim 1 , further comprising:
generating fragments by dividing the frequent 1-itemsets;
generating itemsets being all combinations of frequent 1-itemsets in each of the fragments;
calculating bit vectors corresponding to the generated itemsets; and
generating fragment blocks by vertically partitioning a transaction bitmap including the calculated bit vectors and dividing the transaction bitmap for each of the fragments, the transaction bitmap being represented by a vertical bitmap layout,
wherein the blocks are the fragment blocks.

5. The frequent pattern mining method of claim 4 , wherein the copying of the relative memory addresses comprises:
generating the relative memory addresses of the candidate k-itemsets using a dictionary that maps an itemset of the transaction bitmap to a relative memory address; and
copying the generated relative memory addresses to the device memories as outer operand.

6. The frequent pattern mining method of claim 5 , wherein the generating of the relative memory addresses comprises:
identifying itemsets included in a candidate k-itemset; and
generating a relative memory address of the candidate k-itemset by combining relative memory addresses of the identified itemsets.

7. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to perform the frequent pattern mining method of claim 1 .

8. A frequent pattern mining method, comprising:
mining frequent 1-itemsets from transaction data;
generating transaction blocks by vertically partitioning a transaction bitmap including bit vectors corresponding to the frequent 1-itemsets, the transaction bitmap being represented by a vertical bitmap layout, wherein each bit vector describes an occurrence of a different 1-itemset of a plurality of 1-itemsets in a plurality of data transactions of the transaction data being mined for frequent patterns, wherein each bit of a certain bit vector indicates an occurrence of a respective 1-itemset in a specific one of said plurality of data transactions and wherein each of said generated blocks comprises a different portion, of a pre-defined size, of each of the bit vectors;
calculating supports of candidate k-itemsets from the transaction blocks using graphic processing units (GPUs), by:
generating relative memory addresses of the candidate k-itemsets using a dictionary that maps a frequent 1-itemset of the transaction bitmap to a relative memory address,
copying the relative memory addresses to device memories of the GPUs as outer operand,
copying one of the transaction blocks to the device memories as inner operand,
calculating, by the GPUs, partial supports corresponding to the relative memory addresses using the copied transaction block and the relative memory addresses,
updating the supports of the candidate k-itemsets by synchronizing the partial supports,
copying a second transaction block to the device memories as inner operand,
calculating, by the GPUs, second partial supports corresponding to the relative memory addresses using the copied second transaction block and the relative memory addresses and
updating the supports of the candidate k-itemsets by synchronizing the second partial supports; and

mining frequent k-itemsets based on the supports;
wherein the generating transaction blocks comprises:
generating the transaction blocks by vertically partitioning the transaction bitmap based on the size of the device memories of the GPU;
wherein said 1-itemset is defined as a set containing a single item;
wherein said k-itemset is defined as a set containing a plurality of items in a count of k; and
wherein said support is defined as a number of occurrences.

9. A frequent pattern mining method, comprising:
mining frequent 1-itemsets from transaction data;
generating fragments by dividing the frequent 1-itemsets;
generating itemsets being all combinations of frequent 1-itemsets in each of the fragments;
calculating bit vectors corresponding to the generated itemsets, wherein each bit vector describes an occurrence of a different itemset of the generated itemsets in a plurality of data transactions of the transaction data being mined for frequent patterns, wherein each bit of a certain bit vector indicates an occurrence of a respective itemset in a specific one of said plurality of data transactions;
generating fragment blocks by vertically partitioning a transaction bitmap including the calculated bit vectors and dividing the transaction bitmap for each of the fragments, the transaction bitmap being represented by a vertical bitmap layout;
calculating supports of candidate k-itemsets from the fragment blocks using graphic processing units (GPUs), by:
gen

Assignees

• Daegu Gyeongbuk Inst Science & Tech

Inventors

• Kim Min Soo
• Chon Kangwook

Classifications

• G06F16/2465

  Query processing support for facilitating data mining operations in structured databases · CPC title

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06F16/2237

  Vectors, bitmaps or matrices · CPC title

• G06F2216/03

  Data mining · CPC title

• G06T1/60 Primary

  Memory management · CPC title