Dynamic itemset counting and implication rules for market basket data

Sergey BrinRajeev MotwaniJeffrey D. UllmanShalom Tsur

article1997SIGMOD2,449 citations

Presents dynamic itemset counting and normalized implication rules that reduce database passes and yield more intuitive market-basket relationships.

Listen

Organizations increasingly rely on market-basket data mining to discover meaningful relationships across large transaction datasets, from retail sales to public records. However, traditional mining approaches face two significant hurdles: standard algorithms require numerous expensive passes over large databases, and standard rule-evaluation metrics like confidence and interest frequently produce misleading or uninformative conclusions by failing to distinguish genuine directional implications from mere baseline popularity. The article set out to introduce and evaluate Dynamic Itemset Counting, a more efficient algorithm for identifying frequent itemsets, alongside conviction, a new statistical metric for deriving true implication rules.

The authors evaluated their approach through comparative experiments against the established Apriori benchmark using two distinct datasets: a synthetic retail dataset of 100,000 records and a complex, real-world 1990 U.S. Census sample containing roughly 30,000 records with 73 selected attributes. The evaluation assessed computational runtimes, pass counts across data, the impact of transaction reordering, and the qualitative accuracy of generated association rules.

The analysis yielded several key findings. First, Dynamic Itemset Counting significantly reduced data passes and computational time, outperforming Apriori by approximately 30% on synthetic data at low support thresholds and running up to 3.7 times faster on census data when transaction order was randomized. Second, Dynamic Itemset Counting achieved near-complete processing in roughly 1.3 to 2.1 passes at optimal check intervals (300 to 1,000 transactions), compared to the 10 full passes required by Apriori. Third, the new conviction metric successfully filtered out misleading correlations caused by highly frequent items, accurately capturing directional implication where standard confidence and interest metrics fell short. Finally, item reordering within underlying tree structures produced negligible performance benefits (under 10%), showing that algorithmic scheduling rather than low-level data structure reordering drove efficiency gains.

These findings indicate that organizations can substantially reduce data processing costs, execution times, and computational resource demands when analyzing large transactional systems. Furthermore, adopting conviction improves analytical decision-making by prioritizing genuinely relevant, actionable relationships over obvious or spurious baseline patterns.

Decision-makers implementing data mining workflows should consider adopting Dynamic Itemset Counting paired with transaction randomization and moderate check intervals (between 300 and 1,000 records) to maximize throughput. Additionally, analytical pipelines should incorporate rule-pruning techniques, such as eliminating non-minimal rules, which can reduce raw rule output volume by more than a factor of five without losing analytical value. Further work is recommended to explore dynamic interval tuning, distributed parallel implementations, and automated handling of non-randomized or streaming data.

While confidence in the core computational speedups and statistical accuracy of conviction is high, readers should note that the performance advantages of Dynamic Itemset Counting are sensitive to data homogeneity and record ordering. In highly correlated or non-randomized datasets, additional preprocessing like random shuffling is essential to achieve optimal efficiency.

Hitachi America Ltd.Stanford University association rules Dynamic Itemset Counting DIC algorithm market basket data

Brin et al (1997).pdf

Paper: Fast Algorithms for Mining Association Rules in Large Databases, R. Agrawal et al. (1994). Reading this foundational paper first is essential because it introduces the Apriori algorithm, which serves as the primary benchmark and computational baseline evaluated in the source work.
Paper: Mining association rules between sets of items in large databases, R. Agrawal et al. (1993). Understanding this earlier work is crucial as it establishes the original problem definition and multi-pass database scanning approach for mining association rules that the source later aims to accelerate.

Paper: Mining frequent patterns without candidate generation, Jiawei Han et al. (2000). This later work directly extends the pursuit of efficient association rule mining by introducing a tree-based frequent pattern growth method that completely eliminates candidate generation.

Cover for Dynamic itemset counting and implication rules for market basket data

Abstract

We consider the problem of analyzing market-basket data and present several important contributions. First, we present a new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling. We investigate the idea of item reordering, which can improve the low-level efficiency of the algorithm. Second, we present a new way of generating “implication rules,” which are normalized based on both the antecedent and the consequent and are truly implications (not simply a measure of co-occurrence), and we show how they produce more intuitive results than other methods. Finally, we show how different characteristics of real data, as opposed to synthetic data, can dramatically affect the performance of the system and the form of the results.

Topics

association rules

Keywords

Dynamic Itemset Counting DIC algorithm market basket data mining association rules implication rules large itemsets minimal small itemsets support threshold incremental updates

1 Introduction
1.1 Algorithms for Finding Large Itemsets
1.2 Implication Rules
2 Counting Large ltemsets
2.1 The Data Structure
3 Item Reordering
2.2 Significance of DIC
4 Implication rules
5 Results
5.1 Test Data
5.2 Test Implementations
5.3 Relative Performance of DIC and Apriori
5.3.1 Performance on the Census Data
5.4 Varying the Interval Size
5.5 Effect of Item Reordering
5.6 Tests of Implication Rules
6 Conclusions
6.1 Finding Large Itemsets
6.1.1 Parallelism
6.1.2 Incremental Updates
6.1.3 Census Data
6.2 Implication Rules
Acknowledgements
References

Knowls

Knowl 1 — Conviction Measure for Implication Rules
definition
For two itemsets $A$ and $B$ , the conviction of the implication rule $A \to B$ measures the degree of implication of $B$ by $A$ and is defined in terms of transaction probabilities as:

$\text{conviction}(A \to B) = \frac{P(A) P(\neg B)}{P(A, \neg B)}$

where $P(A)$ is the probability that a transaction contains $A$ , $P(\neg B) = 1 - P(B)$ is the probability that a transaction does not contain $B$ , and $P(A, \neg B)$ is the joint probability that a transaction contains $A$ but does not contain $B$ .

Conviction exhibits the following properties:
- Independence Baseline: If $A$ and $B$ are statistically independent, $P(A, \neg B) = P(A)P(\neg B)$ , yielding a conviction value of $1$ . Values greater than $1$ indicate positive implication.
- Logical Implication Limit: If the rule holds without exception ( $P(B \mid A) = 1$ ), the counterexample probability $P(A, \neg B)$ is $0$ , resulting in an infinite conviction value ( $\infty$ ).
- Directionality: Unlike symmetrical correlation measures such as interest (lift), $\text{conviction}(A \to B) \neq \text{conviction}(B \to A)$ .
- Consequent Normalization: Unlike confidence $P(B \mid A)$ , conviction incorporates $P(B)$ and does not award high scores to rules simply because the consequent $B$ has high baseline frequency in the dataset.
In computational implementations, searching for minimal values of the un-inverted ratio $\frac{P(A, \neg B)}{P(A)P(\neg B)}$ avoids handling infinite values directly.
Knowl 2 — Dynamic Itemset Counting Algorithm
algorithm
Dynamic Itemset Counting (DIC) discovers all large itemsets with support exceeding a threshold $\sigma$ by dynamically starting counters for candidate itemsets at intervals of $M$ transactions throughout dataset passes, rather than waiting for full dataset passes as in level-wise algorithms.
Input: Database D of transactions, support threshold $\sigma$ , checkpoint interval M
Output: Set of all large itemsets L
Initialize empty itemset with state solid_large
Initialize all 1-itemsets with state dashed_small and count 0
All other itemsets remain unmarked
Set transactions_read = 0
while there exist itemsets with dashed states do
    Read next transaction S from D (or rewind to start of D if at EOF)
    Increment counters for all dashed itemsets contained in S
    Increment transactions_read

    if transactions_read mod M == 0 or EOF reached then
        for each itemset I currently being tracked do
            if state(I) == dashed_small and count(I) >= $\sigma$ * |D| then
                state(I) = dashed_large
                for each immediate superset K of I do
                    if K is unmarked and all immediate subsets of K are in {dashed_large, solid_large} then
                        state(K) = dashed_small
                        count(K) = 0
                        start_point(K) = current position in D
                    end if
                end for
            end if
            if (I has been counted across all |D| transactions since start_point(I)) then
                if count(I) >= $\sigma$ * |D| then
                    state(I) = solid_large
                else
                    state(I) = solid_small
                end if
            end if
        end for
    end if
end while
return all itemsets with state solid_large
Knowl 3 — Itemset State Classification and Candidate Expansion in Dynamic Itemset Counting
model/method
In the Dynamic Itemset Counting (DIC) framework, itemsets in the itemset lattice are categorized into four dynamic states based on whether counting has completed across the entire dataset and whether their observed occurrence count meets the support threshold $\sigma$ :
- Solid Large (Confirmed Large): An itemset that has been counted through all transactions in the dataset and whose support count is $\ge \sigma$ .
- Solid Small (Confirmed Small): An itemset that has been counted through all transactions in the dataset and whose support count is $< \sigma$ .
- Dashed Large (Suspected Large): An active itemset whose counting is in progress across the dataset and whose accumulated count already exceeds the support threshold $\sigma$ .
- Dashed Small (Suspected Small): An active itemset whose counting is in progress across the dataset and whose accumulated count has not yet reached the support threshold $\sigma$ .
Candidate generation occurs dynamically: whenever an active dashed small itemset reaches the support threshold and becomes a dashed large itemset, all of its immediate supersets (itemsets of size $k+1$ ) are evaluated. Any superset whose full collection of size- $k$ subsets are all confirmed or suspected large (solid large or dashed large) is immediately instantiated into the trie as a dashed small itemset with an active counter starting at the current transaction checkpoint.
Knowl 4 — Trie Counter Increment Traversal and Cost Model
equation
In candidate itemset tracking, itemsets are stored in a trie where the empty set is the root node, and each edge is labeled by an item according to a fixed sorting order. For a transaction $S = [S[0], S[1], \dots, S[n]]$ containing $n+1$ sorted items, candidate matching traverses the trie recursively:
procedure Increment(T, S)
    T.counter = T.counter + 1
    if T is not a leaf then
        for i = 0 to length(S) - 1 do
            if T.branches[S[i]] exists then
                Increment(T.branches[S[i]], S[i + 1 .. length(S) - 1])
            end if
        end for
    end if
end procedure
The computational cost (number of loop iterations) incurred when processing transaction $S$ against trie $T$ is given by:

$\text{Cost}(S, T) = \sum_{I} \left( n - \text{Index}(\text{Last}(I), S) \right)$

where $I$ ranges over all non-leaf itemsets in $T$ that are subsets of $S$ , $\text{Last}(I)$ denotes the last item of prefix $I$ under the sort order, and $\text{Index}(\text{Last}(I), S)$ is the $0$ -based index position of that item in the sorted transaction array $S$ .
Knowl 5 — Item Reordering by Inverse Itemset Popularity
model/method
To minimize the trie traversal cost $\sum_{I} (n - \text{Index}(\text{Last}(I), S))$ , items should be sorted such that items appearing in many candidate itemsets have high index values (placed late in the sort order), leaving fewer remaining items in the transaction slice $S[i+1 \dots n]$ to be checked in recursive loops.

Because the exact distribution of non-leaf candidate itemsets is unknown prior to mining, the inverse of item frequencies observed in the first $M$ transactions is used as an empirical proxy for candidate popularity. After reading the first $M$ transactions, the global item sorting order is rearranged to place the most popular 1-itemsets at the end, the candidate trie is constructed according to this updated sort order, and subsequent transactions are reordered accordingly before being matched against the trie.
Knowl 6 — Non-Minimal Implication Rule Pruning
model/method
When mining datasets with dense attribute correlations, implication rule generation produces thousands of redundant rules. Redundant non-minimal rules are filtered out by applying the following pruning criterion:

An implication rule $I \to C$ (where $I$ is an antecedent itemset and $C$ is a consequent itemset) is pruned if there exists a sub-rule $I' \to C$ such that $I' \subset I$ and:

$\text{conviction}(I' \to C) \ge \text{conviction}(I \to C)$

On dense datasets such as U.S. Census microdata, pruning all non-minimal rules with equal or lower conviction than their sub-rules reduces the total number of generated rules by more than a factor of 5 while eliminating lengthy, uninformative rules.
Knowl 7 — Comparative Performance and Pass Count of Dynamic Itemset Counting vs Apriori
empirical result
Dynamic Itemset Counting (DIC) and Apriori were benchmarked on two datasets:
- Synthetic Data ( $100{,}000$ transactions, $1{,}000$ items, average transaction size $20$ , average large itemset size $4$ ): Apriori was approximately $30\%$ faster than DIC at high support thresholds ( $0.02$ ). At lower support thresholds ( $0.005$ ), DIC outperformed Apriori, running approximately $30\%$ faster.
- U.S. Census PUMS Data ( $30{,}000$ $30, 000$ records for Washington D.C., $73$ $73$ attributes yielding $2{,}166$ $2, 166$ items after bucketization, items with $>80\%$ $> 80%$ support removed):
  - At support threshold $0.36$ , Apriori required $10$ full dataset passes to complete execution.
  - Standard DIC without data randomization made $9$ passes over the dataset.
  - Randomized DIC completed in $1.3$ to $2.1$ passes for $M \in \{100, 300, 1000\}$ and achieved a execution speedup of $3.2\times$ over Apriori at support $0.36$ , and $3.7\times$ over Apriori at support $0.38$ .
Knowl 8 — Impact of Transaction Order Randomization on Dynamic Itemset Counting over Non-Homogeneous Data
empirical result
The efficiency of Dynamic Itemset Counting depends heavily on data homogeneity across the transaction sequence. In spatially clustered datasets, such as census records ordered by geographic district, high correlation causes large itemsets to appear infrequently in initial intervals and cross the support threshold only near the end of a pass, forcing DIC to require nearly as many passes as Apriori ( $9$ passes vs $10$ passes for Apriori at support $0.36$ ).

Randomizing the order of transactions before running DIC resolves this bottleneck by distributing item occurrences uniformly across intervals. On the Washington D.C. census dataset at support threshold $0.36$ with $M = 10{,}000$ , randomizing transaction order reduced the required number of passes from $9$ down to $4$ , and with lower $M$ down to $1.3$ passes, leading to a more than three-fold runtime speedup over Apriori.
Knowl 9 — Effect of Checkpoint Interval Size on Dynamic Itemset Counting Performance
empirical result
The performance of Dynamic Itemset Counting on randomized census data depends on the interval parameter $M$ :
- Intermediate Intervals ( $M = 300$ and $M = 1000$ ): Produced the lowest execution times, completing counting in $1.3$ and $2.1$ passes respectively at support threshold $0.36$ , balancing candidate activation speed with state maintenance overhead.
- Small Interval ( $M = 100$ ): Incurred high computational overhead due to the cost of checking lattice states and trie expansions at every checkpoint, resulting in the worst execution time despite finishing in $1.3$ passes.
- Large Interval ( $M = 10{,}000$ ): Delayed the detection and promotion of suspected large itemsets, increasing the required number of passes to $4$ and resulting in higher execution time than intermediate values.

Coverage note — Omitted speculative discussions on future parallel and streaming extensions (such as the two-train FIFO model for incremental updates) and unresolved considerations regarding transitive implication rule pruning.

References

1.R. Agrawal, T. Imilienski, and A. Swami. Database Mining: A Performance Perspective. IEEE Transactions on Knowledge and Data Engineering, 5(6):914–925, December 1993.
2.R. Agrawal, T. Imilienski, and A. Swami. Mining Association Rules between Sets of Items in Large Databases. Proc. of the ACM SIGMOD Int'l Conf. on Management of Data, pages 207–216, May 1993.
3.R. Agrawal, K. Lin, S. Sawhney, and K. Shim. Fast similarity search in the presence of noise, scaling and translation in time-series databases. In Proc. of the Int'l Conf. on Very Large Data Bases (VLDB), 1995.
4.R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994.
5.R. Agrawal and R. Srikant. Mining sequential patterns. In Proceedings of the 11th International Conference on Data Engineering, Taipei, Taiwan, 1995.
6.M. Mehta, R. Agrawal, and J. Rissanen. Sliq: A fast scalable classifier for data mining. March 1996.
7.R. Srikant and R. Agrawal. Mining generalized association rules. 1995.
8.H. Toivonen. Sampling large databases for association rules. Proc. of the Int'l Conf. on Very Large Data Bases (VLDB), 1996.

Citation

MLA

Brin, S., et al. “Dynamic Itemset Counting and Implication Rules for Market Basket Data”. Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data - SIGMOD '97, 1997, pp. 255–64, https://doi.org/10.1145/253260.253325.

APA

Brin, S., Motwani, R., Ullman, J. D., & Tsur, S. (1997). Dynamic itemset counting and implication rules for market basket data. Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data - SIGMOD '97, 255–264. https://doi.org/10.1145/253260.253325

Chicago

Brin, S., R. Motwani, J. D. Ullman, and S. Tsur. 1997. “Dynamic Itemset Counting and Implication Rules for Market Basket Data”. Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data - SIGMOD '97, 255–64. https://doi.org/10.1145/253260.253325.

Harvard

Brin, S. et al. (1997) “Dynamic itemset counting and implication rules for market basket data”, Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97. ACM Press, pp. 255–264. Available at: https://doi.org/10.1145/253260.253325.

Vancouver

1. Brin S, Motwani R, Ullman JD, Tsur S (1997) Dynamic itemset counting and implication rules for market basket data. In: Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97. ACM Press, pp 255–264

BibTeX

@inproceedings{Brin_1997, series={SIGMOD ’97}, title={Dynamic itemset counting and implication rules for market basket data}, url={http://dx.doi.org/10.1145/253260.253325}, DOI={10.1145/253260.253325}, booktitle={Proceedings of the 1997 ACM SIGMOD international conference on Management of data  - SIGMOD ’97}, publisher={ACM Press}, author={Brin, Sergey and Motwani, Rajeev and Ullman, Jeffrey D. and Tsur, Shalom}, year={1997}, pages={255–264}, collection={SIGMOD ’97} }

Metadata:Crossref

Access the Paper

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

Open PDF

Dynamic itemset counting and implication rules for market basket data

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Conviction Measure for Implication Rules

Knowl 2 — Dynamic Itemset Counting Algorithm

Knowl 3 — Itemset State Classification and Candidate Expansion in Dynamic Itemset Counting

Knowl 4 — Trie Counter Increment Traversal and Cost Model

Knowl 5 — Item Reordering by Inverse Itemset Popularity

Knowl 6 — Non-Minimal Implication Rule Pruning

Knowl 7 — Comparative Performance and Pass Count of Dynamic Itemset Counting vs Apriori

Knowl 8 — Impact of Transaction Order Randomization on Dynamic Itemset Counting over Non-Homogeneous Data

Knowl 9 — Effect of Checkpoint Interval Size on Dynamic Itemset Counting Performance

References

Citation

BibTeX

Access the Paper