Efficient data reduction with EASE

ABSTRACT

A variety of mining and analysis problems --- ranging from association-rule discovery to contingency table analysis to materialization of certain approximate datacubes --- involve the extraction of knowledge from a set of categorical count data. Such data can be viewed as a collection of "transactions," where a transaction is a fixed-length vector of counts. Classical algorithms for solving count-data problems require one or more computationally intensive passes over the entire database and can be prohibitively slow. One effective method for dealing with this ever-worsening scalability problem is to run the algorithms on a small sample of the data. We present a new data-reduction algorithm, called EASE, for producing such a sample. Like the FAST algorithm introduced by Chen et al., EASE is especially designed for count data applications. Both EASE and FAST take a relatively large initial random sample and then deterministically produce a subsample whose "distance" --- appropriately defined --- from the complete database is minimal. Unlike FAST, which obtains the final subsample by quasi-greedy descent, EASE uses epsilon-approximation methods to obtain the final subsample by a process of repeated halving. Experiments both in the context of association rule mining and classical χ² contingency-table analysis show that EASE outperforms both FAST and simple random sampling, sometimes dramatically.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: N. Alon and J. H. Spencer. The probabilistic method. Wiley Interscience, New York, 1992.
• 4: Hervé Brönnimann , Bernard Chazelle , Jiri Matousek, Product Range Spaces, Sensitive Sampling, and Derandomization, SIAM Journal on Computing, v.28 n.5, p.1552-1575, April/May 1999 [doi>10.1137/S0097539796260321]
• 5: H. Bronnimann, B. Chen, M. Dash, and P. Haas, P. Scheuermann. Efficient data reduction method for on-line association rule discovery. In Proceedings of NSF Workshop on New Generation of Data Mining, 2002.
• 6: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 7: Bin Chen , Peter Haas , Peter Scheuermann, A new two-phase sampling based algorithm for discovering association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775114]
• 8: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 9: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 10: G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proceedings of International Conference on Very Large Databases (VLDB), 2002.
• 11: Jiří Matoušek, Derandomization in computational geometry, Journal of Algorithms, v.20 n.3, p.545-580, May 1996 [doi>10.1006/jagm.1996.0027]
• 12: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 13: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 14: Mohammed J Zaki , Srinivasan Parthasarathy , Wei Li , Mitsunori Ogihara, Evaluation of Sampling for Data Mining of Association Rules, University of Rochester, Rochester, NY, 1996

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Keywords:
OLAP, association rules, count dataset, data streams, frequency estimation, sampling