|
|
|
     |
                         |
Return to Research Sessions
In a vertical representation of a market-basket database, each item is associated with a column of values representing the transactions in which it is present. The association-rule mining algorithms that have been recently proposed for this representation show performance improvements over their classical horizontal counterparts, but are either efficient only for certain database sizes, or assume particular characteristics of the database contents, or are applicable only to specific kinds of database schemas. We present here a new vertical mining algorithm called VIPER, which is general-purpose, making no special requirements of the underlying database. VIPER stores data in compressed bit-vectors called "snakes" and integrates a number of novel optimizations for efficient snake generation, intersection, counting and storage. We analyze the performance of VIPER for a range of synthetic database workloads. Our experimental results indicate significant performance gains, especially for large databases, over previously proposed vertical and horizontal mining algorithms. In fact, there are even workload regions where VIPER outperforms an optimal, but practically infeasible, horizontal mining algorithm.
Note: References link to DBLP on the Web.
@inproceedings{ author = {Pradeep Shenoy and Jayant R. Haritsa and S. Sudarshan and Gaurav Bhalotia and Mayank Bawa and Devavrat Shah}, editor = {Weidong Chen and Jeffrey F. Naughton and Philip A. Bernstein}, title = {Turbo-charging Vertical Mining of Large Databases}, booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, May 16-18, 2000, Dallas, Texas, USA}, journal = {SIGMOD Record}, publisher = {ACM}, volume = {29}, number = {2}, year = {2000}, isbn = {1-58113-218-2}, pages = {22-33}, crossref = {DBLP:conf/sigmod/2000}, bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc. |
