Determination of rules by providing data records in columnar data structures

• US 8,671,111 B2
• Filed: 05/07/2012
• Issued: 03/11/2014
• Est. Priority Date: 05/31/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dantressangle, Patrick, Hechler, Eberhard, Oberhofer, Martin, Wurst, Michael
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US13/465,210
• Publication Number:
  US 20120310874A1
• Time in Patent Office: 673 Days
• Field of Search: 707/776, 707802-804, 707/806, 709/201, 709/203, 709/213, 709/217
• US Class Current: 707/776
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures

Abstract

A method includes providing a columnar database comprising a plurality of columnar data structures associated with one column attribute; providing first data records having a plurality of first attribute-value pairs comprising counting information indicative of a number of first data records having the respective first attribute-value pair; providing mask data structures comprising one or more second attribute-value pairs; selecting second data records by intersecting the columnar data structures and the mask data structures; selecting one of the column attributes and one value contained in the column data structure associated with said selected column attribute as the destination attribute-value pair; creating one second rule for each first attribute-value pair; calculating, for each second rule, a co-occurrence-count between its respective source attribute-value pair and its destination attribute-value pair; and specifically selecting one or more of said second rules as the first rules in dependence on the calculated co-occurrence-count.

Claims

1. A computer-implemented method for determining first rules, wherein each first rule comprises a source attribute-value pair and a destination attribute-value pair, the method comprising:

providing a columnar database, the columnar database comprising a plurality of columnar data structures, each columnar data structure being associated with one column attribute and comprising one or more column entries;

providing first data records, the first data records being stored in the columnar database, each first data record having a plurality of first attribute-value pairs, wherein each value of said first attribute-value pairs is stored in one of the columnar data structures associated with the respective column attribute, wherein each column entry is associated with one value of the respective column attribute and comprises counting information, the counting information being indicative of a number of first data records having the respective first attribute-value pair;

providing mask data structures, each mask data structure having the same structure as one of the columnar data structures, the mask data structures comprising one or more second attribute-value pairs;

selecting second data records as a sub-set of the first data records by intersecting the columnar data structures and the mask data structures, the second data records selectively comprising first data records which comprise at least one first attribute-value pair matching one of the one or more second attribute-value pairs;

selecting one of the column attributes and one value being contained in the column data structure associated with said selected column attribute as the destination attribute-value pair;

creating one second rule for each first attribute-value pair of the second data records, wherein said first attribute-value pair is used as source attribute-value of said second rule and wherein the selected destination attribute-value pair is used as the destination attribute-value pair of said second rule;

calculating, for each second rule, a co-occurrence-count between its respective source attribute-value pair and its destination attribute-value pair; and

specifically selecting one or more of said second rules as the first rules in dependence on the calculated co-occurrence-count.

2. The computer-implemented method of claim 1, wherein specifically selecting one or more of said second rules comprises:

sorting the second rules according to their co-occurrence-count in descending order and selecting the first n sorted second rules as n first rules, wherein n is an integer greater than 0;

determining n second rules having a co-occurrence-count that exceeds a first threshold and selecting said n second rules as first rules, wherein n is an integer greater than 0; and

calculating for each second rule a co-occurrence statistic providing for each of said second rules a significance score and selecting n of said second rules having a significance score that exceeds a second threshold, wherein n is an integer greater than 0.

3. The computer-implemented method of claim 2, wherein the co-occurrence statistic is based on a chi-square test.

4. The computer-implemented method of claim 1, wherein selecting the destination attribute-value pair is implemented by displaying a graphical user interface (GUI) to a user, the GUI comprising one or more first GUI elements for selecting one column attribute from the column attributes by the user, the GUI comprising one or more second GUI elements for selecting one value from the columnar data structure having assigned said selected column attribute, wherein the selected column attribute and the selected value constitute the destination attribute-value pair.

5. The computer-implemented method of claim 4, wherein the first and second GUI elements are automatically determined by analyzing the structure and data content of the columnar data structures.

6. The computer-implemented method of claim 1, wherein the column entries of the columnar data structures and column entries of the mask data structures are selected from a group consisting of:

bit sets, bit vectors, sorted lists, and sorted arrays.

7. The computer-implemented method of claim 1, wherein the mask data structures are provided by:

providing an online analytical process (OLAP) cube for executing a data analysis of all first data records, each dimension and/or hierarchical level of the OLAP cube having assigned one or more third attribute-value pairs;

in dependence on a slicing, dicing, pivoting, drill-down or roll-up event performed on said OLAP cube, selecting a current dimension and/or a current hierarchical level of the OLAP cube; and

automatically generating the mask data structures, wherein the mask data structures comprise the third attribute-value pairs of the current dimension and/or of the current hierarchical level as the second attribute-value pairs.

8. The computer-implemented method of claim 7, wherein the GUI comprises at least one or more GUI elements being selected from the group comprising:

third GUI elements for triggering the slicing, dicing, pivoting, drill-down or roll-up event on the OLAP cube; and

fourth GUI elements for selecting and/or specifying the one or more third attribute-value pairs.

9. The computer-implemented method of anyone of claim 7, wherein the first rules are presented to a user on the GUI in descending order depending on their co-occurrence-score and wherein upon selection of one or more of said presented first rules the source attribute-value pairs of the selected first rules are assigned as the third attribute-value pairs to the OLAP cube.

10. The computer-implemented method of claim 1, wherein the first rules are presented to a user on the graphical user interface in descending order depending on their co-occurrence-score.

11. The computer-implemented method of claim 1, wherein the provided mask data structures further comprise k sub-set-bagging mask data structures, k being an integer larger than 1;

wherein the selection of the second data records is performed by intersecting each of the k sub-set-bagging mask data structures with the columnar data structures and with any of the mask data structures not being a sub-set-bagging mask data structure, thereby returning k sub-sets of second data records;

wherein the creation of the second rules comprises the creation of k sub-sets of second rules, wherein the creation of each sub-set of second rules is implemented by creating second rules for the first attribute-value pairs of all second data records being contained in said sub-set of second data records;

wherein specifically selecting one or more of the second rules as first rules further comprises, for each of the k sub-sets of second rules, specifically selecting one or more of its second rules as first rules in dependence on the calculated co-occurrence-count, thereby creating k sub-sets of first rules, and compiling, from all k sub-sets of first rules, a unique list of first rules, the unique list of first rules solely comprising first rules which are contained in at least t of said sub-sets of first rules, wherein 0<

=t<

=k.

12. The computer-implemented method of claim 11, wherein the selection of k sub-sets of second data records is executed concurrently and wherein the calculation of the co-occurrence-counts of the second rules is executed for each of the k sub-sets of second rules in parallel.

13. The computer-implemented method of claim 1, wherein the columnar data structures and the mask data structures are completely loaded into a working memory.

14. A computer program product for determining first rules, wherein each first rule comprises a source attribute-value pair and a destination attribute-value pair, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code being configured for;

providing a columnar database, the columnar database comprising a plurality of columnar data structures, each columnar data structure being associated with one column attribute and comprising one or more column entries;

providing first data records, the first data records being stored in the columnar database, each first data record having a plurality of first attribute-value pairs, wherein each value of said first attribute-value pairs is stored in one of the columnar data structures associated with the respective column attribute, wherein each column entry is associated with one value of the respective column attribute and comprises counting information, the counting information being indicative of a number of first data records having the respective first attribute-value pair;

providing mask data structures, each mask data structure having the same structure as one of the columnar data structures, the mask data structures comprising one or more second attribute-value pairs;

selecting second data records as a sub-set of the first data records by intersecting the columnar data structures and the mask data structures, the second data records selectively comprising first data records which comprise at least one first attribute-value pair matching one of the one or more second attribute-value pairs;

selecting one of the column attributes and one value being contained in the column data structure associated with said selected column attribute as the destination attribute-value pair;

creating one second rule for each first attribute-value pair of the second data records, wherein said first attribute-value pair is used as source attribute-value of said second rule and wherein the selected destination attribute-value pair is used as the destination attribute-value pair of said second rule;

calculating;

for each second rule, a co-occurrence-count between its respective source attribute-value pair and its destination attribute-value pair; and

specifically selecting one or more of said second rules as the first rules in dependence on the calculated co-occurrence-count.

15. The computer program product according to claim 14, wherein specifically selecting one or more of said second rules comprises:

sorting the second rules according to their co-occurrence-count in descending order and selecting the first n sorted second rules as n first rules, wherein n is an integer greater than 0;

determining n second rules having a co-occurrence-count that exceeds a first threshold and selecting said n second rules as first rules, wherein n is an integer greater than 0; and

calculating for each second rule a co-occurrence statistic providing for each of said second rules a significance score and selecting n of said second rules having a significance score that exceeds a second threshold, wherein n is an integer greater than 0.

16. The computer program product according to claim 15, wherein the co-occurrence statistic is based on a chi-square test.

17. The computer program product according to claim 14, wherein selecting the destination attribute-value pair is implemented by displaying a graphical user interface to a user, the graphical user interface comprising one or more first GUI elements for selecting one column attribute from the column attributes by the user, the graphical user interface comprising one or more second GUI elements for selecting one value from the columnar data structure having assigned said selected column attribute, wherein the selected column attribute and the selected value constitute the destination attribute-value pair.

18. The computer program product according to claim 17, wherein the first and second GUI elements are automatically determined by analyzing the structure and data content of the columnar data structures.

19. The computer program product according to claim 14, wherein the column entries of the columnar data structures and column entries of the mask data structures are selected from a group consisting of:

bit sets, bit vectors, sorted lists, and sorted arrays.

20. A data processing system being operatively coupled to a columnar database, the data processing system comprising a processor, the system configured to perform a method comprising:

providing a columnar database, the columnar database comprising a plurality of columnar data structures, each columnar data structure being associated with one column attribute and comprising one or more column entries;

providing first data records, the first data records being stored in the columnar database, each first data record having a plurality of first attribute-value pairs, wherein each value of said first attribute-value pairs is stored in one of the columnar data structures associated with the respective column attribute, wherein each column entry is associated with one value of the respective column attribute and comprises counting information, the counting information being indicative of a number of first data records having the respective first attribute-value pair;

providing mask data structures, each mask data structure having the same structure as one of the columnar data structures, the mask data structures comprising one or more second attribute-value pairs;

selecting second data records as a sub-set of the first data records by intersecting the columnar data structures and the mask data structures, the second data records selectively comprising first data records which comprise at least one first attribute-value pair matching one of the one or more second attribute-value pairs;

selecting one of the column attributes and one value being contained in the column data structure associated with said selected column attribute as the destination attribute-value pair;

creating one second rule for each first attribute-value pair of the second data records, wherein said first attribute-value pair is used as source attribute-value of said second rule and wherein the selected destination attribute-value pair is used as the destination attribute-value pair of said second rule;

calculating, for each second rule, a co-occurrence-count between its respective source attribute-value pair and its destination attribute-value pair; and

specifically selecting one or more of said second rules as the first rules in dependence on the calculated co-occurrence-count.