A parallel algorithm based on search space partition for generating concepts

摘要

Concept lattice, the core data structure in formal concept analysis, has been used widely in machine learning, data mining and knowledge discovery, information retrieval, etc. The main difficulty with concept lattice-based system comes from the lattice construction itself. In this paper, a parallel algorithm based on the closure search space partition for computing concepts is proposed. This algorithm divides the closure search space into several subspaces in accordance with criterions prescribed ahead and introduces an efficient scheme to recognize the valid ones, in which the searching for closures is bounded. An intermediate structure is employed to judge the validity of a subspace and compute closures more efficiently. Since the searching in subspaces are independent tasks, a parallel algorithm based on search space partition can be directly reached.