INPUT DATA STRUCTURE FOR DATA MINING

• US 20070220030A1
• Filed: 02/06/2007
• Published: 09/20/2007
• Est. Priority Date: 03/14/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dorneich, Ansgar, Lingenfelder, Christoph, Bollinger, Toni
• Granted Patent: US 8,250,105 B2
• 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
• CPC Class Codes: G06F 2216/03 Data mining

Abstract

Methods and apparatus, including computer program products, implementing and using techniques for compressing data included in several transactions. Each transaction has at least one item. A unique identifier is assigned to each different item and, if taxonomy is defined, to each different taxonomy parent. Sets of transactions are formed from the several transactions. The sets of transactions are stored using a computer data structure including: a list of identifiers of different items in the set of transactions, information indicating number of identifiers in the list, and bit field information indicating presence of the different items in the set of transactions, said bit field information being organized in accordance with the list for facilitating evaluation of patterns with respect to the set of transactions. A data structure for compressing data included in a set of transactions is also provided.

Claims

1. A computer data structure for compressing data comprised in a set of transactions, each transaction having at least one item, the computer data structure comprising:

a list of identifiers of different items in the set of transactions,

information indicating number of identifiers in the list, and

bit field information indicating presence of the different items in the set of transactions, said bit field information being organized in accordance with the list for facilitating evaluation of patterns with respect to the set of transactions.

2. The computer data structure of claim 1, wherein said list of identifiers further comprises identifiers of different taxonomy parents of the different items, and said bit field information indicates presence of the different items and of the different taxonomy parents in the set of transactions.

3. The computer data structure of claim 1, wherein said bit field information further comprises one bit for each item-transaction pair, the size of the bit field being the number of identifiers times number of transactions in the set.

4. The computer data structure of claim 1, wherein the set contains a predetermined number of transactions, said predetermined number being dependent on hardware.

5. The computer data structure of claim 1, wherein the set of transactions belongs to a transaction group and each transaction has ordering information, said data structure further comprising:

information indicating number of transactions in the transaction group, and

information about the ordering information of the different transactions.

6. The computer data structure of claim 5, wherein said information about the ordering information indicates differences between transactions.

7. The computer data structure of claim 5, further comprising information indicating the total number of items in the set of transactions.

8. The computer data structure of claim 1, further comprising at least one of the following:

weight statistics for said different items, and accumulated weight statistics for said set of transactions.

9. A computer-implemented method for compressing data included in a plurality of transactions, each transaction having at least one item, said method comprising:

assigning a unique identifier to each different item and, if taxonomy is defined, to each different taxonomy parent,

forming sets of transactions from the plurality of transactions, and

storing said sets of transactions using a computer data structure including;

a list of identifiers of different items in the set of transactions,

information indicating number of identifiers in the list, and

bit field information indicating presence of the different items in the set of transactions, said bit field information being organized in accordance with the list for facilitating evaluation of patterns with respect to the set of transactions.

10. The method of claim 9, further comprising:

determining item frequencies and, if taxonomy is defined, taxonomy parent frequencies before assigning said unique identifiers, and

discarding items having item frequency and, if present, taxonomy parent frequency less than a predefined frequency, thereby producing remaining items and remaining transactions,

wherein said unique identifiers are assigned to each different remaining item and to each different remaining possible taxonomy parent.

11. The method of claim 9, further comprising ordering items and identifiers in said data structures in accordance with said identifiers.

12. The method of claim 9, wherein each set of transactions contains a predetermined number of transactions, said predetermined number being dependent on hardware.

13. The method of claim 12, further comprising discarding transactions having less remaining items than a predefined number before forming said sets of transactions.

14. The method of claim 12, further comprising ordering said remaining transactions based on similarity thereof before said step of forming sets.

15. The method of claim 9, wherein each set of transactions represents a transaction group, identified by each transaction within the group carrying a same transaction group identifier, each transaction having ordering information and said computer data structures further comprising information indicating number of transactions in the transaction group, and information about the ordering information of the different transactions.

16. The method of claim 15, further comprising discarding sets of transaction having less remaining items than a predefined number of items or less transactions than a predefined number of transactions.

17. A computer-implemented method for detecting patterns in input data containing a plurality of transactions, each transaction having at least one item and items possibly having taxonomy parents, the method comprising:

providing input data in computer data structures having

a list of identifiers of different items in the set of transactions,

information indicating number of identifiers in the list, and

bit field information indicating presence of the different items in the set of transactions, said bit field information being organized in accordance with the list for facilitating evaluation of patterns with respect to the set of transactions; and

evaluating a candidate pattern using bit map operations on the bit field information of the computer data structures.

18. The method of claim 17, wherein said step of providing input data contains at least one of the following:

reading said data structures from a storage medium; and

processing input data to form said data structures.

19. The method of claim 17, further comprising taking into account evaluation information of a parent candidate pattern of said candidate pattern when evaluating said candidate pattern.

20. The method of claim 19, wherein said evaluation information of said parent candidate pattern is taken into account by evaluating said candidate pattern only with respect to transactions supporting said parent candidate pattern.

21. The method of claims 17, further comprising determining whether items defined by positive item constraints are present in transactions in connection with evaluating the candidate pattern.

22. The method of claim 17, further comprising evaluating a set of similar candidate patterns, said set containing at least two candidate patterns, together with respect to the computer data structures.

23. The method of claim 22, further comprising determining presence of common items of the set of similar candidate patterns in said computer data structures, and determining presence of non-common items of the set of similar candidate patterns in transactions of said computer data structures having said common items.

24. The method of claim 17, further comprising determining whether items occur in a same order in the candidate pattern and in transactions of said computer data structures.

25. A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

assign a unique identifier to each different item and, if taxonomy is defined, to each different taxonomy parent,

form sets of transactions from the plurality of transactions, and

store said sets of transactions using a computer data structure including;

a list of identifiers of different items in the set of transactions,

information indicating number of identifiers in the list, and

bit field information indicating presence of the different items in the set of transactions, said bit field information being organized in accordance with the list for facilitating evaluation of patterns with respect to the set of transactions.

26. The computer program product of claim 25, further causing the computer to:

determine item frequencies and, if taxonomy is defined, taxonomy parent frequencies before assigning said unique identifiers, and

discard items having item frequency and, if present, taxonomy parent frequency less than a predefined frequency, thereby producing remaining items and remaining transactions,

wherein said unique identifiers are assigned to each different remaining item and to each different remaining possible taxonomy parent.

27. The computer program product of claim 25, further causing the computer to order items and identifiers in said data structures in accordance with said identifiers.

28. The computer program product of claim 25, wherein each set of transactions contains a predetermined number of transactions, said predetermined number being dependent on hardware.

29. The computer program product of claim 25, wherein each set of transactions represents a transaction group, identified by each transaction within the group carrying a same transaction group identifier, each transaction having ordering information and said computer data structures further comprising information indicating number of transactions in the transaction group, and information about the ordering information of the different transactions.

30. A computer program product comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

provide input data in computer data structures having

a list of identifiers of different items in the set of transactions,

information indicating number of identifiers in the list, and

bit field information indicating presence of the different items in the set of transactions, said bit field information being organized in accordance with the list for facilitating evaluation of patterns with respect to the set of transactions; and

evaluate a candidate pattern using bit map operations on the bit field information of the computer data structures.

31. The computer program product of claim 30, wherein the instructions to provide input data contains instructions to do at least one of the following:

read said data structures from a storage medium; and

process input data to form said data structures.

32. The computer program product of claim 30, further causing the computer to take into account evaluation information of a parent candidate pattern of said candidate pattern when evaluating said candidate pattern.

33. The computer program product of claim 30, further causing the computer to determine whether items defined by positive item constraints are present in transactions in connection with evaluating the candidate pattern.

34. The computer program product of claim 30, further causing the computer to evaluate a set of similar candidate patterns, said set containing at least two candidate patterns, together with respect to the computer data structures.

35. The computer program product of claim 30, further causing the computer to determine whether items occur in a same order in the candidate pattern and in transactions of said computer data structures.