Back

An Efficient Algorithm for Mining Association Rules in Large Databases

Ashoka SavasereEdward OmiecinskiShamkant B. Navathe

article1995VLDB2,006 citations
College of ComputingGeorgia Institute of Technologydatabase systemsefficient algorithmfrequent itemsetsmining association rulesApriori algorithmlarge itemsets
Savasere et al (1995).pdf
Cover for An Efficient Algorithm for Mining Association Rules in Large Databases

Abstract

Mining for association rules between items in a large database of sales transactions has been described as an important database mining problem. In this paper we present an efficient algorithm for mining association rules that is fundamentally different from known algorithms. Compared to previous algorithms, our algorithm not only reduces the I/O overhead significantly but also has lower CPU overhead for most cases. We have performed extensive experiments and compared the performance of our algorithm with one of the best existing algorithms. It was found that for large databases, the CPU overhead was reduced by as much as a factor of four and I/O was reduced by almost an order of magnitude. Hence this algorithm is especially suitable for very large size databases.

Topics

database systemsefficient algorithmfrequent itemsets

Keywords

mining association rulesApriori algorithmlarge itemsetscandidate itemsetsPartition algorithmknowledge discoveryminimum supporthashtree structuredatabase mining

Table of Contents

  • 1 Introduction
  • 2 Problem Description
  • 2.1 Previous Work
  • 3 Partition Algorithm
  • 3.1 Generation of Local Large Itemsets
  • 3.2 Generation of Final Large Itemsets
  • 3.3 Discovering Rules
  • 3.4 Size of the Global Candidate Set
  • 3.4.1 Effect of Data Skew
  • 3.5 Data Structures and Implementation
  • 3.5.1 Generating Local Large Itemsets
  • 3.5.2 Generating the Global Candidate Set
  • 3.5.3 Generating Final Counts
  • 3.6 Buffer Management
  • 3.7 Choosing the Number of Partitions
  • 4 Performance Comparison
  • 4.1 Synthetic Data
  • 4.2 Experiments
  • 4.2.1 Explanation of Performance
  • 4.2.2 Improvement in Disk I/O
  • 4.3 Scale-up Experiments
  • 5 Conclusions
  • Acknowledgment
  • References

Knowls

  1. Knowl 1 — Partition Algorithm for Mining Association Rules

    algorithm

    The Partition algorithm discovers all globally large (frequent) itemsets in a transaction database DD using at most two complete passes over the data. The database is logically divided into nn non-overlapping partitions P={p1,p2,…,pn}P = \{p_1, p_2, \dots, p_n\} such that each partition fits entirely within main memory.

    The algorithm executes in two distinct phases:

    1. Phase I (Local Generation and Merging): Each partition pip_i is loaded into main memory one at a time. All itemsets that meet the minimum support threshold minSup\text{minSup} within partition pip_i (the local large itemsets LpiL^{p_i}) are generated using in-memory tidlist joins. At the end of Phase I, the local large itemsets from all nn partitions are merged via union to form the global candidate set CG=⋃i=1nLpiC^G = \bigcup_{i=1}^n L^{p_i}.
    2. Phase II (Global Support Counting): Counters for all global candidate itemsets in CGC^G are initialized to zero. The database partitions are read a second time. For each partition, local support counts for all c∈CGc \in C^G are accumulated by intersecting tidlists of constituent 1-itemsets. Candidate itemsets whose total support meets or exceeds ∣D∣⋅minSup|D| \cdot \text{minSup} form the final set of global large itemsets LGL^G.
    Input: Transaction database DD, minimum support ratio minSup\text{minSup}, number of partitions nn
    Output: Set of all globally large itemsets LGL^G
    1. Partition DD into nn disjoint memory-sized partitions P={p1,p2,…,pn}P = \{p_1, p_2, \dots, p_n\}
    2. // Phase I: Local Large Itemset Generation
    3. for i=1i = 1 to nn do
    4. Read partition pip_i into main memory
    5. Lpi=gen_large_itemsets(pi,minSup)L^{p_i} = \text{gen\_large\_itemsets}(p_i, \text{minSup})
    6. end for
    7. // Merge Phase: Global Candidate Generation
    8. CG=∅C^G = \emptyset
    9. for k=1,2,…k = 1, 2, \dots while ∃j∈{1,…,n}\exists j \in \{1, \dots, n\} such that Lkpj≠∅L_k^{p_j} \ne \emptyset do
    10. CkG=⋃j=1nLkpjC_k^G = \bigcup_{j=1}^n L_k^{p_j}
    11. CG=CG∪CkGC^G = C^G \cup C_k^G
    12. end for
    13. // Phase II: Global Counting
    14. for each candidate itemset c∈CGc \in C^G do
    15. c.count=0c.\text{count} = 0
    16. end for
    17. for i=1i = 1 to nn do
    18. Read partition pip_i into main memory
    19. for all candidate itemsets c∈CGc \in C^G do
    20. c.count=c.count+count_in_partition(c,pi)c.\text{count} = c.\text{count} + \text{count\_in\_partition}(c, p_i)
    21. end for
    22. end for
    23. LG={c∈CG∣c.count≥∣D∣⋅minSup}L^G = \{c \in C^G \mid c.\text{count} \ge |D| \cdot \text{minSup}\}
    24. return LGL^G

  2. Knowl 2 — Necessary Condition for Global Frequent Itemsets Under Partitioning

    theoretical result

    Let a database DD consisting of ∣D∣|D| transactions be partitioned into nn pairwise disjoint subsets p1,p2,…,pnp_1, p_2, \dots, p_n such that D=⋃i=1npiD = \bigcup_{i=1}^n p_i and pi∩pj=∅p_i \cap p_j = \emptyset for all i≠ji \ne j. Let minSup∈(0,1]\text{minSup} \in (0, 1] denote a user-specified minimum support threshold.

    An itemset XX is defined to be globally large if its total support in DD satisfies: countD(X)≥∣D∣⋅minSup\text{count}_D(X) \ge |D| \cdot \text{minSup} and locally large in partition pip_i if: countpi(X)≥∣pi∣⋅minSup\text{count}_{p_i}(X) \ge |p_i| \cdot \text{minSup}

    Theorem: Any itemset XX that is globally large in DD must be locally large in at least one partition pi∈{p1,p2,…,pn}p_i \in \{p_1, p_2, \dots, p_n\}.

    Implication: The union of all locally large itemsets generated across all nn partitions, CG=⋃i=1nLpiC^G = \bigcup_{i=1}^n L^{p_i}, is guaranteed to contain all globally large itemsets (LG⊆CGL^G \subseteq C^G). Generating candidates via local partition mining introduces potential false positives but zero false negatives.

  3. Knowl 3 — In-Memory Local Large Itemset Generation via Tidlist Joining

    algorithm

    The procedure gen_large_itemsets computes all local large itemsets of all lengths within a single in-memory partition pp. It begins by scanning pp once to form sorted tidlists (lists of transaction IDs containing each item) for all 1-itemsets. For each length k≥2k \ge 2, candidate kk-itemsets are generated by joining pairs of large (k−1)(k-1)-itemsets sharing a common (k−2)(k-2)-length prefix. If all (k−1)(k-1)-subsets of a candidate are present in Lk−1pL_{k-1}^p, its support is immediately evaluated by intersecting the sorted tidlists of the two generator itemsets. If its support meets minSup\text{minSup}, it is added to LkpL_k^p.

    Input: In-memory partition pp, minimum support ratio minSup\text{minSup}
    Output: Set of all local large itemsets Lp=⋃kLkpL^p = \bigcup_k L_k^p
    1. L1p={all large 1-itemsets along with their sorted tidlists in p}L_1^p = \{ \text{all large 1-itemsets along with their sorted tidlists in } p \}
    2. for k=2k = 2 while Lk−1p≠∅L_{k-1}^p \ne \emptyset do
    3. Lkp=∅L_k^p = \emptyset
    4. for each itemset l1∈Lk−1pl_1 \in L_{k-1}^p do
    5. for each itemset l2∈Lk−1pl_2 \in L_{k-1}^p do
    6. if l1[1]=l2[1]∧⋯∧l1[k−2]=l2[k−2]∧l1[k−1]<l2[k−1]l_1[1] = l_2[1] \land \dots \land l_1[k-2] = l_2[k-2] \land l_1[k-1] < l_2[k-1] then
    7. c=l1[1]⋅l1[2]⋯l1[k−1]⋅l2[k−1]c = l_1[1] \cdot l_1[2] \cdots l_1[k-1] \cdot l_2[k-1]
    8. if for all (k−1)(k-1)-subsets ss of cc, s∈Lk−1ps \in L_{k-1}^p then
    9. c.tidlist=l1.tidlist∩l2.tidlistc.\text{tidlist} = l_1.\text{tidlist} \cap l_2.\text{tidlist}
    10. if ∣c.tidlist∣/∣p∣≥minSup|c.\text{tidlist}| / |p| \ge \text{minSup} then
    11. Lkp=Lkp∪{c}L_k^p = L_k^p \cup \{c\}
    12. end if
    13. end if
    14. end if
    15. end for
    16. end for
    17. end for
    18. return ⋃kLkp\bigcup_k L_k^p

  4. Knowl 4 — Tidlist Data Structure and Intersection Support Counting

    model/method

    For any itemset XX evaluated within a database partition pp, a tidlist is an ordered list of transaction identifiers (TIDs) corresponding to every transaction in pp that contains XX. The TIDs are stored in strictly ascending order.

    The support count of XX in partition pp is given directly by the cardinality of its tidlist: countp(X)=∣X.tidlist∣\text{count}_p(X) = |X.\text{tidlist}|

    For any candidate kk-itemset c=l1∪l2c = l_1 \cup l_2 formed by joining two (k−1)(k-1)-itemsets l1l_1 and l2l_2, the tidlist of cc is computed by intersecting the tidlists of l1l_1 and l2l_2: c.tidlist=l1.tidlist∩l2.tidlistc.\text{tidlist} = l_1.\text{tidlist} \cap l_2.\text{tidlist}

    Because both tidlists are maintained in sorted order, their intersection is computed using a two-pointer sort-merge join in O(∣l1.tidlist∣+∣l2.tidlist∣)O(|l_1.\text{tidlist}| + |l_2.\text{tidlist}|) operations without reading or testing transactions from the raw database. As itemset size kk increases, the lengths of the tidlists monotonically decrease, making support counting progressively cheaper in later iterations.

  5. Knowl 5 — Phase II Global Support Counting via 1-Itemset Tidlist Intersections

    algorithm

    In Phase II of the Partition algorithm, the global support counts for all candidate itemsets in CGC^G are accumulated across all partitions. For each partition pip_i, sorted tidlists are generated for all 1-itemsets. Candidate counts are evaluated in descending order of itemset length kk. Intersecting the 1-itemset tidlists gives the exact local TID match list for each candidate; prefix intersections are reused to simultaneously update counts for shorter sub-itemsets in CGC^G.

    Input: Partitions P={p1,…,pn}P = \{p_1, \dots, p_n\}, global candidate set CGC^G
    Output: Accumulated global support counts for all c∈CGc \in C^G
    1. for each candidate c∈CGc \in C^G do
    2. c.count=0c.\text{count} = 0
    3. end for
    4. for i=1i = 1 to nn do
    5. Read partition pip_i into main memory
    6. Generate sorted tidlists for all 1-itemsets in pip_i
    7. for k=max⁡c∈CG∣c∣k = \max_{c \in C^G}|c| down to 2 do
    8. for each candidate c={c[1],c[2],…,c[k]}∈CkGc = \{c[1], c[2], \dots, c[k]\} \in C_k^G do
    9. templist=c[1].tidlist∩c[2].tidlist∩⋯∩c[k].tidlist\text{templist} = c[1].\text{tidlist} \cap c[2].\text{tidlist} \cap \dots \cap c[k].\text{tidlist}
    10. c.count=c.count+∣templist∣c.\text{count} = c.\text{count} + |\text{templist}|
    11. // Intermediate intersections are reused to set local counts of sub-itemsets in CGC^G
    12. end for
    13. end for
    14. end for

  6. Knowl 6 — Global Candidate Set Pruning Criteria

    model/method

    During the merge phase between Phase I and Phase II, the global candidate set CGC^G is pruned to eliminate itemsets that do not require counting in Phase II:

    1. Complete Knowledge Pruning: If an itemset cc is reported as locally large in all nn partitions, its exact global support is already known from the sum of its local counts: countD(c)=∑i=1ncountpi(c)\text{count}_D(c) = \sum_{i=1}^n \text{count}_{p_i}(c) Since countpi(c)≥∣pi∣⋅minSup\text{count}_{p_i}(c) \ge |p_i| \cdot \text{minSup} for all ii, countD(c)≥∣D∣⋅minSup\text{count}_D(c) \ge |D| \cdot \text{minSup}. The itemset cc is immediately declared globally large (c∈LGc \in L^G) and omitted from Phase II verification.

    2. Upper-Bound Pruning: For an itemset cc that is locally large only in a subset of partitions Plarge⊂PP_{\text{large}} \subset P, its maximum possible count in any partition pj∉Plargep_j \notin P_{\text{large}} is bounded by ∣pj∣⋅minSup−1|p_j| \cdot \text{minSup} - 1. The maximum possible global count is: max_count(c)=∑p∈Plargecountp(c)+∑p∉Plarge(∣p∣⋅minSup−1)\text{max\_count}(c) = \sum_{p \in P_{\text{large}}} \text{count}_p(c) + \sum_{p \notin P_{\text{large}}} (|p| \cdot \text{minSup} - 1) If max_count(c)<∣D∣⋅minSup\text{max\_count}(c) < |D| \cdot \text{minSup}, cc cannot possibly be globally large and is pruned from CGC^G before Phase II.

  7. Knowl 7 — Extent-Level Random Allocation for Skew-Resistant Database Partitioning

    model/method

    Data skew (such as temporal clustering of specific purchasing patterns or non-uniform transaction lengths across a database file) causes individual partitions to generate large numbers of spurious locally large itemsets that lack global support, inflating CGC^G.

    To eliminate data skew while preserving disk I/O performance:

    1. The database is divided into disk extents, where an extent is the minimum unit for sequential I/O operations.
    2. Extents are randomly assigned to the nn logical partitions such that each extent belongs to exactly one partition.

    This randomization breaks spatial and temporal data clustering across partitions, ensuring uniform support distributions across all pip_i, while allowing reading within each extent to proceed at sequential I/O speeds.

  8. Knowl 8 — CPU and Disk I/O Performance of Partition vs. Apriori

    empirical result

    Experimental evaluations on synthetic retail transaction datasets (∣D∣=100K|D| = 100\text{K} transactions, N=1,000N = 1,000 items, ∣L∣=2,000|L| = 2,000 maximal potentially large itemsets, transaction sizes ∣T∣∈[5,20]|T| \in [5, 20], maximal itemset sizes ∣I∣∈[2,6]|I| \in [2, 6]) executed on a Silicon Graphics Indy R4400SC workstation (150 MHz, 32 MB RAM, 4 KB disk pages) demonstrate:

    1. I/O Reduction: Partition reads the database at most twice regardless of minimum support or itemset lengths. For dataset T20.I6.100K at 0.25%0.25\% minimum support, Partition reduced disk read requests by 87%87\% compared to Apriori (an 8×8\times reduction from ∼36,000\sim 36,000 to ∼4,500\sim 4,500 4 KB page reads). Across all benchmark datasets at 0.25%0.25\% support, the minimum I/O reduction was 60%60\% (2.5×2.5\times fewer reads).
    2. CPU Overhead: At lower minimum support levels where candidate itemsets are numerous, Partition's tidlist intersection approach outperforms Apriori's hashtree subset comparisons. For T20.I6.100K at 0.25%0.25\% support, execution time dropped from 707 seconds (Apriori) to 97 seconds (Partition-1), an 81%81\% reduction (5×5\times speedup).
    3. High-Support Overhead: At high minimum support settings where very few large itemsets exist, Apriori slightly outperforms Partition because Partition incurs the overhead of allocating and populating tidlists without reaping sufficient join speedups.

  9. Knowl 9 — Scalability of the Partition Algorithm Across Database and Transaction Sizes

    empirical result

    Scalability experiments on the Partition algorithm show:

    1. Database Size Scale-up: Scaling database size from 100,000 to 10,000,000 transactions on dataset T10.I4 (with partitions scaled proportionally from n=1n=1 for 100K to n=100n=100 for 10M) showed an initial execution time increase per transaction when moving from 1 to 4 partitions due to local candidate proliferation. Beyond 400,000 transactions up to 10,000,000 transactions, normalized execution time per transaction remained linear because commonality among local large itemsets across partitions stabilized the size of CGC^G.
    2. Transaction Size Scale-up: Average transaction length ∣T∣|T| was varied from 5 to 50 with ∣I∣|I| from 2 to 6 (holding total physical data volume constant by decreasing transaction counts from 200,000 to 20,000). For high-cost configurations (support threshold of 250 transactions), Partition scaled better than Apriori as transaction size increased because tidlist intersection costs increase slower than Apriori's subset testing operations.

  10. Knowl 10 — Impact of Partition Count and Extent Randomization on Candidate Set Sizes

    data/table

    Experimental measurements on dataset T10.I4.100K (∣D∣=100,000|D| = 100,000 transactions, minSup=0.75%\text{minSup} = 0.75\%) show that while increasing the number of partitions increases the total number of local candidates, the union CGC^G grows at a much slower rate due to substantial overlap among locally large itemsets:

    Number of Partitions Size of Largest LpL^p Average Size of LpL^p Size of CGC^G
    2 91 89.0 93
    4 100 82.5 108
    7 131 97.0 144
    10 149 109.1 170
    20 273 211.9 381
    30 463 344.1 673

    Under synthetic data skew (41 MB database, ∼600,000\sim 600,000 transactions with average length varied from 5 to 20, minSup=0.75%\text{minSup} = 0.75\%), random extent allocation effectively eliminates false candidates generated by localized skew:

    Number of Partitions Reading Sequential Blocks Reading Random Blocks
    Sum of all LpL^p Size of CGC^G Sum of all LpL^p Size of CGC^G
    5 3,961 3,831 69 26
    10 9,281 6,166 150 39
    15 15,800 7,618 304 75
    20 22,871 8,228 439 87
    25 29,245 8,961 599 101
    30 36,311 9,598 760 121

    Sequential block allocation leads to huge candidate set inflation under skew (up to 9,598 candidates for 30 partitions), whereas random block allocation keeps CGC^G bounded to 121.

Coverage note — Rule generation from large itemsets given minimum confidence thresholds was omitted as it is standard and unchanged from prior work (Agrawal et al., 1994).

References

  1. 1.R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pages 207–216, Washington, DC, May 26–28 1993.
  2. 2.R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In Proceedings of the 20th International Conference on Very Large Data Bases, Santiago, Chile, August 29–September 1 1994.
  3. 3.T. M. Anwar, S. B. Navathe, and H. W. Beck. Knowledge mining in databases: A unified approach through conceptual clustering. Technical report, Georgia Institute of Technology, May 1992.
  4. 4.J. Han, Y. Cai, and N. Cercone. Knowledge discovery in databases: an attribute-oriented approach. In Proceedings of the 18th International Conference on Very Large Data Bases, pages 547–559, Vancouver, Canada, 23–27, August 1992.
  5. 5.M. Holsheimer and A. Siebes. Data mining: The search for knowledge in databases. Technical Report CS-R9406, CWI, Amsterdam, The Netherlands, 1993.
  6. 6.M. Houtsma and A. Swami. Set-oriented mining of association rules. In Proceedings of the International Conference on Data Engineering, Taipei, Taiwan, March 1995.
  7. 7.R. Krishnamurthy and T. Imielinski. Practitioner problems in need of database research. ACM SIGMOD Record, 20(3):76–78, September 1991.
  8. 8.G. Piatetsky-Shapiro and W. J. Frawley, editors. Knowledge Discovery in Databases. MIT Press, 1991.
  9. 9.A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. Technical Report GIT-CC-95-04, Georgia Institute of Technology, Atlanta, GA 30332, January 1995.
  10. 10.A. Silberschatz, M. Stonebraker, and J. Ullman. Database systems: achievements and opportunities. Communications of the ACM, 34(10):110–120, October 1991.
  11. 11.M. Stonebraker, R. Agrawal, U. Dayal, E. Nuehold, and A. Reuter. Database research at a crossroads: The Vienna update. In Proceedings of the 19th International Conference on Very Large Data Bases, pages 688–192, Dublin, Ireland, August 1993.
  12. 12.S. Tsur. Data dedging. IEEE Data Engineering Bulletin, 13(4):58–63, December 1990.
  13. 13.J. T-L. Wang, G-W. Chirn, T. G. Marr, B. Shapiro, D. Shasha, and K. Zhang. Cobinatorial pattern discovery for scientific data: some preliminary results. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, pages 115–125, Minneapolis, MN, May 24–27 1994.

Citation

MLA
Savasere, A., et al. “An Efficient Algorithm for Mining Association Rules in Large Databases”. SMARTech Repository (Georgia Institute of Technology), 1995, pp. 432–44, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5437.
APA
Savasere, A., Omiecinski, E., & Navathe, S. B. (1995). An Efficient Algorithm for Mining Association Rules in Large Databases. SMARTech Repository (Georgia Institute of Technology), 432–444. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5437
Chicago
Savasere, A., E. Omiecinski, and S. B. Navathe. 1995. “An Efficient Algorithm for Mining Association Rules in Large Databases”. SMARTech Repository (Georgia Institute of Technology), 432–44. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5437.
Harvard
Savasere, A., Omiecinski, E. and Navathe, S.B. (1995) “An Efficient Algorithm for Mining Association Rules in Large Databases”, SMARTech Repository (Georgia Institute of Technology), pp. 432–444. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5437.
Vancouver
1. Savasere A, Omiecinski E, Navathe SB (1995) An Efficient Algorithm for Mining Association Rules in Large Databases. SMARTech Repository (Georgia Institute of Technology) 432–444

BibTeX

@article{savasere1995efficient,
  title = {An Efficient Algorithm for Mining Association Rules in Large Databases},
  author = {Savasere, Ashoka and Omiecinski, Edward and Navathe, Shamkant B.},
  year = {1995},
  journal = {SMARTech Repository (Georgia Institute of Technology)},
  pages = {432-444},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.103.5437}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF