Finding Frequent Itemsets (Finding Frequent Itemsets)

From Algorithm Wiki
Revision as of 09:09, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


We assume there is a number $s$, called the support threshold. If $I$ is a set of items, the support for $I$ is the number of baskets for which $I$ is a subset. We say $I$ is frequent if its support is $s$ or more


$n$: total number of transactions (size of database)

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
A-Priori algorithm 1994 $O(n^{2})$ $O(n^{2})$ Exact Deterministic Time & Space
The Algorithm of Park; Chen; and Yu (PCY) 1995 $O(n^{2})$ $O(n^{2})$ Exact Deterministic Time
The Multistage Algorithm 1999 $O(n^{2})$ $O(n^{2})$ Exact Deterministic Time
The Multihash Algorithm 1999 $O(n^{2})$ $O(n^{2})$ Exact Deterministic Time

Time Complexity Graph

Finding Frequent Itemsets - Time.png