Method and an apparatus to improve processor utilization in data mining

• US 20060149766A1
• Filed: 12/30/2004
• Published: 07/06/2006
• Est. Priority Date: 12/30/2004
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Ghoting, Amol, Chen, Yen-Kuang, Kim, Daehyun, Nguyen, Anthony D.
• Application Number:
  US11/026,775
• Publication Number:
  US 20060149766A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

A method and an apparatus to improve processor utilization in data mining have been disclosed. In one embodiment, the method includes representing a transaction data set with a prefix tree, and allocating the prefix tree in a depth first search order in a memory of the computing system during data mining of the transaction data set. Other embodiments have been claimed and described.

Claims

1. A method comprising:

representing a transaction data set with a prefix tree; and

allocating the prefix tree in a depth first search order in a memory of a computing system during data mining of the transaction data set.

2. The method of claim 1, further comprising:

performing frequent itemset mining on the transaction data set during the data mining of the transaction data set.

3. The method of claim 2, wherein performing frequent itemset mining comprises:

performing a depth first search traversal of the prefix tree to find one or more maximal frequent itemsets.

4. The method of claim 3, further comprising:

fetching a cache line of data containing at least a portion of the prefix tree from the memory in response to a first request to access a first portion of the transaction data set during the data mining;

temporarily storing the cache line of data in a cache in the computing system; and

receiving a second request to access a second portion of the transaction data set subsequent to the first request, wherein the cache line of data stored in the cache includes the second portion of the transaction data set.

5. The method of claim 3, wherein performing the depth first search traversal of the prefix tree comprises:

determining a support count of an itemset in the second prefix tree;

remembering a point in the prefix tree at which the determining of the support count of the itemset terminates; and

continuing to search for a next itemset at the point remembered without going back to a root node of the prefix tree.

6. The method of claim 3, further comprises:

co-scheduling a plurality of tasks of the frequent itemset mining on a multithreaded processor, wherein the plurality of tasks share at least a portion of the data in the cache.

7. A method comprising:

co-scheduling a plurality of tasks in data mining of a transaction data set on a multithreaded processor, wherein the plurality of tasks share at least a portion of data in a cache of the multithreaded processor; and

fetching a cache line of data from a memory coupled to the multithreaded processor, the cache line of data containing at least a portion of the transaction data set.

8. The method of claim 7, further comprising:

representing the transaction data set with a cache-conscious prefix tree; and

storing the transaction data set in the memory based on the cache-conscious prefix tree.

9. The method of claim 8, wherein representing the transaction data set with the cache-conscious prefix tree comprises:

generating a first prefix tree to represent the transaction data set; and

allocating the cache-conscious prefix tree in a depth first search order of the first prefix tree in the memory.

10. A machine-accessible medium that provides instructions that, if executed by a processor, will cause the processor to perform operations comprising:

representing a transaction data set with a prefix tree; and

allocating the prefix tree in a depth first search order in a memory of a computing system during data mining of the transaction data set.

11. The machine-accessible medium of claim 10, wherein the operations further comprise:

performing frequent itemset mining on the transaction data set during the data mining of the transaction data set.

12. The machine-accessible medium of claim 11, wherein performing frequent itemset mining comprises:

performing a depth first search traversal of the prefix tree to find one or more maximal frequent itemsets.

13. The machine-accessible medium of claim 12, wherein performing the depth first search traversal of the prefix tree comprises:

determining a support count of an itemset in the prefix tree;

remembering a point in the prefix tree at which the determining of the support count of the itemset terminates; and

continuing to search for a next itemset at the point remembered without going back to a root node of the prefix tree.

14. The machine-accessible medium of claim 11, wherein the operations further comprise:

co-scheduling a plurality of tasks of the frequent itemset mining on a multithreaded processor, wherein the plurality of tasks share at least a portion of the data in the cache.

15. A machine-accessible medium that provides instructions that, if executed by a processor, will cause the processor to perform operations comprising:

co-scheduling a plurality of tasks in data mining of a transaction data set on a multithreaded processor, wherein the plurality of tasks share at least a portion of data in a cache of the multithreaded processor; and

fetching a cache line of data from a memory coupled to the multithreaded processor, the cache line of data containing at least a portion of the transaction data set.

16. The machine-accessible medium of claim 15, wherein the operations further comprise:

representing the transaction data set with a cache-conscious prefix tree; and

storing the transaction data set in the memory based on the cache-conscious prefix tree.

17. The machine-accessible medium of claim 16, wherein representing the transaction data set with the cache-conscious prefix tree comprises:

generating a first prefix tree to represent the transaction data set; and

allocating the first prefix tree in a depth first search order of the non-cache-conscious prefix tree in the memory.

18. A system comprising:

a processor;

a network interface coupled to the processor; and

a memory coupled to the processor to store a plurality of instructions that, if executed by the processor, will cause the processor to perform operations comprising;

representing a transaction data set with a prefix tree; and

allocating the prefix tree in a depth first search order in the memory during data mining of the transaction data set.

19. The system of claim 18, wherein the processor comprises a cache, wherein the operations further comprise:

fetching a cache line of data containing at least a portion of the prefix tree from the memory in response to a first request to access a first portion of the transaction data set during the data mining; and

temporarily storing the cache line of data in the cache; and

receiving a second request to access a second portion of the transaction data set subsequent to the first request, wherein the cache line of data stored in the cache includes the second portion of the transaction data set.

20. The system of claim 19, wherein the operations further comprise:

performing frequent itemset mining on the transaction data set during the data mining of the transaction data set.

21. The system of claim 20, wherein performing frequent itemset mining comprises:

performing a depth first search traversal of the second prefix tree to find one or more maximal frequent itemsets.

22. The system of claim 21, wherein performing the depth first search traversal of the prefix tree comprises:

determining a support count of an itemset in the prefix tree;

remembering a point in the prefix tree at which the determining of the support count of the itemset terminates; and

continuing to search for a next itemset at the point remembered without going back to a root node of the prefix tree.

23. The system of claim 21, wherein the processor comprises a multithreaded processor, wherein the operations further comprise:

co-scheduling a plurality of tasks of the frequent itemset mining on the multithreaded processor, wherein the plurality of tasks share at least a portion of the data in the cache.

24. A system comprising:

a multithreaded processor comprising a cache;

a network interface coupled to the multithreaded processor; and

a memory coupled to the multithreaded processor to store a plurality of instructions that, if executed by the processor, will cause the processor to perform operations comprising;

co-scheduling a plurality of tasks in data mining of a transaction data set on the multithreaded processor, wherein the plurality of tasks share at least a portion of data in the cache; and

fetching a cache line of data from the memory, the cache line of data containing at least a portion of the transaction data set.

25. The system of claim 24, wherein the operations further comprise:

representing the transaction data set with a cache-conscious prefix tree; and

storing the transaction data set in the memory based on the cache-conscious prefix tree.

26. The system of claim 25, representing the transaction data set with the cache-conscious prefix tree comprises:

generating a first prefix tree to represent the transaction data set; and

allocating the cache-conscious prefix tree in a depth first search order of the first prefix tree in the memory.

27. An apparatus comprising:

a memory; and

a processing circuitry coupled to the memory, the processing circuitry operable to allocate a prefix tree in a depth first search order in the memory to represent a transaction data set during data mining of the transaction data set.

28. The apparatus of claim 27, wherein the processing circuitry is operable to perform frequent itemset mining on the transaction data set during the data mining of the transaction data set.

29. The apparatus of claim 28, wherein the processing circuitry is operable to perform a depth first search traversal of the prefix tree to find one or more maximal frequent itemsets.

30. The apparatus of claim 29, wherein the processing circuitry is operable to determine a support count of an itemset in the prefix tree, remember a point in the prefix tree at which determining of the support count of the itemset terminates, and to continue to search for a next itemset at the point remembered without going back to a root node of the prefix tree.