Data mining, hypergraph transversals, and machine learning (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Data mining, hypergraph transversals, and machine learning (extended abstract)

Full text

Pdf (1.50 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Tucson, Arizona, United States

Pages: 209 - 216

Year of Publication: 1997

ISBN:0-89791-910-6

Authors

Dimitrios Gunopulos	IBM Almaden RC K55/B1, 650 Harry Rd., San Jose, CA
Heikki Mannila	University of Helsinki, Department of Computer Science, P.O. Box 26, FIN-00014 Helsinki, Finland
Roni Khardon	Aiken Computation Laboratory, Harvard University, Cambridge, MA
Hannu Toivonen	University of Helsinki, Department of Computer Science, P.O. Box 26, FIN-00014 Helsinki, Finland

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 66, Citation Count: 44

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/263661.263684 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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 , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
	3	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	4	C. Berge. Hypergraphs. Combinatorics of Finite Sets. North-Holland Publishing Company, Amsterdam, 3rd edition, I973.
	5	Nader H. Bshouty , Richard Cleve , Ricard Gavaldà , Sampath Kannan , Christino Tamon, Oracles and queries that are sufficient for exact learning, Journal of Computer and System Sciences, v.52 n.3, p.421-433, June 1996 [doi>10.1006/jcss.1996.0032]
	6	L. De Itaedt and M. Bruynooghe. A theory of clausal discovery. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCA!-93), pages 1058- 1053, Chamb~ry, France, 1993. Morgan Kaufraann.
	7	Luc De Raedt , Sašo Džeroski, First-order jk-clausal theories are PAC-learnable, Artificial Intelligence, v.70 n.1-2, p.375-392, Oct. 1994 [doi>10.1016/0004-3702(94)90112-0]
	8	Thomas Eiter , Georg Gottlob, Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, v.24 n.6, p.1278-1304, Dec. 1995 [doi>10.1137/S0097539793250299]
	9	Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth, From data mining to knowledge discovery: an overview, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
	10	Michael L. Fredman , Leonid Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms, v.21 n.3, p.618-628, Nov. 1996 [doi>10.1006/jagm.1996.0062]
	11	Dimitrios Gunopulos , Heikki Mannila , Sanjeev Saluja, Discovering All Most Specific Sentences by Randomized Algorithms, Proceedings of the 6th International Conference on Database Theory, p.215-229, January 08-10, 1997
	12	It. Khaxdon. Translating between Horn representations and their characteristic models. Journal of AI Research, 3:349- 372, 1995.
	13	J.-U. Kietz and S. Wrobel. Controlling the complexity of learning in logic through syntactic and task-oriented models. In S. Muggleton, editor, Inductive Logic Programming, pages 335 - 359. Academic Press, London, 1992.
	14	W. Kloesgen. Efficient discovery of interesting statements in databases. Journal of Intelligent Information Systems, 4(1):53 - 69, 1995.
	15	Pat Langley, Elements of machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1995
	16	Heikki Mannila , Kari-Jouko Räihä, Design by exmple: An application of Armstrong relations, Journal of Computer and System Sciences, v.33 n.2, p.126-141, Oct. 1986 [doi>10.1016/0022-0000(86)90015-2]
	17	Heikki Mannila , Kari-Jouko Räihä, The design of relational databases, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
	18	Heikki Mannila , Kari-Jouko Räihä, Algorithms for inferring functional dependencies from relations, Data & Knowledge Engineering, v.12 n.1, p.83-99, Feb. 1994 [doi>10.1016/0169-023X(94)90023-X]
	19	H. Mannila and H. Toivonen. On an algorithm for finding all interesting sentences. In Cybernetics and Systems, Volume II, The Thirteenth European Meeting on Cybernetics and Systems Research, pages 973 - 978, Vienna, Austria, Apr. 1996. Extended version available as: Levehvise search and borders of theories in knowledge discovery, Report C-1997-8, University of Helsinld, Depaxtment of Computer Science.
	20	H. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for discovering association rules. In Knowledge Discovery in Databases, Papers from the 1994 AAAI Workshop (KDD'94), pages 181 - 192, Seattle, Washington, July 1994.
	21	H. Mannila, H. Toivonen, and A. I. Verkanao. Discovering frequent episodes in sequences. In Proceedings of the First International Conference on Knowledge Discovery and Data Mining (KDD'95), pages 210-- 215, Montreal, Canada, Aug. 1995.
	22	N. Misra and L. Pitt. On bounded-degree hypergraph transversals. Manuscript., 1995.
	23	T. M. Mitchell. Generalization as search. Artificial intelligence, 18:203 - 226, 1982.
	24	C. Tamon. Private communication. 1997.

CITED BY 44

	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, ACM SIGMOD Record, v.27 n.2, p.94-105, June 1998
	Thomas Eiter , Georg Gottlob , Kazuhisa Makino, New results on monotone dualization and generating hypergraph transversals, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States
	Mohammed J. Zaki , Neal Lesh , Mitsunori Ogihara, PlanMine: Predicting Plan Failures Using Sequence Mining, Artificial Intelligence Review, v.14 n.6, p.421-446, December 1, 2000
	Dimitrios Gunopulos , Roni Khardon , Heikki Mannila , Sanjeev Saluja , Hannu Toivonen , Ram Sewak Sharma, Discovering all most specific sentences, ACM Transactions on Database Systems (TODS), v.28 n.2, p.140-174, June 2003
	Mohammed J. Zaki, Scalable Algorithms for Association Mining, IEEE Transactions on Knowledge and Data Engineering, v.12 n.3, p.372-390, May 2000
	Massimo Coppola , Marco Vanneschi, High-performance data mining with skeleton-based structured parallel programming, Parallel Computing, v.28 n.5, p.793-813, May 2002
	Daniel Kifer , Johannes Gehrke , Cristian Bucila , Walker White, How to quickly find a witness, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.272-283, June 09-11, 2003, San Diego, California
	Ganesh Ramesh , William A. Maniatty , Mohammed J. Zaki, Feasible itemset distributions in data mining: theory and application, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.284-295, June 09-11, 2003, San Diego, California
	Alain Casali , Rosine Cicchetti , Lotfi Lakhal, Extracting semantics from data cubes using cube transversals and closures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
	Cristian Bucila , Johannes Gehrke , Daniel Kifer , Walker White, DualMiner: a dual-pruning algorithm for itemsets with constraints, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Michael Steinbach , Pang-Ning Tan , Vipin Kumar, Support envelopes: a technique for exploring the structure of association patterns, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Ming-Yen Lin , Suh-Yin Lee, Incremental update on sequential patterns in large databases by implicit merging and efficient counting, Information Systems, v.29 n.5, p.385-404, July 2004
	Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
	Magnus Wahlström, Exact algorithms for finding minimum transversals in rank-3 hypergraphs, Journal of Algorithms, v.51 n.2, p.107-121, May 2004
	K. K. Loo , Chi Lap Yip , Ben Kao , David Cheung, A lattice-based approach for I/O efficient association rule mining, Information Systems, v.27 n.1, p.41-74, March 2002
	D. -I. Lin , Z. M. Kedem, Pincer-Search: An Efficient Algorithm for Discovering the Maximum Frequent Set, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.553-566, May 2002
	Xifeng Yan , Hong Cheng , Jiawei Han , Dong Xin, Summarizing itemset patterns: a profile-based approach, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	Li Yang, Pruning and Visualizing Generalized Association Rules in Parallel Coordinates, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.60-70, January 2005
	Dimitris J. Kavvadias , Elias C. Stavropoulos, Monotone boolean dualization is in co-NP[log²n], Information Processing Letters, v.85 n.1, p.1-6, 16 January 2003
	Chao Wang , Srinivasan Parthasarathy, Summarizing itemset patterns using probabilistic models, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Leonid Khachiyan , Endre Boros , Khaled Elbassioni , Vladimir Gurvich, An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation, Discrete Applied Mathematics, v.154 n.16, p.2350-2372, 1 November 2006
	Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, On compressing frequent patterns, Data & Knowledge Engineering, v.60 n.1, p.5-29, January, 2007
	Matthias Hagen, On the fixed-parameter tractability of the equivalence test of monotone normal forms, Information Processing Letters, v.103 n.4, p.163-167, August, 2007
	Leonid Khachiyan , Endre Boros , Khaled Elbassioni , Vladimir Gurvich, A global parallel algorithm for the hypergraph transversal problem, Information Processing Letters, v.101 n.4, p.148-155, February, 2007
	Thomas Eiter , Kazuhisa Makino , Georg Gottlob, Computational aspects of monotone dualization: A brief survey, Discrete Applied Mathematics, v.156 n.11, p.2035-2049, June, 2008
	Leonid Khachiyan , Endre Boros , Khaled Elbassioni , Vladimir Gurvich , Kazuhisa Makino, Dual-bounded generating problems: Efficient and inefficient points for discrete probability distributions and sparse boxes for multidimensional data, Theoretical Computer Science, v.379 n.3, p.361-376, June, 2007
	Kotagiri Ramamohanarao , Hongjian Fan, Patterns Based Classifiers, World Wide Web, v.10 n.1, p.71-83, March 2007
	Robert H. Sloan , Ken Takata , György Turán, On frequent sets of Boolean matrices, Annals of Mathematics and Artificial Intelligence, v.24 n.1-4, p.193-209, 1998
	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic Subspace Clustering of High Dimensional Data, Data Mining and Knowledge Discovery, v.11 n.1, p.5-33, July 2005
	E. Boros , V. Gurvich , L. Khachiyan , K. Makino, On Maximal Frequent and Minimal Infrequent Sets in Binary Matrices, Annals of Mathematics and Artificial Intelligence, v.39 n.3, p.211-221, November 2003
	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, A Microeconomic View of Data Mining, Data Mining and Knowledge Discovery, v.2 n.4, p.311-324, December 1998
	Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997
	Byron J. Gao , Martin Ester , Jin-Yi Cai , Oliver Schulte , Hui Xiong, The minimum consistent subset cover problem and its applications in data mining, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA
	Arnaud Durand , Miki Hermann, On the counting complexity of propositional circumscription, Information Processing Letters, v.106 n.4, p.164-170, May, 2008
	Yen-Liang Chen , Lucas Tzu-Hsuan Hung, Using decision trees to summarize associative classification rules, Expert Systems with Applications: An International Journal, v.36 n.2, p.2338-2351, March, 2009
	Céline Hébert , Alain Bretto , Bruno Crémilleux, A Data Mining Formalization to Improve Hypergraph Minimal Transversal Computation, Fundamenta Informaticae, v.80 n.4, p.415-433, December 2007
	Khaled M. Elbassioni, On the complexity of monotone dualization and generating minimal hypergraph transversals, Discrete Applied Mathematics, v.156 n.11, p.2109-2123, June, 2008
	Leonid Khachiyan , Endre Boros , Khaled Elbassioni , Vladimir Gurvich, Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions, Discrete Applied Mathematics, v.156 n.11, p.2020-2034, June, 2008
	Daya Ram Gaur , Ramesh Krishnamurti, Self-duality of bounded monotone boolean functions and related problems, Discrete Applied Mathematics, v.156 n.10, p.1598-1605, May, 2008
	Matthias Hagen, Lower bounds for three algorithms for transversal hypergraph generation, Discrete Applied Mathematics, v.157 n.7, p.1460-1469, April, 2009
	Arnaud Soulet , Bruno Crémilleux, Mining constraint-based patterns using automatic relaxation, Intelligent Data Analysis, v.13 n.1, p.109-133, January 2009
	Ardian Kristanto Poernomo , Vivekanand Gopalkrishnan, CP-summary: a concise representation for browsing frequent itemsets, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France
	Sébastien Nedjar , Alain Casali , Rosine Cicchetti , Lotfi Lakhal, Emerging Cubes: Borders, size estimations and lossless reductions, Information Systems, v.34 n.6, p.536-550, September, 2009