Comparing performance of algorithms for generating concept lattices

TLDR

Concept lattices are increasingly used as tools for intelligent data analysis. This study examines several algorithms that generate all formal concepts and diagram graphs of concept lattices. The authors propose modifications to well‑known algorithms, analyze their worst‑case and experimental complexity, and outline principles for comparing practical performance. They find that algorithmic complexity varies with context density, providing guidelines for selecting algorithms based on sparsity or density, and discuss practical performance comparison principles.

Abstract

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 wellknown 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.