The development of a semantic Web with data that machines can understand depends crucially on the formal representation of knowledge in suitable ontologies (that is, sets of concepts within certain domains). The goal of formal concept analysis (FCA) is to automatically generate an ontology from a given set of objects with characterizing attributes. For this purpose, various FCA algorithms have been developed and implemented in several software packages. However, the last comparison on the efficiency of algorithms for tasks related to FCA took place in 2004; data for current implementations is lacking.
To overcome this problem, the authors used the software package Graph Model Workshop (GMW) to develop an environment for benchmarking FCA implementations by reading input data in two FCA formats (Frequent Itemset Mining Implementations (FIMI) and Burmeister), running the programs on the inputs, validating the correctness of the results, and measuring the execution times. At a 2009 workshop, the environment was used to benchmark four programs with real-life datasets as well as syntactic ones. Two programs implemented classical FCA algorithms, and two others independently implemented a newer “close-by-one” algorithm.
The results clearly demonstrate that the two implementations of “close-by-one” outperform the other programs, and each has its advantages in certain situations. All of the results are collected in a database in a systematic way. The paper sketches the benchmark results and invites researchers to submit new programs and datasets. As a result, the presented environment may become a central point of information exchange in FCA.