Scalable Algorithms for Association Mining

Mohammed J. Zaki

article2000TKDE1,908 citations

Introduces the ECLAT and related lattice-decomposition algorithms for frequent itemset mining, demonstrating an order-of-magnitude speedup over Apriori by combining vertical database layouts with independent memory-bound sublattice search strategies.

Listen

Organizations increasingly rely on discovering shared patterns across vast volumes of customer transactions to optimize retail layouts, catalog designs, and diagnostic systems. However, uncovering these frequent associations in massive datasets is computationally expensive and constrained by disk operations. Established methods require repeated scans over the entire database and rely on intricate internal memory structures that cause substantial processing delays when handling millions of records.

The article develops and evaluates scalable data mining algorithms designed to identify frequent item combinations rapidly while minimizing costly database reads. Specifically, it demonstrates how organizing items into mathematical structures called lattices allows the search space to be broken down into independent chunks that can be processed directly in computer memory.

The evaluated approach utilizes a vertical data format where each item tracks its own list of transaction identifiers. By performing simple intersection operations between these lists, the system determines pattern frequencies without building complex indexing trees. The article introduces techniques to decompose the full problem into smaller subproblems using common item prefixes or graph clusters known as maximal cliques, combined with bottom-up, top-down, or hybrid search strategies. Testing was conducted on synthetic retail benchmark databases scaling from 100,000 up to 5 million transactions, assessing performance under varying pattern lengths and transaction volumes.

The experimental findings show that the proposed methods dramatically outperform traditional techniques. The leading algorithm, MaxClique, reduced search candidate operations by factors ranging from 3 to 35 and accelerated execution speeds by a factor of 20 to over 30 compared to standard benchmarks like Apriori, reaching improvements exceeding two orders of magnitude in challenging scenarios. The baseline vertical algorithm, Eclat, routinely outperformed traditional tools by more than an order of magnitude while maintaining an average memory footprint of under 2 percent of total database size. Furthermore, the hybrid search methods successfully discovered long patterns of over 20 items where previous methods failed due to memory exhaustion, all while demonstrating linear scaling as transaction volumes grew.

These results demonstrate that organizations can process enterprise-scale association mining tasks with significantly lower hardware overhead, shorter processing windows, and reduced memory costs. Because the core operations rely on list intersections, these algorithms can be integrated directly into relational database management systems using standard database query operations, reducing the risk and cost of deploying specialized external data structures.

Technical leaders seeking to implement frequent pattern mining should deploy the MaxClique algorithm when long frequent combinations exist and graph density remains manageable, while using Eclat as a robust default when processing very dense datasets or extremely low support thresholds. Systems can be configured with modest memory allocations, as subproblem decomposition keeps working memory requirements exceptionally low.

The primary operational limitation involves dense association graphs—which occur under very large transaction sizes or very low support thresholds—where clique generation introduces computational overhead and overlap. The article provides high confidence in linear scalability across large transaction volumes on benchmark datasets, though organizations operating on unusually dense item relationships should evaluate prefix-based approaches before committing to clique-based partitioning.

Rensselaer Polytechnic Institute association mining efficient algorithm frequent itemsets association mining maximal frequent itemsets association rules

zakimjz/ECLAT Zaki (2000).pdf

Paper: Fast Algorithms for Mining Association Rules in Large Databases, R. Agrawal et al. (1994). It introduces the foundational Apriori algorithm and level-wise candidate generation framework that the source specifically seeks to accelerate and decompose using subset lattice traversal.
Paper: Mining association rules between sets of items in large databases, R. Agrawal et al. (1993). It defines the core problem of mining association rules from large transactional databases and establishes the two-phase paradigm of finding frequent itemsets before generating rules.
Paper: Dynamic itemset counting and implication rules for market basket data, Sergey Brin et al. (1997). It presents dynamic itemset counting as an early advancement over Apriori to reduce database passes, establishing key multi-pass optimization challenges addressed by the source.
Paper: Data Mining: An Overview from a Database Perspective, Ming-Syan Chen et al. (1996). It provides a comprehensive overview of early data mining and association rule discovery methods from a database perspective, detailing the candidate generation and vertical layout trade-offs analyzed in the source.

Paper: Mining frequent patterns without candidate generation, Jiawei Han et al. (2000). It takes frequent itemset discovery beyond candidate generation and lattice traversal entirely by introducing the FP-tree and FP-growth algorithm.
Paper: Mining and summarizing customer reviews, Minqing Hu et al. (2004). It directly applies association rule mining techniques to extract frequent feature terms and summarize opinions from online customer reviews.

Cover for Scalable Algorithms for Association Mining

Abstract

Association rule discovery has emerged as an important problem in knowledge discovery and data mining. The association mining task consists of identifying the frequent itemsets and then, forming conditional implication rules among them. In this paper, we present efficient algorithms for the discovery of frequent itemsets which forms the compute intensive phase of the task. The algorithms utilize the structural properties of frequent itemsets to facilitate fast discovery. The items are organized into a subset lattice search space, which is decomposed into small independent chunks or sublattices, which can be solved in memory. Efficient lattice traversal techniques are presented which quickly identify all the long frequent itemsets and their subsets if required. We also present the effect of using different database layout schemes combined with the proposed decomposition and traversal techniques. We experimentally compare the new algorithms against the previous approaches, obtaining improvements of more than an order of magnitude for our test databases.

Topics

association mining efficient algorithm frequent itemsets transaction database frequent patterns rule mining knowledge discovery in database

Keywords

association mining maximal frequent itemsets association rules association graph intermediate tid-lists lattice-based approach support counting maximal cliques parallel algorithms bottom-up search

1 INTRODUCTION
2 PROBLEM STATEMENT
3 RELATED WORK
4 ITEMSET ENUMERATION: LATTICE-BASED APPROACH
4.1 Support Counting
4.2 Lattice Decomposition: Prefix-Based Classes
4.3 Search for Frequent Itemsets
4.3.1 Bottom-Up Search
4.3.2 Top-Down Search
4.3.3 Hybrid Search
4.4 Generating Smaller Classes: Maximal Clique Approach
4.4.1 Maximal Clique Generation
5 ALGORITHM DESIGN AND IMPLEMENTATION
5.1 Computing Frequent 1-Itemsets and 2-Itemsets
5.2 Search Implementation
5.3 Number of Database Scans
5.4 New Algorithms
6 THE APRIORI AND PARTITION ALGORITHMS
7 EXPERIMENTAL RESULTS
8 CONCLUSIONS
APPENDIX A ITEMSETS
A.1 Finding Maximum Frequent Itemsets
REFERENCES

Knowls

Knowl 1 — Support Counting via Vertical Tid-List Intersections
model/method
Let $\mathcal{I}$ be a set of items and $\mathcal{D}$ be a transaction database where each transaction has a unique identifier (tid). In a vertical database layout, each itemset $X \subseteq \mathcal{I}$ is associated with its tid-list $\mathcal{L}(X)$ , which consists of all transaction identifiers containing $X$ . The support $\sigma(X)$ of an itemset $X$ is the cardinality of its tid-list: $\sigma(X) = |\mathcal{L}(X)|$

For any itemset $X$ expressed as the union of a collection of itemsets $J = \{Y_1, Y_2, \dots, Y_m\}$ (where $X = \bigcup_{Y \in J} Y$ ), its support is determined by the intersection of the component tid-lists: $\sigma(X) = \left| \bigcap_{Y \in J} \mathcal{L}(Y) \right|$

In particular, the tid-list of any $k$ -itemset $X$ can be computed by intersecting the tid-lists of any two of its $(k-1)$ -subsets, $\mathcal{L}(A)$ and $\mathcal{L}(B)$ : $\mathcal{L}(A \cup B) = \mathcal{L}(A) \cap \mathcal{L}(B)$

If $X \subseteq Y$ , then $\mathcal{L}(Y) \subseteq \mathcal{L}(X)$ , meaning tid-list cardinalities decrease monotonically as itemset length grows, which progressively accelerates support counting at deeper levels of the search space.
Knowl 2 — Prefix-Based Lattice Decomposition via Equivalence Relation Theta-k
model/method
Let $\mathcal{P}(\mathcal{I})$ be the powerset lattice of items $\mathcal{I}$ , and let $p(X, k)$ denote the $k$ -length prefix of an itemset $X$ under a fixed lexicographic ordering. An equivalence relation $\theta_k$ on $\mathcal{P}(\mathcal{I})$ is defined by: $X \equiv_{\theta_k} Y \iff p(X, k) = p(Y, k)$

Each equivalence class $[X]_{\theta_k} = \{ Y \in \mathcal{P}(\mathcal{I}) \mid p(Y, k) = X \}$ is a sublattice of $\mathcal{P}(\mathcal{I})$ and forms a Boolean lattice with bottom element $X$ , top element $\bigcup_{Y \in [X]_{\theta_k}} Y$ , and atoms corresponding to the frequent extensions $\{X \cup \{i\} \mid X \cup \{i\} \in \mathcal{F}_{k+1}\}$ , where $\mathcal{F}_{k+1}$ is the set of frequent $(k+1)$ -itemsets.

Each equivalence class $[X]_{\theta_k}$ can be loaded and solved independently in main memory via tid-list intersections of its atoms. Processing the classes in reverse lexicographical order ensures that all subsets of an itemset are evaluated before the itemset itself, allowing downward-closure pruning without inter-class synchronization. If a class $[X]_{\theta_k}$ is too large to fit in main memory, the decomposition is applied recursively by partitioning under $\theta_{k+1}$ .
Knowl 3 — Maximal-Clique-Based Lattice Decomposition via Pseudoequivalence Relation Phi-k
model/method
Let $\mathcal{F}_k$ be the set of frequent $k$ -itemsets. The $k$ -association graph is an undirected graph $G_k = (V, E)$ with vertex set $V = \mathcal{F}_1$ and edge set: $E = \{ (X, Y) \mid X, Y \in V \text{ and } \exists Z \in \mathcal{F}_{k+1} \text{ such that } X, Y \subset Z \}$ Let $M_k$ be the set of all maximal cliques in $G_k$ . A pseudoequivalence relation $\phi_k$ on $\mathcal{P}(\mathcal{I})$ is defined by: $X \equiv_{\phi_k} Y \iff \exists C \in M_k \text{ such that } X, Y \subseteq C \text{ and } p(X, k) = p(Y, k)$

Each pseudoclass $[X]_{\phi_k}$ is a sublattice of $\mathcal{P}(\mathcal{I})$ and a Boolean lattice. Every pseudoclass $[Y]_{\phi_k}$ is a subset of some prefix-based class $[X]_{\theta_k}$ , and each prefix class $[X]_{\theta_k}$ equals the union of a set of pseudoclasses from $\phi_k$ : $[X]_{\theta_k} = \bigcup \{ [Z]_{\phi_k} \mid Z \text{ is a prefix of } X \}$

Because maximal cliques eliminate edges between items that do not co-occur in any frequent $(k+1)$ -itemset, $[X]_{\phi_k}$ contains fewer atoms than $[X]_{\theta_k}$ , thereby significantly reducing the number of candidate pairwise intersections during search.
Knowl 4 — Bottom-Up Sublattice Itemset Search
algorithm
The bottom-up search strategy enumerates all frequent itemsets within an independent sublattice $S$ by performing recursive pairwise tid-list intersections level by level. It only requires holding intermediate tid-lists for at most two consecutive itemset lengths in main memory.
procedure Bottom-Up(S)
    Input: S, a set of frequent itemset atoms in the current sublattice
    Output: Enumeration of all frequent itemsets in the sublattice
    for each atom A_i in S do
        T_i = empty_set
        for each atom A_j in S with j > i do
            R = A_i union A_j
            L(R) = L(A_i) intersection L(A_j)
            if |L(R)| >= min_sup then
                T_i = T_i union {R}
                Record R as frequent
            end if
        end for
        if T_i is not empty then
            Bottom-Up(T_i)
        end if
    end for
end procedure
Knowl 5 — Hybrid Sublattice Itemset Search
algorithm
The hybrid search strategy prioritizes finding long maximal frequent itemsets before completing the enumeration of remaining frequent itemsets. Atoms within a sublattice $S$ are sorted in descending order of support based on the heuristic that higher support atoms are more likely to participate in longer frequent patterns. The search operates in two phases: a maximal phase that greedily extends a candidate itemset atom-by-atom until an extension becomes infrequent, followed by a bottom-up phase combining remaining atoms with the maximal set.
procedure Hybrid(S)
    Input: S, a set of sublattice atoms sorted in descending order of support
    Output: Long maximal frequent itemsets and remaining frequent itemsets
    R = A_1
    S_1 = {A_1}
    for each atom A_i in S with i > 1 do
        R_cand = R union A_i
        L(R_cand) = L(R) intersection L(A_i)
        if |L(R_cand)| >= min_sup then
            R = R_cand
            L(R) = L(R_cand)
            S_1 = S_1 union {A_i}
            Record R as frequent
        else
            break
        end if
    end for
    S_2 = S \ S_1
    for each atom B_i in S_2 do
        T_i = { X_j | sigma(X_j) >= min_sup, L(X_j) = L(B_i) intersection L(A_j), for all A_j in S_1 }
        S_1 = S_1 union {B_i}
        if T_i is not empty then
            Bottom-Up(T_i)
        end if
    end for
end procedure
Knowl 6 — Top-Down Sublattice Itemset Search
algorithm
The top-down search targets the discovery of maximal frequent itemsets within a sublattice $S$ without computing supports for all intermediate subsets. It begins by testing the top element $R = \bigcup \{A_i \in S\}$ via a $k$ -way tid-list intersection. If $R$ is frequent, the sublattice search terminates. If $R$ is infrequent, it recursively evaluates all $(|R|-1)$ -subsets of $R$ , using a global hash table $HT$ of known infrequent itemsets to prune redundant branches.
procedure Top-Down(S)
    Input: S, a set of sublattice atoms; global hash table HT of infrequent itemsets
    Output: Maximal frequent itemsets in the sublattice
    R = Union of all A_i in S
    if R is not in HT then
        L(R) = Intersection of L(A_i) for all A_i in S
        if |L(R)| >= min_sup then
            Record R as frequent
        else
            for all Y subset of R with |Y| = |R| - 1 do
                if Y is not in HT then
                    Top-Down({ A_j | A_j subset of Y })
                    if sigma(Y) < min_sup then
                        HT = HT union {Y}
                    end if
                end if
            end for
        end if
    end if
end procedure
Knowl 7 — Weak Maximal Clique Formulation for Dense Association Graphs
model/method
When association graphs $G_k$ are dense (such as under low support thresholds or large transaction sizes), maximal clique enumeration can produce large, heavily overlapping cliques, resulting in high clique generation time and redundant itemset checks across sublattices. To control clique overlap, two cliques $X$ and $Y$ are defined as $\alpha$ -related if: $\frac{|X \cap Y|}{|X \cup Y|} \ge \alpha$ where $\alpha \in [0, 1]$ is a user-specified overlap threshold.

If two cliques $X$ and $Y$ are $\alpha$ -related, they are collapsed into a single weak maximal clique $Z = X \cup Y$ . A setting of $\alpha = 1.0$ generates standard maximal cliques, while $\alpha = 0.0$ collapses all connected components into a single clique. A value of $\alpha = 0.5$ avoids most redundant cliques while preserving the compact sublattice structure.
Knowl 8 — On-The-Fly Vertical-to-Horizontal Inversion for Pairwise Support Counting
model/method
Computing frequent 2-itemsets $\mathcal{F}_2$ directly from vertical tid-lists of frequent items $\mathcal{F}_1$ requires $\binom{|\mathcal{F}_1|}{2}$ pairwise disk-list intersections, reading approximately $\frac{|\mathcal{F}_1|}{2}$ database scans of data. To avoid this overhead, the database is inverted on-the-fly from vertical tid-lists into horizontal transaction blocks:
1. For each frequent item $i \in \mathcal{F}_1$ , its tid-list $\mathcal{L}(i)$ is read into memory.
2. For every transaction identifier $t \in \mathcal{L}(i)$ , item $i$ is appended to an in-memory transaction buffer array indexed by $t$ .
3. Memory is bounded by processing a block of transactions at a time.
4. Candidate 2-itemset support counts are incremented directly in a two-dimensional upper-triangular array by enumerating all item pairs within each recovered horizontal transaction in the block.
This single-pass inversion enables $\mathcal{F}_2$ computation with minimal overhead, after which vertical tid-list processing resumes for sublattices of size $k \ge 3$ .
Knowl 9 — Complexity and Bounded-Arboricity Linear Time Complexity for Frequent Itemsets
theoretical result
Let a transaction database be modeled as a bipartite graph $G = (U, V, E)$ , where $U = \mathcal{I}$ is the set of items, $V = \mathcal{D}$ is the set of transaction identifiers, and $(u, v) \in E$ denotes that transaction $v$ contains item $u$ . A complete bipartite subgraph $K_{i, t} = I \times T$ with $I \subseteq U, T \subseteq V, |I| = i, |T| = t$ corresponds to an itemset $I$ of size $i$ with support $t$ .
1. Determining whether a bipartite graph $G$ contains a balanced bipartite clique $K_{k, k}$ (or a constrained clique $K_{i, t}$ with $t \ge \text{min\_sup}$ ) is NP-complete.
2. Counting the number of maximal bipartite cliques in a bipartite graph is #P-complete.
3. For sparse bipartite graphs of bounded arboricity $i$ (where arboricity $r(G) = \max_{H \subseteq G} \frac{e(H)}{n(H) - 1} \approx i$ is bounded by the maximum transaction size or maximum frequent itemset size), all maximal bipartite cliques can be enumerated in time: $O(i^3 \cdot 2^{2i} \cdot (|U| + |V|))$
This proves that frequent itemset mining scales linearly in the number of database transactions $|V|$ and the number of items $|U|$ whenever transaction sizes are bounded.
Knowl 10 — Empirical Performance and Memory Footprint of Eclat and MaxClique
empirical result
Benchmarking of the vertical lattice algorithms (Eclat, MaxEclat, Clique, MaxClique, TopDown, AprClique) against horizontal algorithms (Apriori and Partition with 3 and 10 partitions) across synthetic retail datasets (such as T10.I4.D400K, T20.I8.D400K, T20.I12.D400K, and T30.I16.D400K) shows the following:
- Eclat is typically more than an order of magnitude faster than Apriori and 2x to 4x faster than Partition because it eliminates candidate hash trees and multi-pass dataset scanning.
- MaxClique delivers the highest overall performance, outperforming Apriori by a factor of 20x to 30x on dense datasets, and outperforming Eclat by up to a factor of 10x on long patterns.
- On dense datasets with long patterns (e.g., T30.I16.D400K at 0.75% support), MaxClique completed in 69 seconds whereas Apriori required 22,963 seconds (a 332x speedup) and Partition ran out of virtual memory.
- At 0.5% support on T30.I16 (where the longest frequent itemset has size 22 and there are 13,480,771 frequent itemsets), pure bottom-up algorithms fail due to enumerating $\ge 2^{22}$ candidate subsets, while MaxClique succeeded by performing only 197,601 intersections.
- All vertical lattice algorithms demonstrate linear scaling with database size as transactions increase from 100,000 to 5,000,000, while maintaining a mean tid-list memory footprint under 0.018 MB (<2% of the database size).

Coverage note — Omitted the theoretical Zarankiewicz number bounds (Theorem 5) and output-polynomial maximum independent set listing (Theorem 4) from Appendix A, as they provide general theoretical upper bounds on extremal graphs rather than algorithmic mechanisms used in the proposed association mining methods.

References

1.R. Agrawal, T. Imielinski, and A. Swami, "Mining Association Rules Between Sets of Items in Large Databases," ACM SIGMOD Conf. Management of Data, May 1993.
2.R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. Inkeri Verkamo, "Fast Discovery of Association Rules," Advances in Knowledge Discovery and Data Mining, U. Fayyad and et al., eds., pp. 307-328, Menlo Park, Calif.: AAAI Press, 1996.
3.R. Agrawal and J. Shafer, "Parallel Mining of Association Rules," IEEE Trans. Knowledge and Data Eng., vol. 8, no. 6, pp. 962-969, Dec. 1996.
4.R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules," Proc. 20th Very Large Data Base Conf., Sept. 1994.
5.R.J. Bayardo, "Efficiently Mining Long Patterns From Databases," ACM SIGMOD Conf. Management of Data, June 1998.
6.S. Brin, R. Motwani, J. Ullman, and S. Tsur, "Dynamic Itemset Counting and Implication Rules for Market Basket Data," ACM SIGMOD Conf. Management of Data, May 1997.
7.D. Cheung, J. Han, V. Ng, A. Fu, and Y. Fu, "A Fast Distributed Algorithm for Mining Association Rules," Fourth Int'l Conf. Parallel and Distributed Information Systems, Dec. 1996.
8.B.A. Davey and H.A. Priestley, Introduction to Lattices and Order. Cambridge Univ. Press, 1990.
9.D. Eppstein, "Arboricity and Bipartite Subgraph Listing Algorithms," Information Processing Letters, vol. 51, pp. 207-211, 1994.
10.M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
11.D. Gunopulos, R. Khardon, H. Mannila, and H. Toivonen, "Data Mining, Hypergraph Transversals, and Machine Learning," Proc. 16th ACM Symp. Principles of Database Systems, May 1997.
12.D. Gunopulos, H. Mannila, and S. Saluja, "Discovering All the Most Specific Sentences by Randomized Algorithms," Int'l Conf. Database Theory, Jan. 1997.
13.E.-H. Han, G. Karypis, and V. Kumar, "Scalable Parallel Data Mining for Association Rules," ACM SIGMOD Conf. Management of Data, May 1997.
14.M. Holsheimer, M. Kersten, H. Mannila, and H. Toivonen, "A Perspective on Databases and Data Mining," First Int'l Conf. Knowledge Discovery and Data Mining, Aug. 1995.
15.M. Houtsma and A. Swami, "Set-Oriented Mining of Association Rules in Relational Databases," 11th Int'l Conf. Data Eng., 1995.
16.T. Kashiwabara, S. Masuda, K. Nakajima, and T. Fujisawa, "Generation of Maximum Independent Sets of a Bipartite Graph and Maximum Cliques of a Circular-Arc Graph," J. Algorithms, vol. 13, pp. 161-174, 1992.
17.S.O. Kuznetsov, "Interpretation on Graphs and Complexity Characteristics of a Search for Specific Patterns," Nauchn. Tekh. Inf., Ser. 2 (Automatic Document Math Linguist), vol. 23, no. 1, pp. 23-37, 1989.
18.L.E. LaForge, "Some Zarankiewicz Numbers," Technical Report SOCS-94. Z, McGill Univ., July 1994.
19.D.-I. Lin and Z.M. Kedem, "Pincer-Search: A New Algorithm for Discovering the Maximum Frequent Set," Sixth Int'l Conf. Extending Database Technology, Mar. 1998.
20.J.-L. Lin and M.H. Dunham, "Mining Association Rules: Anti-Skew Algorithms," 14th Int'l Conf. Data Eng., Feb. 1998.
21.A. Mueller, "Fast Sequential and Parallel Algorithms for Association Rule Mining: A Comparison," Technical Report CS-TR-3515, Univ. of Maryland, College Park, Aug. 1995.
22.G.D. Mulligan and D.G. Corneil, "Corrections to Bierstone's Algorithm for Generating Cliques," J. ACM, vol. 19, no. 2, pp. 244-247, 1972.
23.J.S. Park, M. Chen, and P.S. Yu, "An Effective Hash Based Algorithm for Mining Association Rules," ACM SIGMOD Int'l Conf. Management of Data, May 1995.
24.S. Parthasarathy, M.J. Zaki, and W. Li, "Memory Placement Techniques for Parallel Association Mining," Fourth Int'l Conf. Knowledge Discovery and Data Mining, Aug. 1998.
25.S. Sarawagi, S. Thomas, and R. Agrawal, "Integrating Association Rule Mining with Databases: Alternatives and Implications," ACM SIGMOD Int'l Conf. Management of Data, June 1998.
26.A. Savasere, E. Omiecinski, and S. Navathe, "An Efficient Algorithm for Mining Association Rules in Large Databases," Proc. 21st Very Large Data Bases Conf., 1995.
27.H. Toivonen, "Sampling Large Databases for Association Rules," Proc. 22nd Very Large Data Bases Conf., 1996.
28.S.-J. Yen and A.L.P. Chen, "An Efficient Approach to Discovering Knowledge from Large Databases," Fourth Int'l Conf. Parallel and Distributed Information Systems, Dec. 1996.
29.M.J. Zaki, S. Parthasarathy, W. Li, and M. Ogihara, "Evaluation of Sampling for Data Mining of Association Rules," Seventh Int'l Workshop on Research Issues in Data Eng., Apr. 1997.
30.M.J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li, "New Algorithms for Fast Discovery of Association Rules," Third Int'l Conf. Knowledge Discovery and Data Mining, Aug. 1997.
31.M.J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li, "Parallel Algorithms for Fast Discovery of Association Rules," Data Mining and Knowledge Discovery: An Int'l Journal, vol. 1, no. 4, pp. 343-373, Dec. 1997.

Citation

MLA

Zaki, M. J. “Scalable Algorithms for Association Mining”. IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 3, 2000, pp. 372–90, https://doi.org/10.1109/69.846291.

APA

Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390. https://doi.org/10.1109/69.846291

Chicago

Zaki, M. J. 2000. “Scalable Algorithms for Association Mining”. IEEE Transactions on Knowledge and Data Engineering 12 (3): 372–90. https://doi.org/10.1109/69.846291.

Harvard

Zaki, M.J. (2000) “Scalable algorithms for association mining”, IEEE Transactions on Knowledge and Data Engineering, 12(3), pp. 372–390. Available at: https://doi.org/10.1109/69.846291.

Vancouver

1. Zaki MJ (2000) Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering 12:372–390

BibTeX

@article{Zaki_2000, title={Scalable algorithms for association mining}, volume={12}, ISSN={1041-4347}, url={http://dx.doi.org/10.1109/69.846291}, DOI={10.1109/69.846291}, number={3}, journal={IEEE Transactions on Knowledge and Data Engineering}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Zaki, M.J.}, year={2000}, pages={372–390} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

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

Open PDF

Scalable Algorithms for Association Mining

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Support Counting via Vertical Tid-List Intersections

Knowl 2 — Prefix-Based Lattice Decomposition via Equivalence Relation Theta-k

Knowl 3 — Maximal-Clique-Based Lattice Decomposition via Pseudoequivalence Relation Phi-k

Knowl 4 — Bottom-Up Sublattice Itemset Search

Knowl 5 — Hybrid Sublattice Itemset Search

Knowl 6 — Top-Down Sublattice Itemset Search

Knowl 7 — Weak Maximal Clique Formulation for Dense Association Graphs

Knowl 8 — On-The-Fly Vertical-to-Horizontal Inversion for Pairwise Support Counting

Knowl 9 — Complexity and Bounded-Arboricity Linear Time Complexity for Frequent Itemsets

Knowl 10 — Empirical Performance and Memory Footprint of Eclat and MaxClique

References

Citation

BibTeX

Source Code

Access the Paper