Skip to content
Back to search results

ECLAT Frequent-Itemset Mining

Introduced by
Mohammed J. Zaki
Year
2000
Type
Frequent-itemset mining algorithm (vertical format)
Family
Pattern mining
Font size

What does it do?

ECLAT, introduced by Mohammed Zaki in 2000, mines frequent itemsets using a vertical data representation: instead of scanning transactions, it stores for each item the set of transaction IDs (a tidset) that contain it, and computes the support of any itemset by intersecting tidsets.

This depth-first, intersection-based approach is fast and memory-efficient, an alternative to Apriori's horizontal scans and FP-Growth's tree.

The intuition behind the method

Most itemset miners think row by row: which items are in each transaction? ECLAT flips the table on its side. For every item it keeps a list of the transactions that contain it. Now the support of a pair of items is just the size of the overlap of their two lists — a simple set intersection — and you never rescan the database. To find longer frequent itemsets, intersect the lists of shorter ones. Walking this depth-first and pruning whenever an intersection gets too small efficiently enumerates all frequent itemsets.

History

Mohammed Zaki introduced ECLAT and the vertical mining paradigm in work culminating in his 2000 IEEE TKDE paper on scalable association mining, later refining it with diffsets (dECLAT). It joined Apriori (1994, horizontal candidate generation) and FP-Growth (2000, tree-based) as one of the three canonical families of frequent-itemset algorithms, each trading off scans, memory, and data density differently. ECLAT remains a standard option in data-mining toolkits.

When to use it

Use ECLAT for frequent-itemset mining when a vertical, intersection-based approach suits the data — it is often very fast on dense datasets and avoids repeated database scans, making it a strong alternative to Apriori and a peer to FP-Growth. It shines when tidsets are moderate in size and fit in memory, and the diffset variant handles dense data well. Its costs: tidsets for frequent items can be large and memory-heavy on big sparse datasets, intermediate intersections add overhead, and like all support-based mining it is sensitive to the minimum-support threshold. As always, frequent itemsets are only the first stage; association rules with confidence/lift are generated afterward. Choose among ECLAT, FP-Growth, and Apriori based on data density and memory.

Limitations and considerations

  • Tidsets for frequent items can be large, costing memory on big datasets.
  • Intermediate intersection results add memory/time overhead.
  • Less intuitive than horizontal (Apriori) representations.
  • Sensitive to the minimum-support threshold, like all itemset mining.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Support computed by fast tidset intersections — no repeated database scans.
  • Depth-first search with prefix equivalence classes reuses work and localizes memory.
  • Often very efficient on dense datasets, competitive with FP-Growth.
  • The diffset optimization further reduces memory and intersection cost.

Applications

  • Market-basket and retail association mining.
  • Web and clickstream co-occurrence analysis.
  • Bioinformatics frequent co-occurrence discovery.
  • Any frequent-itemset task favouring a vertical, intersection-based approach.
  • Dense transactional datasets where diffset ECLAT excels.

How it works

How it works

1

The database is transformed once into vertical format: each item maps to its tidset, the set of transaction IDs in which it appears. This is the key data structure — all subsequent work is set operations on tidsets, not passes over the original transactions.

Formula
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

The support of an itemset is the cardinality of the intersection of its items' tidsets — the number of transactions containing all of them. Counting becomes intersecting, which is fast, and frequent single items (those whose tidset is large enough) seed the search.

Formula
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

Itemsets are extended by intersecting tidsets: the tidset of X ∪ {y} is the intersection of the tidsets of X and {y}. ECLAT explores the itemset lattice depth-first within equivalence classes (itemsets sharing a prefix), so intersections are reused and the search stays local.

Formula
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

An extension is kept only if its tidset (hence support) meets the minimum-support threshold; otherwise that branch is pruned (anti-monotonicity: no superset can be frequent). Diffsets — storing only the differences between tidsets — are a common optimization that further shrinks memory and intersection cost.

Formula
\text{keep extensions with } \text{support} \ge \text{minsup}

Common pitfalls

  • Mining very large sparse data where tidsets blow up memory — consider diffsets or FP-Growth.
  • Setting minimum support too low and producing an unmanageable number of itemsets.
  • Confusing frequent itemsets with association rules (rules are a separate step).
  • Ignoring the diffset variant on dense data where it greatly helps.

Frequently asked questions

How does ECLAT differ from Apriori and FP-Growth?

All three find frequent itemsets. Apriori uses a horizontal format with candidate generation and many scans; FP-Growth compresses data into a tree and mines recursively; ECLAT uses a vertical tidset format and computes support by intersecting transaction-ID lists depth-first. ECLAT and FP-Growth avoid Apriori's repeated scans.

What is a tidset?

A tidset (transaction-ID set) is the list of transactions that contain a given item or itemset. ECLAT stores these vertically and computes an itemset's support as the size of the intersection of its items' tidsets, turning counting into set intersection.

What are diffsets?

Diffsets store only the difference between an itemset's tidset and its parent's, rather than the full tidset. On dense data this drastically reduces memory and intersection cost, giving the dECLAT variant a substantial efficiency advantage.

Related methods

Sources

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    Open DOI reference
    Copied.