Finding Frequent Itemsets

Description

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

Parameters

$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

Space Complexity Graph

Time-Space Tradeoff