Revisiting the GreCon algorithm for Boolean matrix factorization

摘要

Over the past decade, the most fundamental Boolean matrix factorization (BMF) algorithms GreCon and GreConD were proposed. Whereas GreConD has become a popular and widely used BMF algorithm, GreCon – the algorithm on which the GreConD is built – is somewhat forgotten in contemporary BMF research; however, GreCon may produce better results than GreConD. The main disadvantage of GreCon algorithm is a slow running time. In the paper, we argue that the search strategy of GreConD, notwithstanding it provides a good result, is limited. We show that the reasons for not using GreCon algorithm are no longer the truth. We revise the algorithm and propose a new approach to storing and updating data required for factor enumeration. By various experiments, we demonstrate that the revised version is competitive with contemporary BMF algorithms in terms of running time. Moreover, in some cases, the revised GreCon outperforms GreConD—one of the fastest BMF algorithms. Furthermore, we show that our novel approach to GreCon enables the utilization of novel approaches to BMF.