Comparing performance of algorithms for generating concept lattices. (English) Zbl 1024.68020

Summary: Recently concept lattices became widely used tools for intelligent data analysis. In this paper, several algorithms that generate the set of all formal concepts and diagram graphs of concept lattices are considered. Some modifications of well-known algorithms are proposed. Algorithmic complexity of the algorithms is studied both theoretically (in the worst case) and experimentally. Conditions of preferable use of some algorithms are given in terms of density/sparseness of underlying formal contexts. Principles of comparing practical performance of algorithms are discussed.


68P05 Data structures
68P15 Database theory
68Q25 Analysis of algorithms and problem complexity
06B99 Lattices


Full Text: DOI Link


[1] Aho A. V., Data Structures and Algorithms (1983) · Zbl 0487.68005
[2] Blake C. L., UCI Repository of machine learning databases (1998)
[3] Bordat J. P., Math. Sci. Hum. 96 pp 31– (1986)
[4] Carpineto C., Machine Learning 24 pp 95– (1996)
[5] Chein M., Bull. Math. Soc. Sci. Math. R.S. Roumanie 13 pp 21– (1969)
[6] DOI: 10.1006/jmps.1993.1003 · Zbl 0772.92018
[7] Finn V. K., Itogi Nauki i Tekhniki. Ser. Informatika 15 pp 54– (1991)
[8] Ganter B., FB4-Preprint No. 831, in: Two Basic Algorithms in Concept Analysis (1984)
[9] Ganter, B. and Kuznetsov, S. Formalizing hypotheses with concepts. Proceedings 8th International Conference on Conceptual Structures, ICCS 2000, Lecture Notes in Artificial Intelligence. 1867, Darmstadt, Germany. pp.342–356. · Zbl 0973.68195
[10] DOI: 10.1007/BF00383449 · Zbl 0754.06003
[11] Ganter B., Formal Concept Analysis: Mathematical Foundations (1999) · Zbl 0909.06001
[12] DOI: 10.1111/j.1467-8640.1995.tb00031.x
[13] Goldberg L. A., Efficient Algorithms for Listing Combinatorial Structures (1993) · Zbl 0821.68059
[14] Guénoche A., Math. Inf. Sci. Hum. 109 pp 41– (1990)
[15] DOI: 10.1016/0020-0190(88)90065-8 · Zbl 0654.68086
[16] Kuznetsov S. O., Automatic Documentation and Mathematical Linguistics 24 pp 37– (1989)
[17] Kuznetsov S. O., Automatic Documentation and Mathematical Linguistics 27 pp 11– (1993)
[18] DOI: 10.1023/A:1013970520933 · Zbl 0991.06006
[19] Kuznetsov S. O., Preprint MATH-A1-05, in: Algorithm for the Construction of the Set of All Concepts and Their Une Diagram (2000)
[20] Lindig C., Algorithmen zur begriffsanalyse und ihre anwendung bei Softwarebibliotheken, (Dr.-Ing.) (1999)
[21] Mephu Nguifo E., Construction and Selection: A Data Mining Perspective pp 205– (1998)
[22] Norris E. M., Revue Roumaine de Mathématiques Pures et Appliquées 23 pp 243– (1978)
[23] DOI: 10.1016/S0020-0190(99)00108-8 · Zbl 0998.06005
[24] Obiedkov S. A., Nauch. Tekh. Inf., Ser 2 pp 64– (1999)
[25] Stumme, G., Taouil, R., Bastide, Y., Pasquier, N. and Lakhal, L. Fast computation of concept lattices using data mining techniques. Proceedings, 7th Int. Workshop on Knowledge Representation Meets Databases (KRDB 2000). Berlin, Germany. pp.129–139. · Zbl 0983.68511
[26] Stumme, G., Wille, R. and Wille, U. Conceptual knowledge discovery in databases using formal concept analysis methods. Proceedings, 2nd European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD’98). Nantes, France. pp.450–458.
[27] Valtchev, P. and Missaoui, R. Building concept (Galois) lattices from parts: generalizing the incremental methods. Proceedings, 9th International Conference on Conceptual Structures, ICCS 2001, Lecture Notes in Artificial Intelligence, 2120. Stanford, CA, USA. pp.290–303. · Zbl 0998.68172
[28] Valtchev P., A Partition-Based Approach Towards Building Galois (Concept) Lattices. Rapport de recherche no. 2000-08 (2000)
[29] Van Der Merwe F. J., AddAtom: an incremental algorithm for constructing concept lattices and concept sublattices. Technical report (2002)
[30] Yevtushenko, S. BDD-based Algorithms for the Construction of the Set of All Concepts. Contributions to ICCS 2002. Borovets, Bulgaria. pp.61–73.
[31] Zabezhailo M. I., Automatic Documentation and Mathematical Linguistics 21 pp 1– (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.