sigmod_1998_elementary.txt

利用lwp：：get写的

<proceedings><paper><title>Query flocks: a generalization of association-rule mining</title><author><AuthorName>Dick Tsur</AuthorName><institute><InstituteName>Hitachi Corp.</InstituteName><country></country></institute></author><author><AuthorName>Jeffrey D. Ullman</AuthorName><institute><InstituteName>Stanford University</InstituteName><country></country></institute></author><author><AuthorName>Serge Abiteboul</AuthorName><institute><InstituteName>Stanford University and INRIA</InstituteName><country></country></institute></author><author><AuthorName>Chris Clifton</AuthorName><institute><InstituteName>MITRE Corp.</InstituteName><country></country></institute></author><author><AuthorName>Rajeev Motwani</AuthorName><institute><InstituteName>Stanford University</InstituteName><country></country></institute></author><author><AuthorName>Svetlozar Nestorov</AuthorName><institute><InstituteName>Stanford University</InstituteName><country></country></institute></author><author><AuthorName>Arnon Rosenthal</AuthorName><institute><InstituteName>MITRE Corp.</InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Management of Data</conference><citation><name>Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995</name><name>Rakesh Agrawal , Tomasz Imieli&amp;#324;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</name><name>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</name><name>Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States</name><name>P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts</name><name>A. Gupta, V. Harinarayan, and D. Quass, Generalized projections, a powerful approach to aggregation, Proc. 21st VLDB Conf., 1995o</name><name>Maurice A. W. Houtsma , Arun N. Swami, Set-Oriented Mining for Association Rules in Relational Databases, Proceedings of the Eleventh International Conference on Data Engineering, p.25-33, March 06-10, 1995</name><name>Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982</name><name>Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993</name><name>Heikki Mannila, Methods and Problems in Data Mining, Proceedings of the 6th International Conference on Database Theory, p.41-55, January 08-10, 1997</name><name>Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988</name><name>Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988</name><name>Jeffrey D. Ullman , Jennifer Widom, A first course in database systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997</name><name>X. Zhang and M. Z. Ozsoyoglu [1993]. "On efficient reasoning with implication constraints," Proc. Third DOOD Conf., pp. 236-252, 1993.</name></citation><abstract>Association-rule mining has proved a highly successful technique for extracting useful information from very large databases. This success is attributed not only to the appropriateness of the objectives, but to the fact that a number of new query-optimization ideas, such as the &amp;ldquo;a-priori&amp;rdquo; trick, make association-rule mining run much faster than might be expected. In this paper we see that the same tricks can be extended to a much more general context, allowing efficient mining of very large databases for many different kinds of patterns. The general idea, called &amp;ldquo;query flocks,&amp;rdquo; is a generate-and-test model for data-mining problems. We show how the idea can be used either in a general-purpose mining system or in a next generation of conventional query optimizers.</abstract></paper><paper><title>Exploratory mining and pruning optimizations of constrained associations rules</title><author><AuthorName>Raymond T. Ng</AuthorName><institute><InstituteName>University of British Columbia</InstituteName><country></country></institute></author><author><AuthorName>Laks V. S. Lakshmanan</AuthorName><institute><InstituteName>Concordia University</InstituteName><country></country></institute></author><author><AuthorName>Jiawei Han</AuthorName><institute><InstituteName>Simon Fraser University</InstituteName><country></country></institute></author><author><AuthorName>Alex Pang</AuthorName><institute><InstituteName>University of British Columbia</InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Management of Data</conference><citation><name>Rakesh Agrawal , Tomasz Imieli&amp;#324;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</name><name>Rakesh Agrawal , John C. Shafer, Parallel Mining of Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.962-969, December 1996</name><name>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</name><name>Elena Baralis , Giuseppe Psaila, Designing Templates for Mining Association Rules, Journal of Intelligent Information Systems, v.9 n.1, p.7-32, July/Aug. 1997</name><name>Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States</name><name>David Wai-Lok Cheung , Jiawei Han , Vincent Ng , C. Y. Wong, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique, Proceedings of the Twelfth International Conference on Data Engineering, p.106-114, February 26-March 01, 1996</name><name>Takeshi Fukuda , Yasukiko Morimoto , Shinichi Morishita , Takeshi Tokuyama, Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.13-23, June 04-06, 1996, Montreal, Quebec, Canada</name><name>Eui-Hong Han , George Karypis , Vipin Kumar, Scalable parallel data mining for association rules, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.277-288, May 11-15, 1997, Tucson, Arizona, United States</name><name>Jiawei Han , Yongjian Fu, Discovery of Multiple-Level Association Rules from Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.420-431, September 11-15, 1995</name><name>Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States</name><name>Tomasz Imielinski , Heikki Mannila, A database perspective on knowledge discovery, Communications of the ACM, v.39 n.11, p.58-64, Nov. 1996</name><name>M. Kamber, J. Hail, and J. Y. Chiang. Metarule-guided mining of multi-dimensional association rules using data cubes. KDD 97, pp 207-210.</name><name>Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen , A. Inkeri Verkamo, Finding interesting rules from large sets of discovered association rules, Proceedings of the third international conference on Information and knowledge management, p.401-407, November 29-December 02, 1994, Gaithersburg, Maryland, United States</name><name>Brian Lent , Arun N. Swami , Jennifer Widom, Clustering Association Rules, Proceedings of the Thirteenth International Conference on Data Engineering, p.220-231, April 07-11, 1997</name><name>Rosa Meo , Giuseppe Psaila , Stefano Ceri, A New SQL-like Operator for Mining Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.122-133, September 03-06, 1996</name><name>R. J. Miller , Y. Yang, Association rules over interval data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.452-461, May 11-15, 1997, Tucson, Arizona, United States</name><name>Raymond T. Ng, Laks V.S. Lakshmanan, Jiawei Han, and Alex Pang. Exploratory Mining and Optimization of Constrained Association Queries. Technical Report, University of British Columbia and Concordia University, October 1997.</name><name>Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States</name><name>Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995</name><name>Avi Silberschatz , Stan Zdonik, Database systems&amp;mdash;breaking out of the box, ACM SIGMOD Record, v.26 n.3, p.36-50, Sept. 1997</name><name>Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995</name><name>Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada</name><name>R. Srikant, Q. Vu and R. Agrawal. Mining association rules with item constraints. KDD 97, pp 67-73.</name><name>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</name><name>D. Tsur, J. D. Ullman, S. Abitboul, C. Clifton, R. Motwani, and S. Nestorov. Query flocks: A generalization of association-rule mining, http://wwwdb.stanford.edu/,.,ullrnan/pub/qflocks.ps, 1-20, Oct. 1997.</name></citation><abstract>From the standpoint of supporting human-centered discovery of knowledge, the present-day model of mining association rules suffers from the following serious shortcomings: (i) lack of user exploration and control, (ii) lack of focus, and (iii) rigid notion of relationships. In effect, this model functions as a black-box, admitting little user interaction in between. We propose, in this paper, an architecture that opens up the black-box, and supports constraint-based, human-centered exploratory mining of associations. The foundation of this architecture is a rich set of constraint constructs, including domain, class, and SQL-style aggregate constraints, which enable users to clearly specify what associations are to be mined. We propose constrained association queries as a means of specifying the constraints to be satisfied by the antecedent and consequent of a mined association.
In this paper, we mainly focus on the technical challenges in guaranteeing a level of performance that is commensurate with the selectivities of the constraints in an association query. To this end, we introduce and analyze two properties of constraints that are critical to pruning: anti-monotonicity and succinctness. We then develop characterizations of various constraints into four categories, according to these properties. Finally, we describe a mining algorithm called CAP, which achieves a maximized degree of pruning for all categories of constraints. Experimental results indicate that CAP can run much faster, in some cases as much as 80 times, than several basic algorithms. This demonstrates how important the succinctness and anti-monotonicity properties are, in delivering the performance guarantee.</abstract></paper><paper><title>Parallel mining algorithms for generalized association rules with classification hierarchy</title><author><AuthorName>Takahiko Shintani</AuthorName><institute><InstituteName>Institute of Industrial Science, The University of Tokyo</InstituteName><country></country></institute></author><author><AuthorName>Masaru Kitsuregawa</AuthorName><institute><InstituteName>Institute of Industrial Science, The University of Tokyo</InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Management of Data</conference><citation><name>Rakesh Agrawal , John C. Shafer, Parallel Mining of Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.962-969, December 1996</name><name>David W. Cheung , Jiawei Han , Vincent T. Ng , Ada W. Fu , Yongjian Fu, A fast distributed algorithm for mining association rules, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.31-43, December 18-20, 1996, Miami Beach, Florida, United States</name><name>David W. Cheung , Vincent T. Ng , Ada W. Fu , Yongjian Fu, Efficient Mining of Association Rules in Distributed Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.911-922, December 1996</name><name>Eui-Hong Han , George Karypis , Vipin Kumar, Scalable parallel data mining for association rules, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.277-288, May 11-15, 1997, Tucson, Arizona, United States</name><name>Jong Soo Park , Ming-Syan Chen , Philip S. Yu, Efficient parallel data mining for association rules, Proceedings of the fourth international conference on Information and knowledge management, p.31-36, November 29-December 02, 1995, Baltimore, Maryland, United States</name><name>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</name><name>Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995</name><name>Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996</name><name>Takahiko Shintani , Masaru Kitsuregawa, Hash based parallel algorithms for mining association rules, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.19-30, December 18-20, 1996, Miami Beach, Florida, United States</name><name>Takahiko Shintani , Masaru Kitsuregawa, Mining Algorithms for Sequential Patterns in Parallel: Hash Based Approach, Proceedings of the Second Pacific-Asia Conference on Research and Development in Knowledge Discovery and Data Mining, p.283-294, April 15-17, 1998</name></citation><abstract>Association rule mining recently attracted strong attention. Usually, the classification hierarchy over the data items is available. Users are interested in generalized association rules that span different levels of the hierarchy, since sometimes more interesting rules can be derived by taking the hierarchy into account.