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
Cited by 1,067 works.
Authors
References
- Mining association rules between sets of items in large databases
- Fast Algorithms for Mining Association Rules in Large Databases
- Knowledge Discovery in Databases
- The Probabilistic Method
- Fast discovery of association rules
- An effective hash-based algorithm for mining association rules
- Mining generalized association rules
- An Efficient Algorithm for Mining Association Rules in Large Databases
- Efficient algorithms for discovering association rules
- Discovery of Multiple-Level Association Rules from Large Databases