Back

An effective hash-based algorithm for mining association rules

Jong Soo ParkMing-Syan ChenPhilip S. Yu

article1995SIGMOD1,748 citations

Introduces the Direct Hashing and Pruning (DHP) algorithm, which substantially speeds up association rule mining by using a hash technique to prune candidate 2-itemsets and progressively reduce transaction database sizes during early iterations.

Listen

Modern retail and catalog businesses continuously capture massive volumes of point-of-sale data that contain critical insights into customer purchasing habits. Discovering association rules—such as identifying which products customers routinely buy together—enables strategic decisions regarding product placement, promotional discounting, and catalog design. However, discovering frequent item combinations in massive transaction databases is computationally demanding, as previous techniques suffer from severe processing bottlenecks during initial iterations where the number of evaluated candidate combinations is excessively large.

The main objective of the article is to design and evaluate Direct Hashing and Pruning (DHP), a high-performance algorithm that accelerates the discovery of frequent itemsets in large databases. The article evaluates DHP’s ability to filter out non-viable candidate itemsets during early passes and progressively reduce the transaction database size across successive iterations.

The authors conducted extensive simulation experiments comparing DHP against the leading baseline algorithm, Apriori. The experimental framework evaluated synthetic retail transaction datasets scaling up to 100,000 transactions and up to 10,000 distinct items, testing varying transaction lengths and minimum support thresholds to assess runtime, candidate set sizes, and database reduction rates.

The key findings demonstrate significant performance advantages. First, DHP reduces the number of candidate two-item combinations by orders of magnitude compared to previous approaches by using a direct hash table and bit vector to filter out unlikely candidates before support counting. Second, DHP drastically shrinks the dataset size for later iterations, trimming the transaction database down to approximately 10% of its original file size and 20% of its original transaction count by pass three. Third, overall execution time is cut dramatically; for instance, on standard benchmarks DHP completed processing in 13.91 seconds compared to 39.39 seconds for Apriori—a reduction of nearly 65%. Finally, DHP scales linearly with total database volume and maintains robust performance across varied support thresholds and expanding item catalog sizes.

These findings imply substantial operational efficiency gains and cost reductions for organizations running large-scale analytics. Because the first two iterations traditionally account for roughly 65% of total execution time in baseline approaches, DHP resolves the primary computational bottleneck. The slightly increased memory and processing cost incurred during the initial pass to build the hash table is heavily outweighed by the massive reduction in candidate comparisons and database scanning time in subsequent passes.

Organizations evaluating data mining architectures should adopt direct hashing and progressive pruning strategies to enhance throughput on frequent itemset workloads. When configuring DHP, engineering teams should allocate sufficiently large hash tables—ideally sized between one-quarter of and equal to the total possible pair combinations—to maximize candidate pruning while managing available memory. For later stages where remaining candidate counts become very small, the algorithm should transition away from hashing to standard generation procedures to avoid unnecessary overhead.

The reported results are based on synthetic retail transaction models running on a single workstation environment, representing a potential limitation for unstructured or non-retail transactional workloads. Nevertheless, given the consistent linear scale-up behavior and robust sensitivity analysis across varied transaction configurations, decision-makers can have high confidence in DHP's capability to deliver substantial computational speedups.

IBMSungshin Women's Universitycomputational efficiencyfrequent itemsetshash functionsmining association ruleshash-based algorithmApriori algorithm
Park et al (1995).pdf
Cover for An effective hash-based algorithm for mining association rules

Abstract

In this paper, we examine the issue of mining association rules among items in a large database of sales transactions. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items which appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first and then, identifying, within this candidate set, those itemsets that meet the large itemset requirement. Generally this is done iteratively for each large k-itemset in increasing order of k where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate large itemsets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we propose an effective hash-based algorithm for the candidate set generation. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. Extensive simulation study is conducted to evaluate performance of the proposed algorithm.

Topics

computational efficiencyfrequent itemsetshash functionssalestransaction databaseextensive simulationsfrequent patterns

Keywords

mining association ruleshash-based algorithmApriori algorithmcandidate itemsetslarge itemset generationalgorithm DHPhash filteringAprioriTid algorithmtransaction database

Table of Contents

  • 1 Introduction
  • 2 Problem Description
  • 3 Direct Hashing with Efficient Pruning for Fast Data Mining
  • 3.1 Algorithm DHP
  • 3.2 Reducing the Size of Transaction Database
  • 4 Experimental Results
  • 4.1 Generation of Synthetic Data
  • 4.2 Effect of the Size of a Hash Table
  • 4.3 Comparison of DHP and Apriori
  • 4.4 Scale-Up Experiment for DHP
  • 5 Conclusions
  • References

Knowls

  1. Knowl 1 — Direct Hashing and Pruning Algorithm for Large Itemset Mining

    algorithm

    The Direct Hashing and Pruning (DHP) algorithm mines large itemsets from a transaction database DD given a minimum support count threshold ss and a bucket threshold LARGE\text{LARGE}. DHP proceeds in three distinct operational parts:

    1. Part 1 (Pass 1): Scans the original database D1=DD_1 = D, accumulates the occurrence counts of individual items (1-itemsets) using a hash tree to form the set of large 1-itemsets L1={c∣c.count≥s}L_1 = \{c \mid c.\text{count} \ge s\}, and simultaneously hashes all 2-subsets of each transaction into a hash table H2H_2.
    2. Part 2 (Iterative Hashing and Trimming): Executes for k≥2k \ge 2 as long as the number of frequent buckets in HkH_k satisfies ∣{x∣Hk[x]≥s}∣≥LARGE|\{x \mid H_k[x] \ge s\}| \ge \text{LARGE}. It generates candidate kk-itemsets CkC_k from Lk−1∗Lk−1L_{k-1} * L_{k-1} filtered by the condition Hk[hk(c)]≥sH_k[h_k(c)] \ge s, counts candidate support against the reduced database DkD_k, determines large itemsets LkL_k, builds the next hash table Hk+1H_{k+1} by hashing (k+1)(k+1)-subsets of transactions, and trims transactions and drops empty ones to produce the reduced database Dk+1D_{k+1}.
    3. Part 3 (Late-Stage Iterations): When the number of frequent buckets drops below LARGE\text{LARGE}, hash table creation is discontinued. DHP generates candidate sets Ck+1C_{k+1} via standard candidate join and subset validation (Lk∗LkL_k * L_k) without hash filtering, but continues counting support against the pruned database Dk+1D_{k+1}.
    Input: Transaction database DD, minimum support count threshold ss, threshold LARGE\text{LARGE}
    Output: Large itemsets L1,L2,…,LmL_1, L_2, \dots, L_m
    /* Part 1 */
    Set all buckets of hash table H2H_2 to 0
    for each transaction t∈Dt \in D do
        Insert and count 1-item occurrences of tt in a hash tree
        for each 2-subset x⊆tx \subseteq t do
            H2[h2(x)]←H2[h2(x)]+1H_2[h_2(x)] \leftarrow H_2[h_2(x)] + 1
    L1←{c∣c.count≥s in leaf node of hash tree}L_1 \leftarrow \{c \mid c.\text{count} \ge s \text{ in leaf node of hash tree}\}
    /* Part 2 */
    k←2k \leftarrow 2
    Dk←DD_k \leftarrow D
    while ∣{x∣Hk[x]≥s}∣≥LARGE|\{x \mid H_k[x] \ge s\}| \ge \text{LARGE} do
        Ck←gen_candidate(Lk−1,Hk)C_k \leftarrow \text{gen\_candidate}(L_{k-1}, H_k)
        Set all buckets of Hk+1H_{k+1} to 0
        Dk+1←∅D_{k+1} \leftarrow \emptyset
        for each transaction t∈Dkt \in D_k do
            t′←count_support(t,Ck,k)t' \leftarrow \text{count\_support}(t, C_k, k)
            if ∣t′∣>k|t'| > k then
                t′′←make_hasht(t′,Hk,k,Hk+1)t'' \leftarrow \text{make\_hasht}(t', H_k, k, H_{k+1})
                if ∣t′′∣>k|t''| > k then
                    Dk+1←Dk+1∪{t′′}D_{k+1} \leftarrow D_{k+1} \cup \{t''\}
        Lk←{c∈Ck∣c.count≥s}L_k \leftarrow \{c \in C_k \mid c.\text{count} \ge s\}
        k←k+1k \leftarrow k + 1
    /* Part 3 */
    Ck←gen_candidate(Lk−1,Hk)C_k \leftarrow \text{gen\_candidate}(L_{k-1}, H_k)
    while ∣Ck∣>0|C_k| > 0 do
        Dk+1←∅D_{k+1} \leftarrow \emptyset
        for each transaction t∈Dkt \in D_k do
            t′←count_support(t,Ck,k)t' \leftarrow \text{count\_support}(t, C_k, k)
            if ∣t′∣>k|t'| > k then
                Dk+1←Dk+1∪{t′}D_{k+1} \leftarrow D_{k+1} \cup \{t'\}
        Lk←{c∈Ck∣c.count≥s}L_k \leftarrow \{c \in C_k \mid c.\text{count} \ge s\}
        if ∣Dk+1∣=0|D_{k+1}| = 0 then
            break
        Ck+1←apriori_gen(Lk)C_{k+1} \leftarrow \text{apriori\_gen}(L_k)
        k←k+1k \leftarrow k + 1

  2. Knowl 2 — Direct Hashing Technique for Candidate Itemset Filtering

    model/method

    The direct hashing method filters out unpromising candidate itemsets before their support is counted against the database, specifically targeting the computational bottleneck of generating candidate 2-itemsets C2C_2.

    During pass kk, as transactions tt in the database are scanned to count the occurrences of candidate kk-itemsets, DHP collects advance frequency information for (k+1)(k+1)-itemsets. For every (k+1)(k+1)-subset xx of tt that survives trimming, a hash function hk+1(x)h_{k+1}(x) maps xx into bucket hk+1(x)h_{k+1}(x) of hash table Hk+1H_{k+1}, incrementing its bucket counter by 1.

    In pass k+1k+1, candidate generation joins large itemsets p,q∈Lkp, q \in L_k that share their first k−1k-1 items, yielding a potential candidate (k+1)(k+1)-itemset c=p[1]⋯p[k−1]⋅p[k]⋅q[k]c = p[1] \cdots p[k-1] \cdot p[k] \cdot q[k]. Before admitting cc into Ck+1C_{k+1}, DHP evaluates the hash filter:

    Hk+1[hk+1(c)]≥sH_{k+1}[h_{k+1}(c)] \ge s

    where ss is the minimum support count. If the bucket count is strictly less than ss, no (k+1)(k+1)-itemset hashing to that bucket can possibly be large, and cc is immediately discarded without being added to Ck+1C_{k+1} or inserted into the candidate hash tree.

    To optimize memory and lookup speed, Hk+1H_{k+1} can be represented as a bit vector where entry ii is set to 1 if Hk+1[i]≥sH_{k+1}[i] \ge s and 0 otherwise. Because ∣L1∣|L_1| is typically large, the unconstrained candidate set size (∣L1∣2)\binom{|L_1|}{2} can exceed the actual large 2-itemset size ∣L2∣|L_2| by orders of magnitude; hashing reduces ∣C2∣|C_2| to a level comparable to ∣L2∣|L_2|.

  3. Knowl 3 — Progressive Database Pruning and Transaction Trimming Mechanisms

    model/method

    DHP applies progressive database pruning during database scans by trimming individual items from transactions and discarding transactions that cannot support future large itemsets.

    Pruning relies on the necessary condition of large itemsets: every subset of a large itemset must itself be large. Consequently, for a transaction tt to contain a large (k+1)(k+1)-itemset, it must satisfy two structural requirements:

    1. Candidate Occurrence Count (Item Trimming): If an item ij∈ti_j \in t belongs to any large (k+1)(k+1)-itemset supported by tt, that item must be part of at least kk candidate kk-itemsets from CkC_k contained in tt. During support counting, an array a[j]a[j] tracks the number of candidates in Ck∩2tC_k \cap 2^t that contain iji_j. Any item with a[j]<ka[j] < k is pruned from tt.
    2. Hash Table Verification (Coverage Trimming): Before hashing a (k+1)(k+1)-subset z⊆tz \subseteq t into Hk+1H_{k+1}, DHP verifies that every kk-subset y⊂zy \subset z maps to a bucket with count Hk[hk(y)]≥sH_k[h_k(y)] \ge s. An item iji_j is retained in the candidate transaction only if it belongs to at least one (k+1)(k+1)-subset zz meeting this criterion across all its kk-subsets.
    3. Transaction Dropping: If the number of retained items in transaction tt is less than or equal to kk, or if tt contains no valid (k+1)(k+1)-subsets, tt cannot support any large (k+1)(k+1)-itemset and is excluded from the reduced database Dk+1D_{k+1}.

    This progressive reduction ensures that the number of transactions ∣Dk∣|D_k| and their individual sizes decrease steeply across successive passes kk.

  4. Knowl 4 — DHP Subprocedures for Candidate Generation, Support Counting, and Hash Construction

    algorithm

    The DHP algorithm relies on three subprocedures executed during each iteration kk:

    • gen_candidate: Constructs CkC_k by joining pairs of itemsets cp,cq∈Lk−1c_p, c_q \in L_{k-1} sharing k−2k-2 common items, retaining only those joined itemsets cc whose bucket count in hash table HkH_k satisfies Hk[hk(c)]≥sH_k[h_k(c)] \ge s.
    • count_support: For a transaction tt, finds all candidate matches c∈Ck∩2tc \in C_k \cap 2^t, increments candidate support counters, and tracks item frequencies a[i]a[i] within candidate matches. Items appearing in fewer than kk matching candidates are trimmed, returning transaction t′t'.
    • make_hasht: For each (k+1)(k+1)-subset z⊆t′z \subseteq t', checks whether all kk-subsets y⊂zy \subset z satisfy Hk[hk(y)]≥sH_k[h_k(y)] \ge s. If valid, Hk+1[hk+1(z)]H_{k+1}[h_{k+1}(z)] is incremented, and items covered by valid (k+1)(k+1)-subsets are retained in the final trimmed transaction t′′t''.
    Procedure gen_candidate(Lk−1L_{k-1}, HkH_k)
        Ck←∅C_k \leftarrow \emptyset
        for each pair cp,cq∈Lk−1c_p, c_q \in L_{k-1} with ∣cp∩cq∣=k−2|c_p \cap c_q| = k-2 do
            c←cp[1]⋯cp[k−2]⋅cp[k−1]⋅cq[k−1]c \leftarrow c_p[1] \cdots c_p[k-2] \cdot c_p[k-1] \cdot c_q[k-1]
            if Hk[hk(c)]≥sH_k[h_k(c)] \ge s then
                Ck←Ck∪{c}C_k \leftarrow C_k \cup \{c\}
        return CkC_k
    Procedure count_support(tt, CkC_k, kk)
        Initialize array a[0…∣t∣−1]a[0 \dots |t|-1] to 0
        for each c∈Ckc \in C_k such that c⊆tc \subseteq t do
            c.count←c.count+1c.\text{count} \leftarrow c.\text{count} + 1
            for each item index iji_j in cc do
                a[ij]←a[ij]+1a[i_j] \leftarrow a[i_j] + 1
        t′←∅t' \leftarrow \emptyset
        for i←0i \leftarrow 0 to ∣t∣−1|t|-1 do
            if a[i]≥ka[i] \ge k then
                t′←t′∪{t[i]}t' \leftarrow t' \cup \{t[i]\}
        return t′t'
    Procedure make_hasht(t′t', HkH_k, kk, Hk+1H_{k+1})
        Initialize array a[0…∣t′∣−1]a[0 \dots |t'|-1] to 0
        for each (k+1)(k+1)-subset z⊆t′z \subseteq t' do
            if ∀y⊂z\forall y \subset z with ∣y∣=k|y|=k, Hk[hk(y)]≥sH_k[h_k(y)] \ge s then
                Hk+1[hk+1(z)]←Hk+1[hk+1(z)]+1H_{k+1}[h_{k+1}(z)] \leftarrow H_{k+1}[h_{k+1}(z)] + 1
                for each item index iji_j in zz do
                    a[ij]←a[ij]+1a[i_j] \leftarrow a[i_j] + 1
        t′′←∅t'' \leftarrow \emptyset
        for i←0i \leftarrow 0 to ∣t′∣−1|t'|-1 do
            if a[i]>0a[i] > 0 then
                t′′←t′′∪{t′[i]}t'' \leftarrow t'' \cup \{t'[i]\}
        return t′′t''

  5. Knowl 5 — Synthetic Transaction Dataset Generation Model with Itemset Correlation

    experimental setup

    Synthetic transaction databases for evaluating association rule mining algorithms are generated using a parametric model characterized by notation Tx.Iy.DzTx.Iy.Dz, where x=∣T∣x = |T| is the average transaction size, y=∣I∣y = |I| is the average size of maximal potentially large itemsets, and z×1000=∣D1∣z \times 1000 = |D_1| is the total number of transactions in the initial database D1D_1. Key parameters and generator mechanics include:

    • Vocabulary and Large Itemsets: Total distinct items NN (default 1000); total number of maximal potentially large itemsets ∣L∣=2000|L| = 2000. The size of each itemset in LL is drawn from a Poisson distribution with mean ∣I∣|I|.
    • Clustered Correlation Model: Items in the first itemset of a cluster are selected uniformly at random from the NN items. For the subsequent SqS_q itemsets (where SqS_q is chosen uniformly between 4 and 6), a correlation fraction of items is drawn from the first itemset and remaining items are picked at random. This correlation fraction is exponentially distributed with mean 0.50.5. After Sq+1S_q + 1 itemsets are formed, a new random cycle begins. This structures LL into ∣L∣/(Sq+1)|L|/(S_q + 1) transaction clusters.
    • Itemset Assignment Pool: Each itemset in LL is assigned an exponentially distributed normalized weight. Transactions sample from a pool of 30 to 80 active itemsets. When an itemset is drawn into the pool, it is assigned an occurrence quota equal to its weight multiplied by a factor MI∈[1250,2500]M_I \in [1250, 2500]. Each assignment of an itemset to a transaction decrements its quota until it reaches 0 and is replaced.
    • Corruption Level: Simulates real customer purchases where items within a potentially large itemset are not always bought simultaneously.

  6. Knowl 6 — Sensitivity of DHP Performance and Database Trimming to Hash Table Size

    data/table

    Varying the number of buckets ∣H2∣|H_2| in the hash table directly impacts candidate set size ∣C2∣|C_2|, the pruned database size D3D_3, and overall execution time.

    ∣H2∣|H_2| 524,288 262,144 131,072 95,536 32,768
    ∣L1∣|L_1| 559 559 559 559 559
    ∣{H2≥s}∣|\{H_2 \ge s\}| 58 61 75 96 182
    ∣C2∣|C_2| 81 120 199 394 1,355
    ∣L2∣|L_2| 45 45 45 45 45
    α\alpha 0.0314 0.0320 0.0345 0.0386 0.0545
    Size of D3D_3 498 KB 500 KB 507 KB 539 KB 603 KB
    ∣D3∣|D_3| 19,732 19,741 19,755 20,501 21,607
    Total time (s) 6.44 6.43 6.24 6.77 7.23

    Experiments conducted on dataset T10.I4.D100T10.I4.D100 (∣D1∣=100,000|D_1|=100,000, ∣T∣=10|T|=10, ∣I∣=4|I|=4, N=1000N=1000, ∣L∣=2000|L|=2000, s=0.75%s=0.75\%) demonstrate:

    • When ∣H2∣=524,288≈(N2)|H_2| = 524,288 \approx \binom{N}{2}, ∣C2∣/∣L2∣=81/45=1.80|C_2|/|L_2| = 81/45 = 1.80, whereas Apriori generates (∣L1∣2)=(5592)=155,961\binom{|L_1|}{2} = \binom{559}{2} = 155,961 candidates.
    • Even when ∣H2∣|H_2| is reduced by a factor of 16 to 32,76832,768, ∣C2∣=1,355|C_2| = 1,355, remaining over two orders of magnitude smaller than Apriori's candidate set.
    • α\alpha, the proportion of 2-itemsets from D1D_1 mapping into frequent buckets, remains under 5.5%5.5\%.
    • The size of D3D_3 is trimmed to ≈10.55%\approx 10.55\% of D1D_1's storage size and ≈19.7%\approx 19.7\% of its transaction count, reducing the average transaction length from 10 items to 4.33 items.
    • Optimal runtime occurs around ∣H2∣≈(N2)/4|H_2| \approx \binom{N}{2}/4 (131,072 entries), balancing hash collision filtering against table management overhead.

  7. Knowl 7 — Execution Time and Pruning Comparison Between DHP and Apriori

    data/table

    A pass-by-pass comparison between Apriori and DHP shows how direct candidate pruning and database trimming reduce computational overhead.

    Pass kk Apriori DHP
    ∣Ck∣|C_k| ∣Lk∣|L_k| ∣Ck∣|C_k| (∣Lk∣|L_k|) DkD_k Size, ∣Dk∣|D_k|
    1 1,000 820 1,000 (820) 6,700 KB, 100,000
    2 335,790 207 338 (207) 6,700 KB, 100,000
    3 618 201 618 (201) 659 KB, 20,602
    4 184 98 184 (98) 546 KB, 17,417
    5 30 23 30 (23) 332 KB, 10,149
    6 1 1 1 (1) 24 KB, 756
    Total Time 39.39 s 13.91 s

    On dataset T15.I4.D100T15.I4.D100 with s=0.75%s=0.75\% and ∣H2∣=524,288|H_2|=524,288:

    • In pass 2, Apriori evaluates (8202)=335,790\binom{820}{2} = 335,790 candidates, whereas DHP evaluates only 338 candidates (a 99.9%99.9\% reduction).
    • In Apriori, passes 1 and 2 account for approximately 65%65\% of total execution time. Apriori's first two passes alone consume more time than the entire execution of DHP.
    • While DHP incurs slight overhead in pass 1 to populate H2H_2, it slashes database size in pass 3 to 659 KB659\text{ KB} and 20,60220,602 transactions (9.8%9.8\% of original data volume).
    • DHP achieves faster execution than Apriori in passes 3 through 6 even when using the same candidate generation logic, due entirely to scanning the pruned transaction sets DkD_k.
    • Overall execution time drops from 39.39 s39.39\text{ s} (Apriori) to 13.91 s13.91\text{ s} (DHP), a speedup of 2.83×2.83\times.

  8. Knowl 8 — Dynamics of Transaction Count and Item Trimming Across Iterations

    empirical result

    Progressive database reduction in DHP exhibits distinct interactions between transaction elimination and individual item trimming across successive mining passes:

    1. Transaction Count Decay: The number of retained transactions ∣Dk∣|D_k| drops rapidly as pass number kk increases. For an initial dataset of 100,000 transactions with s=0.75%s=0.75\% (T15.I4.D100T15.I4.D100 and T20.I4.D100T20.I4.D100), ∣Dk∣|D_k| decreases to approximately 20,000 transactions at pass 3, drops below 5,000 at pass 5, and falls under 1,000 transactions by pass 6.
    2. Opposing Effects on Average Transaction Length: Trimming non-qualifying items decreases the average number of items per transaction. However, transaction removal disproportionately eliminates shorter transactions that fail to contain k+1k+1 items, which pushes the average transaction size upward. Due to these opposing effects, the average transaction length in DkD_k stabilizes after an initial drop (e.g., for T20.I4.D100T20.I4.D100, starting at 20 items, transaction length drops to 7.5 items at pass 3 and remains around 7 to 8 items in subsequent passes).
    3. Isolated Trimming Effect: When small transactions are retained rather than deleted, the average number of items per transaction drops monotonically toward 0 across passes (falling below 1 item by pass 5 and below 0.3 items by pass 6), confirming that the item-level pruning criteria actively remove non-participating items.

  9. Knowl 9 — Scalability of DHP Across Database Size and Item Vocabulary

    data/table

    DHP demonstrates linear execution time scaling with total transaction volume ∣D∣|D| and robust stability as the distinct item vocabulary NN increases.

    NN T5.I2.D100T5.I2.D100 T10.I4.D100T10.I4.D100 T20.I6.D100T20.I6.D100
    1,000 2.26 s 6.69 s 20.44 s
    2,500 2.46 s 6.88 s 21.42 s
    5,000 2.59 s 7.57 s 23.47 s
    7,500 2.68 s 7.53 s 23.95 s
    10,000 2.64 s 7.91 s 23.75 s

    Scalability properties demonstrated across benchmarks include:

    • Database Size Scale-Up: When scaling ∣D∣|D| from 100,000 to 1,000,000 transactions on an RS/6000 workstation (model 560), total execution time increases strictly linearly across short (T10.I4T10.I4), medium (T15.I4T15.I4), and long (T20.I4T20.I4) transaction profiles.
    • Item Vocabulary Scale-Up (NN from 1,000 to 10,000): At fixed minimum support s=0.75%s=0.75\% and hash table size set to the power of 2 greater than (N2)\binom{N}{2}, execution time remains nearly flat. While larger NN slightly increases pass 1 time (since ∣L1∣≈N|L_1| \approx N), candidate frequencies for higher-order itemsets disperse across more items, reducing higher-order candidate counts and compensating for the larger vocabulary size.

Coverage note — None was omitted; all key algorithmic mechanisms, pruning criteria, synthetic data parameters, and empirical performance evaluations from the paper are represented.

References

  1. 1.R. Agrawal, C. Faloutsos, and A. Swami. Efficient Similarity Search in Sequence Databases. Proceedings of the 4th Intl. conf. on Foundations of Data Organization and Algorithms, October, 1993.
  2. 2.R. Agrawal, S. Ghosh, T. Imielinski, B. Iyer, and A. Swami. An Interval Classifier for Database Mining Applications. Proceedings of the 18th International Conference on Very Large Data Bases, pages 560-573, August 1992.
  3. 3.R. Agrawal, T. Imielinski, and A. Swami. Mining Association Rules between Sets of Items in Large Databases. Proceedings of ACM SIGMOD, pages 207-216, May 1993.
  4. 4.R. Agrawal and R. Srikant. Mining Sequential Patterns. Proceedings of the 11th International Conference on Data Engineering, March 1995.
  5. 5.R. Agrawal and S. Srikant. Fast Algorithms for Mining Association Rules in Large Databases. Proceedings of the 20th International Conference on Very Large Data Bases, September 1994.
  6. 6.T.M. Anwar, H.W. Beck, and S.B. Navathe. Knowledge Mining by Imprecise Querying: A Classification-Based Approach. Proceedings of the 8th International Conference on Data Engineering, February 1992.
  7. 7.J. Han, Y. Cai, , and N. Cercone. Knowledge Discovery in Databases: An Attribute-Oriented Approach. Proceedings of the 18th International Conference on Very Large Data Bases, pages 547– 559, August 1992.
  8. 8.M. Houtsma and A. Swami. Set-Oriented Mining of Association Rules. Technical Report RJ 9567, IBM Almaden Research Laboratory, San Jose, CA, October 1993.
  9. 9.E. G. Coffman Jr. and J. Eve. File structures using hashing functions. Comm. of the ACM, 13(7):427– 432, 436, July 1970.
  10. 10.R.T. Ng and J. Han. Efficient and Effective Clustering Methods for Spatial Data Mining. Proceedings of the 18th International Conference on Very Large Data Bases, pages 144–155, September 1994.
  11. 11.G. Piatetsky-Shapiro. Discovery, Analysis and Presentation of Strong Rules. Knowledge Discovery in Databases, 1991.
  12. 12.J.R. Quinlan. Induction of Decision Trees. Machine Learning, 1:81–106, 1986.

Citation

MLA
Park, J. S., et al. “An Effective Hash-based Algorithm for Mining Association Rules”. Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data - SIGMOD '95, 1995, pp. 175–86, https://doi.org/10.1145/223784.223813.
APA
Park, J. S., Chen, M.-S., & Yu, P. S. (1995). An effective hash-based algorithm for mining association rules. Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data - SIGMOD '95, 175–186. https://doi.org/10.1145/223784.223813
Chicago
Park, J. S., M.-S. Chen, and P. S. Yu. 1995. “An Effective Hash-based Algorithm for Mining Association Rules”. Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data - SIGMOD '95, 175–86. https://doi.org/10.1145/223784.223813.
Harvard
Park, J.S., Chen, M.-S. and Yu, P.S. (1995) “An effective hash-based algorithm for mining association rules”, Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95. ACM Press, pp. 175–186. Available at: https://doi.org/10.1145/223784.223813.
Vancouver
1. Park JS, Chen M-S, Yu PS (1995) An effective hash-based algorithm for mining association rules. In: Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95. ACM Press, pp 175–186

BibTeX

@inproceedings{Park_1995, series={SIGMOD ’95}, title={An effective hash-based algorithm for mining association rules}, url={http://dx.doi.org/10.1145/223784.223813}, DOI={10.1145/223784.223813}, booktitle={Proceedings of the 1995 ACM SIGMOD international conference on Management of data  - SIGMOD ’95}, publisher={ACM Press}, author={Park, Jong Soo and Chen, Ming-Syan and Yu, Philip S.}, year={1995}, pages={175–186}, collection={SIGMOD ’95} }
Metadata:Crossref

Access the Paper

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

Open PDF