A perspective on inductive databases

ABSTRACT

Inductive databases tightly integrate databases with data mining. The key ideas are that data and patterns (or models) are handled in the same way and that an inductive query language allows the user to query and manipulate the patterns (or models) of interest.This paper proposes a simple and abstract model for inductive databases. We describe the basic formalism, a simple but fairly powerful inductive query language, some basics of reasoning for query optimization, and discuss some memory organization and implementation issues.

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: Elena Baralis , Giuseppe Psaila, Incremental Refinement of Mining Queries, Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery, p.173-182, September 01, 1999
• 3: R. Bayardo, (Ed.) Special Issue on Constraint-Based Data Mining, SIGKDD Explorations, 2002.
• 4: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 5: Jean-Francois Boulicaut , Mika Klemettinen , Heikki Mannila, Querying Inductive Databases: A Case Study on the MINE RULE Operator, Proceedings of the Second European Symposium on Principles of Data Mining and Knowledge Discovery, p.194-202, September 23-26, 1998
• 6: Jean-Francois Boulicaut , Mika Klemettinen , Heikki Mannila, Modeling KDD Processes within the Inductive Database Framework, Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery, p.293-302, September 01, 1999
• 7: Jean Francois Boulicaut, habilitation thesis, INSA-Lyon, France, 2001.
• 8: Jean-François Boulicaut , Artur Bykowski , Christophe Rigotti, Free-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries, Data Mining and Knowledge Discovery, v.7 n.1, p.5-22, January 2003 [doi>10.1023/A:1021571501451 ]
• 9: Toon Calders , Jan Paredaens, Axiomatization of Frequent Sets, Proceedings of the 8th International Conference on Database Theory, p.204-218, January 04-06, 2001
• 10: Daniele Braga , Alessandro Campi , Mika Klemettinen , Pier Luca Lanzi, Mining Association Rules from XML Data, Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, p.21-30, September 04-06, 2002
• 11: 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 [doi>10.1145/775047.775054]
• 12: Luc Dehaspe , Hannu Toivonen, Discovery of frequent DATALOG patterns, Data Mining and Knowledge Discovery, v.3 n.1, p.7-36, March 1999 [doi>10.1023/A:1009863704807 ]
• 13: L. De Raedt, S. Kramer, The level wise version space algorithm and its application to molecular fragment finding, in Proceedings of the 17th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 2001.
• 14: L. De Raedt. Query evaluation and optimisation in inductive databases using version spaces. In Proceedings of the DTDM Workshop, EDBT 2002.
• 15: L. De Raedt, S. Kramer. Inductive databases for bio- and chemo-informatics. In Frasconi, P. and Shamir, R. (Eds.) Artificial Intelligence and Heuristic Methods for Bioinformatics, IOS Press (Nato Science Series), 2002. In press.
• 16: Luc DE RAEDT , Manfred JAEGER , Sau Dan LEE , Heikki MANNILA, A Theory of Inductive Query Answering, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.123, December 09-12, 2002
• 17: A. Giacometti, D. Laurent and C. Diop. Condensed Representations for Sets of Mining Queries. In Proc. 1st Workshop on Knowledge Discovery with Inductive Queries Helsinki, ECML/PKDD 2002.
• 18: Fosca Giannotti , Giuseppe Manco, Querying Inductive Databases via Logic-Based User-Defined Aggregates, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.125-135, September 15-18, 1999
• 19: Bart Goethals , Jan Van den Bussche, On Supporting Interactive Association Rule Mining, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.307-316, September 04-06, 2000
• 20: Bart Goethals, Jan Van den Bussche: A priori versus a posteriori filtering of association rules. In Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 1999.
• 21: 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
• 22: J. Han, Y. Fu, K. Koperski, W. Wang, and O. Zaiane, DMQL: A Data Mining Query Language for Relational Databases, in Proceedings of the ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery, 1996.
• 23: Jiawei Han , Laks V. S. Lakshmanan , Raymond T. Ng, Constraint-Based, Multidimensional Data Mining, Computer, v.32 n.8, p.46-50, August 1999 [doi>10.1109/2.781634 ]
• 24: 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
• 25: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 26: Haym Hirsh, Generalizing Version Spaces, Machine Learning, v.17 n.1, p.5-46, Oct. 1994 [doi>10.1023/A:1022600917598]
• 27: H. Hirsh. Theoretical underpinnings of versionspaes. In Proceedings of the 12th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 1991.
• 28: Tomasz Imielinski , Heikki Mannila, A database perspective on knowledge discovery, Communications of the ACM, v.39 n.11, p.58-64, Nov. 1996 [doi>10.1145/240455.240472]
• 29: Tomasz Imieliński , Aashu Virmani, MSQL: A Query Language for Database Mining, Data Mining and Knowledge Discovery, v.3 n.4, p.373-408, December 1999 [doi>10.1023/A:1009816913055 ]
• 30: Baptiste Jeudy and Jean-François Boulicaut. Optimization of association rule mining queries, Intelligent Data Analysis, Vol. 6 (5), 2002.
• 31: Stefan Kramer , Luc De Raedt , Christoph Helma, Molecular feature mining in HIV data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.136-143, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502533]
• 32: Tessa Lau , Steven A. Wolfman , Pedro Domingos , Daniel S. Weld, Programming by Demonstration Using Version Space Algebra, Machine Learning, v.53 n.1-2, p.111-156, October-November 2003
• 33: S.D. Lee, L. De Raedt. Mining logical sequences in MineSeqLog. In Dzeroski, S., De Raedt, L., Wrobel, S. (Eds.) Proceedings of the SIGKDD workshop on Multi-Relational Data Mining, 2002.
• 34: 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 [doi>10.1023/A:1009796218281 ]
• 35: Rosa Meo , Giuseppe Psaila , Stefano Ceri, An Extension to SQL for Mining Association Rules, Data Mining and Knowledge Discovery, v.2 n.2, p.195-224, June 1998 [doi>10.1023/A:1009774406717 ]
• 36: Chris Mellish, The description identification problem, Artificial Intelligence, v.52 n.2, p.151-167, Dec. 1991 [doi>10.1016/0004-3702(91)90040-Q ]
• 37: T. Mitchell. Generalization as Search, Artificial Intelligence, Vol. 18 (2), pp. 203--226, 1980.
• 38: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• 39: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Efficient mining of association rules using closed itemset lattices, Information Systems, v.24 n.1, p.25-46, March 1999 [doi>10.1016/S0306-4379(99)00003-4 ]
• 40: Jian Pei , Jiawei Han, Constrained frequent pattern mining: a pattern-growth view, ACM SIGKDD Explorations Newsletter, v.4 n.1, June 2002 [doi>10.1145/568574.568580]
• 41: J. Pei, J. Han, and R. Mao. Closet: An efficient algorithm for mining frequent closed itemsets. In W. Chen, J.F. Naughton, and P.A. Bernstein, editors, ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, Dallas, TX, 2000.
• 42: Anthony K. H. Tung , Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han, Constraint-based clustering in large databases, Proceedings of the 8th International Conference on Database Theory, p.405-419, January 04-06, 2001

INDEX TERMS

Keywords:
constraint-based mining, inductive databases, inductive querying