The Carve algorithm uses a divide-and-conquer strategy to compute the concept lattice of a formal context. The decomposition phase of the Carve algorithm discovers hierarchical structure in an amenable formal context, which the synthesis phase then exploits to construct the concept lattice from those of the component sub-contexts. In this paper, the problem of computing a sound and complete set of attribute implications via a refinement of the Carve decomposition is studied. Indeed, a set of rules is devised to obtain a set of valid implications which is proved to be complete. The refined decomposition and these rules are implemented in the novel Carve+ algorithm, whose runtime compares favorably with direct computation of the Duquenne–Guigues base of implications via the NextClosure algorithm.

Formal Concept Analysis (FCA) derives a multiple-inheritance class hierarchy from a formal context. The number of classes is bounded above by an exponential function of the number of objects and attributes in the context. To support interactive analysis of large formal contexts, this paper exploits a divide-and-conquer technique which discovers hierarchical structure in amenable formal contexts. That hierarchical structure is used to expedite and enhance both the layout of, and user interaction with, the concept lattice. The principal contribution is the dual use of the discovered hierarchical structure for scalable, interactive FCA.