{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:04:31Z","timestamp":1760241871527,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2018,10,25]],"date-time":"2018-10-25T00:00:00Z","timestamp":1540425600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Formal concept analysis (FCA) is largely applied in different areas. However, in some FCA applications the volume of information that needs to be processed can become unfeasible. Thus, the demand for new approaches and algorithms that enable processing large amounts of information is increasing substantially. This article presents a new algorithm for extracting proper implications from high-dimensional contexts. The proposed algorithm, called ImplicPBDD, was based on the PropIm algorithm, and uses a data structure called binary decision diagram (BDD) to simplify the representation of the formal context and enhance the extraction of proper implications. In order to analyze the performance of the ImplicPBDD algorithm, we performed tests using synthetic contexts varying the number of objects, attributes and context density. The experiments show that ImplicPBDD has a better performance\u2014up to 80% faster\u2014than its original algorithm, regardless of the number of attributes, objects and densities.<\/jats:p>","DOI":"10.3390\/info9110266","type":"journal-article","created":{"date-parts":[[2018,10,26]],"date-time":"2018-10-26T03:16:16Z","timestamp":1540523776000},"page":"266","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["ImplicPBDD: A New Approach to Extract Proper Implications Set from High-Dimension Formal Contexts Using a Binary Decision Diagram \u2020"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5335-9592","authenticated-orcid":false,"given":"Phillip G.","family":"Santos","sequence":"first","affiliation":[{"name":"Department of Computer Science, Pontifical Catholic University of Minas Gerais (PUC Minas), Belo Horizonte 31980-110, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6423-8681","authenticated-orcid":false,"given":"Pedro Henrique B.","family":"Ruas","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Pontifical Catholic University of Minas Gerais (PUC Minas), Belo Horizonte 31980-110, Brazil"}]},{"given":"Julio C. V.","family":"Neves","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Pontifical Catholic University of Minas Gerais (PUC Minas), Belo Horizonte 31980-110, Brazil"}]},{"given":"Paula R.","family":"Silva","sequence":"additional","affiliation":[{"name":"Laboratory of Artificial Intelligence and Decision Support (LIAAD), INESC TEC, Porto 4200-465, Portugal"}]},{"given":"S\u00e9rgio M.","family":"Dias","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Pontifical Catholic University of Minas Gerais (PUC Minas), Belo Horizonte 31980-110, Brazil"},{"name":"Federal Service of Data Processing (SERPRO), Belo Horizonte 31035-536, Brazil"}]},{"given":"Luis E.","family":"Z\u00e1rate","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Pontifical Catholic University of Minas Gerais (PUC Minas), Belo Horizonte 31980-110, Brazil"}]},{"given":"Mark A. J.","family":"Song","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Pontifical Catholic University of Minas Gerais (PUC Minas), Belo Horizonte 31980-110, Brazil"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,25]]},"reference":[{"key":"ref_1","unstructured":"Ganter, B., and Wille, R. (1997). Formal Concept Analysis: Mathematical Foundations, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ganter, B., Stumme, G., and Wille, R. (2005). Formal Concept Analysis: Foundations and Applications, Springer.","DOI":"10.1007\/978-3-540-31881-1"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1016\/j.infsof.2014.01.012","article-title":"Efficient synthesis of feature models","volume":"56","author":"She","year":"2014","journal-title":"Inf. Softw. Technol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/s10489-013-0451-7","article-title":"Formal and relational concept analysis for fuzzy-based automatic semantic annotation","volume":"40","author":"Fenza","year":"2014","journal-title":"Appl. Intell."},{"key":"ref_5","first-page":"34","article-title":"Analysis of a vector space model, latent semantic indexing and formal concept analysis for information retrieval","volume":"12","author":"Kumar","year":"2012","journal-title":"Cybern. Inf. Technol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.knosys.2011.06.025","article-title":"Graphical norms via conceptual graphs","volume":"29","author":"Croitoru","year":"2012","journal-title":"Knowl.-Based Syst."},{"key":"ref_7","unstructured":"Poelmans, J., Elzinga, P., and Dedene, G. (2013, January 25\u201327). Retrieval of criminal trajectories with an FCA-based approach. Proceedings of the FCAIR 2013 Formal Concept Analysis Meets Information Retrieval Workshop, Co-Located with the 35th European Conference on Information Retrieval (ECIR 2013), Moscow, Russia."},{"key":"ref_8","unstructured":"Xhafa, F., and Bessis, N. (2014). Discovering the Hidden Semantics in Enterprise Resource Planning Data Through Formal Concept Analysis. Inter-Cooperative Collective Intelligence: Techniques and Applications, Springer."},{"key":"ref_9","first-page":"73","article-title":"Advances in FCA-based applications for social networks analysis","volume":"1","author":"Aufaure","year":"2013","journal-title":"IJCSSA"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Missaoui, R., Kuznetsov, S.O., and Obiedkov, S. (2017). Formal Concept Analysis of Social Networks, Springer. Lecture Notes in Social Networks.","DOI":"10.1007\/978-3-319-64167-6"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Missaoui, R., Abdessalem, T., and Latapy, M. (2017). Trends in Social Network Analysis, Springer. Lecture Notes in Social Networks.","DOI":"10.1007\/978-3-319-53420-6"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s10472-012-9329-3","article-title":"Relational concept analysis: Mining concept lattices from multi-relational data","volume":"67","author":"Huchard","year":"2013","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.eswa.2016.03.011","article-title":"A step forward for Topic Detection in Twitter: An FCA-based approach","volume":"57","author":"Castellanos","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/j.ipm.2016.08.002","article-title":"PREFCA: A portal retrieval engine based on formal concept analysis","volume":"53","author":"Negm","year":"2017","journal-title":"Inf. Process. Manag."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1515\/amcs-2016-0035","article-title":"A comprehensive survey on formal concept analysis, its research trends and applications","volume":"26","author":"Singh","year":"2011","journal-title":"Int. J. Appl. Math. Comput. Sci."},{"key":"ref_16","unstructured":"Taouil, R., and Bastide, Y. (August, January 30). Computing Proper Implications. Proceedings of the 9th International Conference on Conceptual Structures, ICCS 2001, Stanford, CA, USA."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s10472-013-9355-9","article-title":"Fast Algorithms for Implication Using Proper Premises","volume":"70","author":"Ryssel","year":"2014","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Silva, P.R.C., Dias, S.M., Brand\u00e3o, W.C., Song, M.A., and Z\u00e1rate, L.E. (2017). Formal Concept Analysis Applied to Professional Social Networks Analysis, ICEIS.","DOI":"10.5220\/0006333401230134"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0169-023X(94)90023-X","article-title":"Algorithms for inferring functional dependencies from relations","volume":"12","author":"Mannila","year":"1994","journal-title":"Data Knowl. Eng."},{"key":"ref_20","unstructured":"Priss, U. (2006, January 13\u201317). Some open problems in formal concept analysis. Proceedings of the 4th International Conference\u2014ICFCA 2006, Dresden, Germany."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Santos, P., Neves, J., Silva, P., Dias, S.M., Z\u00e1rate, L., and Song, M. (2018, January 21\u201324). An Approach to Extract Proper Implications Set from High-dimension Formal Contexts using Binary Decision Diagram. Proceedings of the 20th International Conference on Enterprise Information Systems, Funchal, Portugal.","DOI":"10.5220\/0006775400500057"},{"key":"ref_22","unstructured":"Bertet, K. (2006, January 30). Some algorithmical aspects using the canonical direct implicationnal basis. Proceedings of the Fourth International Conference\u2014CLA 2006, Tunis, Tunisia."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2155","DOI":"10.1016\/j.tcs.2009.12.021","article-title":"The multiple facets of the canonical direct unit implicational basis","volume":"411","author":"Bertet","year":"2001","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","article-title":"Graph-Based Algorithms for Boolean Function Manipulation","volume":"35","author":"Bryant","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.ress.2014.06.025","article-title":"Choosing a heuristic and root node for edge ordering in BDD-based network reliability analysis","volume":"131","author":"Mo","year":"2014","journal-title":"Reliab. Eng. Syst. Saf."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Rimsa, A., Z\u00e1rate, L.E., and Song, M.A. (2009, January 25\u201327). Evaluation of Different BDD Libraries to Extract Concepts in FCA \u2014 Perspectives and Limitations. Proceedings of the 9th International Conference on Computational Science: Part I, Baton Rouge, LA, USA.","DOI":"10.1007\/978-3-642-01970-8_36"},{"key":"ref_27","unstructured":"Burmeister, P. (2003). Formal Concept Analysis with ConImp: Introduction to the Basic Features, Fachbereich Mathematik, Technische Universit\u00e4t Darmstadt."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1339","DOI":"10.1002\/qre.2344","article-title":"Binary decision diagram\u2013based methods for risk assessment of systems subject to propagated failures and parametric uncertainties","volume":"34","author":"Qiu","year":"2018","journal-title":"Qual. Reliab. Eng. Int."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10601-018-9286-5","article-title":"From MDD to BDD and Arc consistency","volume":"23","author":"Vion","year":"2018","journal-title":"Constraints"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1017\/S1351324918000268","article-title":"Extraction of templates from phrases using Sequence Binary Decision Diagrams","volume":"24","author":"Hirano","year":"2018","journal-title":"Nat. Lang. Eng."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.is.2017.01.008","article-title":"Formal concept analysis for topic detection: A clustering quality experimental analysis","volume":"66","author":"Castellanos","year":"2017","journal-title":"Inf. Syst."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/j.future.2016.05.039","article-title":"Unfolding social content evolution along time and semantics","volume":"66","author":"Fenza","year":"2017","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_33","first-page":"61","article-title":"Bdd-based algorithms for the construction of the set of all concepts","volume":"Volume 2002","author":"Yevtushenko","year":"2002","journal-title":"Foundations and Applications of Conceptual Structures"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/j.ins.2017.11.028","article-title":"Handling high-dimensionality contexts in formal concept analysis via binary decision diagrams","volume":"429","author":"Neto","year":"2018","journal-title":"Inf. Sci."},{"key":"ref_35","unstructured":"Salleb, A., Maazouzi, Z., and Vrain, C. (2002, January 21\u201326). Mining Maximal Frequent Itemsets by a Boolean Based Approach. Proceedings of the 15th European Conference on Artificial Intelligence, Lyon, France."},{"key":"ref_36","unstructured":"Lind-Nielsen, J., Somenzi, F., and Vahidi, A. (2018, September 03). JavaBDD. Available online: http:\/\/javabdd.sourceforge.net."},{"key":"ref_37","unstructured":"LinkedIn (2018, September 07). About LinkedIn. Available online: https:\/\/about.linkedin.com."},{"key":"ref_38","unstructured":"Durand, T. (1998, January 18\u201320). Forms of incompetence. Proceedings of the Fourth International Conference on Competence-Based Management, Oslo, Norway."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Hammoudi, S., \u015amia\u0142ek, M., Camp, O., and Filipe, J. (2018). Professional Competence Identification Through Formal Concept Analysis. Enterprise Information Systems, Springer.","DOI":"10.1007\/978-3-319-93375-7"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/978-3-540-45228-7_32","article-title":"Using an interest ontology for improved support in rule mining","volume":"2737","author":"Chen","year":"2003","journal-title":"Data Warehous. Knowl. Discov."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/11\/266\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:26:11Z","timestamp":1760196371000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/9\/11\/266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,25]]},"references-count":40,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2018,11]]}},"alternative-id":["info9110266"],"URL":"https:\/\/doi.org\/10.3390\/info9110266","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2018,10,25]]}}}