An Efficient Map-Reduce Algorithm for Computing Formal Concepts from Binary data

摘要

The problem of discovering all formal concepts embedded in a binary relational dataset is of significant interest for many data analysis and processing problems. The problem of enumerating all concepts for a dataset is known to be NP-hard. A number of Map-Reduce based algorithms have been developed to conquer the difficulty of processing large datasets. But these algorithms are not very scalable because at core all these algorithms stick to a DFS based sequential search for individual concepts, applying Map-Reduce formalism to parallelize the processing at nodes of the DFS tree. We have present here a completely different and Map-Reduce based formulation for parallelizing the concept discovery problem. One major difference of our approach is that we seek to find a sufficient set of concepts only, and this sufficient set can be used to generate all other concepts in the lattice. This formulation is not very suitable for sequential execution but adapts extremely well to the parallel environments based on Map-Reduce operators. We show in this paper that our algorithm is significantly faster than all the known Map-reduce formulations for discovering concepts in binary relational datasets. We have presented in this paper the outline of the theoretical foundations for our algorithm and empirical tests with a number of benchmarking datasets. We also show that the computationally very difficult problem of finding 3-clusters in pairs of binary relational datasets can also be made very efficient by our formulation.