NextClosures: parallel computation of the canonical base with background knowledge

Abstract

The canonical base of a formal context plays a distinguished role in Formal Concept Analysis, as it is the only minimal implicational base known so far that can be described explicitly. Consequently, several algorithms for the computation of this base have been proposed. However, all those algorithms work sequentially by computing only one pseudo-intent at a time – a fact that heavily impairs the practicability in real-world applications. In this paper, we shall introduce an approach that remedies this deficit by allowing the canonical base to be computed in a parallel manner with respect to arbitrary implicational background knowledge. First experimental evaluations show that for sufficiently large data sets the speed-up is proportional to the number of available CPU cores.

Keywords:

• Formal Concept Analysis
• parallel algorithm
• implication
• canonical base
• background knowledge

Acknowledgements

The authors gratefully thank Bernhard Ganter for his helpful hints on optimal formal contexts for his NextClosure algorithm. Furthermore, the authors greatly appreciate the constructive hints and helpful remarks of the anonymous reviewers. The benchmarks were performed on servers at the Institute of Theoretical Computer Science, and the Centre for Information Services and High Performance Computing (ZIH) at TU Dresden. We thank them both for their generous allocations of computer time.

Notes

No potential conflict of interest was reported by the authors.

1 The test contexts used for the experiments can be obtained from the authors via email.