dm.cs.tu-dortmund.de/en/mlbits/frequent-pattern-acceleration/
Scaling Frequent Itemset Mining – Lecture Notes
unbearably slow
Finding 2-itemsets
We will first focus on 2-itemsets only!
if we have \(M=|F_1|\leq |I|\) frequent 1-itemsets, we need to count \(|C_2|=M^2\) pairs
for triples, we usually do not have to count [...] products (e.g., Walmart), and want to count all pairs:
Triangular matrix : \(n\cdot (n-1)/2\) cells, 4 bytes each
⇝ \(n(n-1)/2\cdot 4 \approx 2\cdot 10^{10} = 20\) GB RAM
Sparse matrix : store only non-zero [...] a sparse matrix)
Compress the hash table to a bitmask after the first pass, reduces memory usage to 1/32.
The basic idea can also be found in Bloom filters for databases [ Bloo70 ] .
Improvements: MultiStage …
