A new parallel algorithm for computing formal concepts based on two parallel stages

The fixpoints of Galois connections induced by binary relational data are called formal con-cepts in formal concept analysis (FCA). Computing formal concepts is one of the most important issues in FCA, while Close-by-One (CbO) and its variants are usually considered as the most efficient serial algorithms for this task. Current approaches to parallelization of CbO-type algorithms such as PCbO (Parallel CbO) usually enter the parallel stage after a serial stage which could be a possible bottleneck. In this paper, we propose a new parallel algorithm for computing formal concepts, which is composed of two parallel phases. The new algorithm parallelizes both the computations of the top L recursion levels and the workload distribution, which decouples worker threads from the main thread. We describe the algorithm and present an experimental evaluation of its performance and comparison with PCbO on various datasets. Results indicate that our algorithm performs better, espe-cially when a dataset is dense or has a large size.(c) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper proposes a new parallel algorithm for computing formal concepts. The algorithm tackles the issues of computation and workload distribution through two parallel phases, resulting in improved performance.