# US 10,872,394 B2 · Frequent pattern mining method and apparatus

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,872,394 B2
- Document ID: US10872394B2
- Status: Granted
- Kind: B2
- Application number: 15/955,879
- Filed: 2018-04-18
- Published: 2018-11-01
- Granted: 2020-12-22
- Earliest claimed: 2017-04-27
- Assignees: Daegu Gyeongbuk Institute of Science and Technology
- Applicants: Daegu Gyeongbuk Institute of Science and Technology
- Inventors: Min Soo Kim; Kangwook Chon
- Web page: https://patentgrep.com/patent/US10872394B2

## CPC

- G06T 1/60: Memory management
- G01R 31/31921: {using compression techniques, e.g. patterns sequencer}
- G06F 16/20: of structured data, e.g. relational data
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/23: Updating
- G06F 16/2465: {Query processing support for facilitating data mining operations in structured databases}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06F 2216/03: Data mining
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G01R: MEASURING ELECTRIC VARIABLES; MEASURING MAGNETIC VARIABLES (indicating correct tuning of resonant circuits H03J3/12)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 1)

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.

### Claim 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.

### Claim 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:
generating relative memory addresses of the candidate k-itemsets using a dictionary that maps an 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 at least one of the fragment blocks to the device memories as inner operand,
calculating, by the GPUs, partial supports corresponding to the relative memory addresses using the copied fragment block and the relative memory addresses,
updating the supports of the candidate k-itemsets by synchronizing the partial supports,
copying at least one second fragment 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 fragment 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 fragment 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.

### Claim 10

A frequent pattern mining method, comprising:
mining frequent 1-itemsets from transaction data;
selecting a traversal from the first level (TFL) strategy or a hopping from intermediate level (HIL) strategy;
generating blocks from bit vectors corresponding to the frequent 1-itemsets based on the selected strategy, by vertically partitioning a transaction bitmap including the bit vectors, the transaction bitmap being represented by a vertical bitmap layout, when the TFL strategy is selected, 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 said 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 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 blocks to the device memories as inner operand,
calculating, by the GPUs, partial supports corresponding to the relative memory addresses using the copied block and the relative memory addresses,
updating the supports of the candidate k-itemsets by synchronizing the partial supports,
copying a second 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 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 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.

### Claim 11 (depends on 10)

The frequent pattern mining method of claim 10, wherein the generating comprises:
generating fragments by dividing the frequent 1-itemsets, when the HIL strategy is selected;
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.

### Claim 12 (depends on 11)

The frequent pattern mining method of claim 11, wherein the calculating of the supports comprises:
generating relative memory addresses of the candidate k-itemsets using a dictionary that maps an 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 at least one of the fragment blocks to the device memories as inner operand;
calculating, by the GPUs, partial supports corresponding to the relative memory addresses using the copied fragment block and the relative memory addresses; and
updating the supports of the candidate k-itemsets by synchronizing the partial supports.

### Claim 13

A frequent pattern mining apparatus, comprising:
a central processing unit (CPU); and
a main memory,
wherein the CPU is configured to:
generate 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,
copy relative memory addresses of candidate k-itemsets, from the main memory 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,
copy 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
update 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 CPU is configured to:
generate 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.