Online Association Rule Mining

Christian Hidber

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-98-1004
May 1998

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/CSD-98-1004.pdf

We present a novel algorithm to compute large itemsets online. It needs at most two scans of the transaction sequence. Any time during the first scan, the user is free to change the support threshold. The algorithm maintains a superset of all large itemsets and a deterministic lower and upper bound on the support of each itemset. We continously display the resulting association rules along with an interval on the rule's support and confidence. The algorithm can compute association rules for a transaction sequence which is read from a network and is too large to be stored locally for a rescan. During the second scan we determine the precise support for each large itemset and prune all small itemsets using a new forward-pruning technique.


BibTeX citation:

@techreport{Hidber:CSD-98-1004,
    Author = {Hidber, Christian},
    Title = {Online Association Rule Mining},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1998},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/5677.html},
    Number = {UCB/CSD-98-1004},
    Abstract = {We present a novel algorithm to compute large itemsets online. It needs at most two scans of the transaction sequence. Any time during the first scan, the user is free to change the support threshold. The algorithm maintains a superset of all large itemsets and a deterministic lower and upper bound on the support of each itemset. We continously display the resulting association rules along with an interval on the rule's support and confidence. The algorithm can compute association rules for a transaction sequence which is read from a network and is too large to be stored locally for a rescan.  During the second scan we determine the precise support for each large itemset and prune all small itemsets using a new forward-pruning technique.}
}

EndNote citation:

%0 Report
%A Hidber, Christian
%T Online Association Rule Mining
%I EECS Department, University of California, Berkeley
%D 1998
%@ UCB/CSD-98-1004
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1998/5677.html
%F Hidber:CSD-98-1004