Minimal generators, an affordable approach by means of massive computation

 

Abstract

Closed sets and minimal generators are fundamental elements to build a complete knowledge representation in formal concept analysis. The enumeration of all the closed sets and their minimal generators from a set of rules or implications constitutes a complex problem, drawing an exponential cost. Even for small datasets, such representation can demand an exhaustive management of the information stored as attribute implications. In this work, we tackle this problem by merging two strategies. On the one hand, we design a pruning, strongly based on logic properties, to drastically reduce the search space of the method. On the other hand, we consider a parallelization of the problem leading to a massive computation by means of a map-reduce like paradigm. In this study we have characterized the type of search space reductions suitable for parallelization. Also, we have analyzed different situations to provide an orientation of the resources (number of cores) needed for both the parallel architecture and the size of the problem in the splitting stage to take advantage in the map stage.

Citation

Please, cite this work as:

[Ben+19] F. Benito-Picazo, P. Cordero, M. Enciso, et al. “Minimal generators, an affordable approach by means of massive computation”. In: The Journal of Supercomputing 75.3 (Mar. 2019), pp. 1350-1367. ISSN: 1573-0484. DOI: 10.1007/s11227-018-2453-z. URL: https://doi.org/10.1007/s11227-018-2453-z.

BibTeX

@Article{Benito-Picazo2019,
    author={Benito-Picazo, F.
    and Cordero, P.
    and Enciso, M.
    and Mora, A.},
    title={Minimal generators, an affordable approach by means of massive computation},
    journal={The Journal of Supercomputing},
    year={2019},
    month={Mar},
    day={01},
    volume={75},
    number={3},
    pages={1350-1367},
    abstract={Closed sets and minimal generators are fundamental elements to build a complete knowledge representation in formal concept analysis. The enumeration of all the closed sets and their minimal generators from a set of rules or implications constitutes a complex problem, drawing an exponential cost. Even for small datasets, such representation can demand an exhaustive management of the information stored as attribute implications. In this work, we tackle this problem by merging two strategies. On the one hand, we design a pruning, strongly based on logic properties, to drastically reduce the search space of the method. On the other hand, we consider a parallelization of the problem leading to a massive computation by means of a map-reduce like paradigm. In this study we have characterized the type of search space reductions suitable for parallelization. Also, we have analyzed different situations to provide an orientation of the resources (number of cores) needed for both the parallel architecture and the size of the problem in the splitting stage to take advantage in the map stage.},
    issn={1573-0484},
    doi={10.1007/s11227-018-2453-z},
    url={https://doi.org/10.1007/s11227-018-2453-z}
}