Sampling Large Databases for Association Rules
Hannu T. T. Toivonen · 1996
Discovery of association rules.is an import-ant database mining problem. Current al-gorithms for finding association rules require several passes over the analyzed database, and obviously the role of I/O overhead is very sig-nificant for very large databases. We present new algorithms that reduce the database activ-ity considerably. The idea is to pick a Random sample, to find using this sample all associ-ation rules that probably hold in the whole database, and then to verify the results with the rest of the database. The algorithms thus produce exact association rules, not approx-imations based on a sample. The approach is, however, probabilistic, and in those rare cases where our sampling method does not produce all association rules, the missing rules can be found in a second pass. Our experiments show that the proposed algorithms can find associ-ation rules very efficiently in only one database Pa= 1