2009
Journal article
Open Access
A constraint-based querying system for exploratory pattern discovery
Bonchi F., Giannotti F., Lucchese C., Orlando S., Perego R, Trasarti R
Constrained Frequent Pattern Mining Information Systems Hardware and Architecture Interactive Data Mining Software H.2.8 Database Applications
In this article we present ConQueSt, a constraint based querying system able to support the intrinsically exploratory (i.e., human-guided, interactive, iterative) nature of pattern discovery. Following the inductive database vision, our framework provides users with an expressive constraint based query language, which allows the discovery process to be effectively driven toward potentially interesting patterns. Such constraints are also exploited to reduce the cost of pattern mining computation. ConQueSt is a comprehensive mining system that can access real world relational databases from which to extract data. Through the interaction with a friendly GUI, the user can define complex mining queries by means of few clicks. After a preprocessing step, mining queries are answered by an efficient and robust pattern mining engine which entails the state-of-the-art of data and search space reduction techniques. Resulting patterns are then presented to the user in a pattern browsing window, and possibly stored back in the underlying database as relations.
Source: Information systems (Oxf.) 34 (2009): 3–27. doi:10.1016/j.is.2008.02.007
Publisher: Pergamon,, Oxford , Regno Unito
[1] R. Srikant, Q. Vu, R. Agrawal, Mining association rules with item constraints, in: Proceedings of the 3rd ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD'97), 1997.
[2] R.T. Ng, L.V.S. Lakshmanan, J. Han, A. Pang, Exploratory mining and pruning optimizations of constrained associations rules, in: Proceedings of the ACM International Conference on Management of Data (SIGMOD'98), 1998.
[3] J. Han, L.V.S. Lakshmanan, R.T. Ng, Constraint-based, multidimensional data mining, Computer 32 (8) (1999) 46-50.
[4] R.J. Bayardo Jr. R. Agrawal, D. Gunopulos, Constraint-based rule mining in large, dense databases, in: Proceedings of the 15th International Conference on Data Engineering (ICDE'99), Sydney, Australia, 23-26 March 1999.
[5] J.-F. Boulicaut, B. Jeudy, Constraint-based data mining, in: O. Maimon, L. Rokach (Eds.), The Data Mining and Knowledge Discovery Handbook, Springer, Berlin, 2005, pp. 399-416.
[6] C. Ordonez, L. de Braal, C.A. Santana, Discovering interesting association rules in medical data, in: ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD'00), 2000.
[7] C. Ordonez, E. Omiecinski, L. de Braal, C.A. Santana, N. Ezquerra, J.A. Taboada, D. Cooke, E. Krawczynska, E.V. Garcia, Mining constrained association rules to predict heart disease, in: Proceedings of the 1st IEEE International Conference on Data Mining (ICDM'01), 2001.
[8] A. Lau, S. Ong, A. Mahidadia, A. Hoffmann, J. Westbrook, T. Zrimec, Mining patterns of dyspepsia symptoms across time points using constraint association rules, in: Proceedings of the 7th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'03), 2003.
[9] J. Besson, C. Robardet, J. Boulicaut, S. Rome, Constraint-based concept mining and its application to microarray data analysis, Intelligent Data Anal. J. 9(1) (2005) 59-82.
[10] H. Mannila, H. Toivonen, Levelwise search and borders of theories in knowledge discovery, Data Mining and Knowledge Discovery 1 (3) (1997) 241-258.
[11] F. Bonchi, F. Giannotti, C. Lucchese, S. Orlando, R. Perego, R. Trasarti, Conquest: a constraint-based querying system for exploratory pattern (demo), in: IEEE International Conference on Data Engineering, 2006.
[12] U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, The kdd process for extracting useful knowledge from volumes of data, Commun. ACM 39 (11) (1996) 27-34.
[13] R. Agrawal, R. Srikant, Fast algorithms for mining association rules in large databases, in: Proceedings of the 20th International Conference on Very Large Databases (VLDB'94), 1994.
[14] S. Bistarelli, F. Bonchi, Interestingness is not a dichotomy: introducing softness in constrained pattern mining, in: Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, 2005, pp. 22-33.
[15] F. Bonchi, F. Giannotti, C. Lucchese, S. Orlando, R. Perego, R. Trasarti, On interactive pattern mining from relational databases, in: International Workshop on Knowledge Discovery in Inductive Databases, 2006.
[16] F. Bonchi, F. Giannotti, A. Mazzanti, D. Pedreschi, ExAMiner: optimized level-wise frequent pattern mining with monotone constraints, in: Proceedings of the Third IEEE International Conference on Data Mining (ICDM'03), 2003.
[17] J. Pei, J. Han, L.V.S. Lakshmanan, Mining frequent item sets with convertible constraints, in: 17th IEEE International Conference on Data Engineering (ICDE'01), 2001.
[18] F. Bonchi, C. Lucchese, Pushing tougher constraints in frequent pattern mining, in: Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'05), Hanoi, Vietnam, 2005.
[19] R. Meo, G. Psaila, S. Ceri, A new SQL-like operator for mining association rules, in: T.M. Vijayaraman, A.P. Buchmann, C. Mohan, N.L. Sarda (Eds.), Proceedings of 22th International Conference on Very Large Data Bases (VLDB'96), Mumbai (Bombay), India, 3-6 September 1996, pp. 122-133.
[20] R. Meo, G. Psaila, S. Ceri, A tightly-coupled architecture for data mining, in: International Conference on Data Engineering (ICDE98), 1998, pp. 316-323.
[21] J. Han, Y. Fu, K. Koperski, W. Wang, O. Zaiane, DMQL: a data mining query language for relational databases, in: SIGMOD'96 Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'96), 1996.
[22] J. Han, M. Kamber, Data Mining: Concepts and Techniques, Morgan Kaufman, Los Altos, CA, 2000.
[23] T. Imielinski, A. Virmani, MSQL: a query language for database mining, Data Min. Knowl. Discovery 3 (4) (1999) 373-408.
[24] T. Calders, B. Goetals, A. Prado, Integrating pattern mining in relational databases, in: Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'06), 2006, pp. 454-461.
[25] S. Orlando, P. Palmerini, R. Perego, F. Silvestri, Adaptive and resource-aware mining of frequent sets, in: Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), Maebashi City, Japan, December 2002, pp. 338-345.
[26] F. Bonchi, F. Giannotti, A. Mazzanti, D. Pedreschi, ExAnte: anticipated data reduction in constrained pattern mining, in: Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'03), 2003.
[27] F. Bonchi, C. Lucchese, On closed constrained frequent pattern mining, in: Proceedings of the 4h IEEE International Conference on Data Mining (ICDM'04), 2004.
[28] L.V.S. Lakshmanan, R.T. Ng, J. Han, A. Pang, Optimization of constrained frequent set queries with 2-variable constraints, in: Proceedings of the ACM International Conference on Management of Data (SIGMOD'99), 1999.
[29] S. Kramer, L.D. Raedt, C. Helma, Molecular feature mining in hiv data, in: Proceedings of the 7th ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD'01), 2001.
[30] C. Bucila, J. Gehrke, D. Kifer, W. White, DualMiner: a dual-pruning algorithm for itemsets with constraints, in: Proceedings of the 8th ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD'02), 2002.
[31] J. Pei, J. Han, Can we push more constraints into frequent pattern mining? in: Proceedings of the 6th ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD'00), 2000.
[32] F. Bonchi, C. Lucchese, Extending the state-of-the-art of constraintbased pattern discovery, Data Knowl. Eng. (DKE) 60 (2) (2007) 377-399.
[33] L.D. Raedt, S. Kramer, The levelwise version space algorithm and its application to molecular fragment finding, in: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI'01), 2001.
[34] B. Jeudy, J.-F. Boulicaut, Optimization of association rule mining queries, Intelligent Data Anal. J. 6 (4) (2002) 341-357.
[35] F. Bonchi, F. Giannotti, A. Mazzanti, D. Pedreschi, Adaptive constraint pushing in frequent pattern mining, in: Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'03), 2003.
[2] R.T. Ng, L.V.S. Lakshmanan, J. Han, A. Pang, Exploratory mining and pruning optimizations of constrained associations rules, in: Proceedings of the ACM International Conference on Management of Data (SIGMOD'98), 1998.
[3] J. Han, L.V.S. Lakshmanan, R.T. Ng, Constraint-based, multidimensional data mining, Computer 32 (8) (1999) 46-50.
[4] R.J. Bayardo Jr. R. Agrawal, D. Gunopulos, Constraint-based rule mining in large, dense databases, in: Proceedings of the 15th International Conference on Data Engineering (ICDE'99), Sydney, Australia, 23-26 March 1999.
[5] J.-F. Boulicaut, B. Jeudy, Constraint-based data mining, in: O. Maimon, L. Rokach (Eds.), The Data Mining and Knowledge Discovery Handbook, Springer, Berlin, 2005, pp. 399-416.
[6] C. Ordonez, L. de Braal, C.A. Santana, Discovering interesting association rules in medical data, in: ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD'00), 2000.
[7] C. Ordonez, E. Omiecinski, L. de Braal, C.A. Santana, N. Ezquerra, J.A. Taboada, D. Cooke, E. Krawczynska, E.V. Garcia, Mining constrained association rules to predict heart disease, in: Proceedings of the 1st IEEE International Conference on Data Mining (ICDM'01), 2001.
[8] A. Lau, S. Ong, A. Mahidadia, A. Hoffmann, J. Westbrook, T. Zrimec, Mining patterns of dyspepsia symptoms across time points using constraint association rules, in: Proceedings of the 7th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'03), 2003.
[9] J. Besson, C. Robardet, J. Boulicaut, S. Rome, Constraint-based concept mining and its application to microarray data analysis, Intelligent Data Anal. J. 9(1) (2005) 59-82.
[10] H. Mannila, H. Toivonen, Levelwise search and borders of theories in knowledge discovery, Data Mining and Knowledge Discovery 1 (3) (1997) 241-258.
[11] F. Bonchi, F. Giannotti, C. Lucchese, S. Orlando, R. Perego, R. Trasarti, Conquest: a constraint-based querying system for exploratory pattern (demo), in: IEEE International Conference on Data Engineering, 2006.
[12] U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, The kdd process for extracting useful knowledge from volumes of data, Commun. ACM 39 (11) (1996) 27-34.
[13] R. Agrawal, R. Srikant, Fast algorithms for mining association rules in large databases, in: Proceedings of the 20th International Conference on Very Large Databases (VLDB'94), 1994.
[14] S. Bistarelli, F. Bonchi, Interestingness is not a dichotomy: introducing softness in constrained pattern mining, in: Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, 2005, pp. 22-33.
[15] F. Bonchi, F. Giannotti, C. Lucchese, S. Orlando, R. Perego, R. Trasarti, On interactive pattern mining from relational databases, in: International Workshop on Knowledge Discovery in Inductive Databases, 2006.
[16] F. Bonchi, F. Giannotti, A. Mazzanti, D. Pedreschi, ExAMiner: optimized level-wise frequent pattern mining with monotone constraints, in: Proceedings of the Third IEEE International Conference on Data Mining (ICDM'03), 2003.
[17] J. Pei, J. Han, L.V.S. Lakshmanan, Mining frequent item sets with convertible constraints, in: 17th IEEE International Conference on Data Engineering (ICDE'01), 2001.
[18] F. Bonchi, C. Lucchese, Pushing tougher constraints in frequent pattern mining, in: Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'05), Hanoi, Vietnam, 2005.
[19] R. Meo, G. Psaila, S. Ceri, A new SQL-like operator for mining association rules, in: T.M. Vijayaraman, A.P. Buchmann, C. Mohan, N.L. Sarda (Eds.), Proceedings of 22th International Conference on Very Large Data Bases (VLDB'96), Mumbai (Bombay), India, 3-6 September 1996, pp. 122-133.
[20] R. Meo, G. Psaila, S. Ceri, A tightly-coupled architecture for data mining, in: International Conference on Data Engineering (ICDE98), 1998, pp. 316-323.
[21] J. Han, Y. Fu, K. Koperski, W. Wang, O. Zaiane, DMQL: a data mining query language for relational databases, in: SIGMOD'96 Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'96), 1996.
[22] J. Han, M. Kamber, Data Mining: Concepts and Techniques, Morgan Kaufman, Los Altos, CA, 2000.
[23] T. Imielinski, A. Virmani, MSQL: a query language for database mining, Data Min. Knowl. Discovery 3 (4) (1999) 373-408.
[24] T. Calders, B. Goetals, A. Prado, Integrating pattern mining in relational databases, in: Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'06), 2006, pp. 454-461.
[25] S. Orlando, P. Palmerini, R. Perego, F. Silvestri, Adaptive and resource-aware mining of frequent sets, in: Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), Maebashi City, Japan, December 2002, pp. 338-345.
[26] F. Bonchi, F. Giannotti, A. Mazzanti, D. Pedreschi, ExAnte: anticipated data reduction in constrained pattern mining, in: Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'03), 2003.
[27] F. Bonchi, C. Lucchese, On closed constrained frequent pattern mining, in: Proceedings of the 4h IEEE International Conference on Data Mining (ICDM'04), 2004.
[28] L.V.S. Lakshmanan, R.T. Ng, J. Han, A. Pang, Optimization of constrained frequent set queries with 2-variable constraints, in: Proceedings of the ACM International Conference on Management of Data (SIGMOD'99), 1999.
[29] S. Kramer, L.D. Raedt, C. Helma, Molecular feature mining in hiv data, in: Proceedings of the 7th ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD'01), 2001.
[30] C. Bucila, J. Gehrke, D. Kifer, W. White, DualMiner: a dual-pruning algorithm for itemsets with constraints, in: Proceedings of the 8th ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD'02), 2002.
[31] J. Pei, J. Han, Can we push more constraints into frequent pattern mining? in: Proceedings of the 6th ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD'00), 2000.
[32] F. Bonchi, C. Lucchese, Extending the state-of-the-art of constraintbased pattern discovery, Data Knowl. Eng. (DKE) 60 (2) (2007) 377-399.
[33] L.D. Raedt, S. Kramer, The levelwise version space algorithm and its application to molecular fragment finding, in: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI'01), 2001.
[34] B. Jeudy, J.-F. Boulicaut, Optimization of association rule mining queries, Intelligent Data Anal. J. 6 (4) (2002) 341-357.
[35] F. Bonchi, F. Giannotti, A. Mazzanti, D. Pedreschi, Adaptive constraint pushing in frequent pattern mining, in: Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD'03), 2003.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:44241,
title = {A constraint-based querying system for exploratory pattern discovery},
author = {Bonchi F. and Giannotti F. and Lucchese C. and Orlando S. and Perego R and Trasarti R},
publisher = {Pergamon,, Oxford , Regno Unito},
doi = {10.1016/j.is.2008.02.007},
journal = {Information systems (Oxf.)},
volume = {34},
pages = {3–27},
year = {2009}
}CNR authors
Bonchi, Francesco
0000-0001-9464-8315
Giannotti, Fosca0000-0003-3099-3835
Lucchese, Claudio0000-0002-2545-0425
Orlando, Salvatore0000-0002-4155-9797
Perego, Raffaele0000-0001-7189-4724
Trasarti, Roberto0000-0001-5316-6475
Knowledge Discovery and Data Mining (2002-ongoing)
High Performance Computing (2002-ongoing)
