Abstract | ||
---|---|---|
The scalability issue has always been a bottleneck for formal concept analysis (FCA) since the number of formal concepts is possibly exponential in the formal context. Motivated by the need to handle large formal contexts efficiently, we propose a parallel algorithm for computing formal concepts, the aim of which is to make Close-by-One (CbO) and its variants highly parallelized and easy to apply. Current approaches to parallelization of CbO-type algorithms such as PCbO (Parallel CbO) compute concepts in the top L recursion levels in serial and then turn to parallel computation after that. To avoid massive serial computations and the hassle of choosing the hyperparameter L in real applications, our proposed algorithm enters parallelization at once after the computation of the top concept and its direct successors, and then uses a parallel reshuffle approach to rebalance the workload distribution among worker threads without communication with the main thread. We describe the algorithm and present an experimental evaluation of its performance and comparison with PCbO on various datasets. Empirical analyses demonstrate that our algorithm is superior when applied to various types of formal contexts. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1007/s13042-022-01547-1 | International Journal of Machine Learning and Cybernetics |
Keywords | DocType | Volume |
Formal concept analysis, Formal concept, Parallel algorithm | Journal | 13 |
Issue | ISSN | Citations |
9 | 1868-8071 | 0 |
PageRank | References | Authors |
0.34 | 22 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zou, Ligeng | 1 | 0 | 0.34 |
Chen, Xiaozhi | 2 | 0 | 0.34 |
Tingting He | 3 | 348 | 61.04 |
Jianhua Dai | 4 | 896 | 51.62 |